ボロノイ図を軽く解説
import net.hires.debug.Stats;
ボロノイ図描画
Quasimondo 先生が 2002 年に書いたコードの写経です。
ステージをクリックしてね。何度も何度もクリックしてね。
オリジナル：http://www.quasimondo.com/archives/000110.php
説明：http://aquioux.blog48.fc2.com/blog-entry-654.html
/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/8oFd
*/
// forked from Aquioux's ボロノイ図
package {
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFormat;
//import net.hires.debug.Stats;
[SWF(width = "465", height = "465", frameRate = "30", backgroundColor = "#FFFFFF")]
/**
* ボロノイ図描画
* Quasimondo 先生が 2002 年に書いたコードの写経です。
* ステージをクリックしてね。何度も何度もクリックしてね。
* オリジナル：http://www.quasimondo.com/archives/000110.php
* 説明：http://aquioux.blog48.fc2.com/blog-entry-654.html
*/
public class Main extends Sprite {
private const STAGE_WIDTH:uint = stage.stageWidth;
private const STAGE_HEIGHT:uint = stage.stageHeight;
private var dots:Array; // Dot の配列
private var sx:Array; // 線開始座標（X座標）
private var sy:Array; // 線開始座標（Y座標）
private var ex:Array; // 線終了座標（X座標）
private var ey:Array; // 線終了座標（Y座標）
private var dotLayer:Sprite; // ドットのコンテナ
private var lineLayer:Sprite; // 線描画用レイヤ
private var textField:TextField; // "Click STAGE"
public function Main():void {
// 配列初期化
dots = [];
sx = [];
sy = [];
ex = [];
ey = [];
// コンテナ等
addChild(dotLayer = new Sprite());
addChild(lineLayer = new Sprite());
//addChild(new Stats());
textField = new TextField();
textField.defaultTextFormat = new TextFormat("_serif", 20, 0x000000);
textField.text = "Click STAGE";
textField.autoSize = TextFieldAutoSize.LEFT;
textField.selectable = false;
textField.x = (STAGE_WIDTH - textField.width) / 2;
textField.y = (STAGE_HEIGHT - textField.height) / 2;
addChild(textField);
// 最初に Dot を3つ配置
for (var i:int = 0; i < 3; i++) {
addDot(Math.random() * STAGE_WIDTH, Math.random() * STAGE_HEIGHT);
}
// イベントリスナー
addEventListener(Event.ENTER_FRAME, enterFrameHandler);
stage.addEventListener(MouseEvent.CLICK, clickHandler);
}
// ENTER_FRAME
private function enterFrameHandler(event:Event):void {
moveDot(); // Dot の移動
setVoronoi(); // ボロノイ境界線の計算
drawVolonoi(); // ボロノイ境界線の描画
}
// Dot の移動
private function moveDot():void {
var n:uint = dots.length;
for (var i:int = 0; i < n; i++) {
var dot:Dot = dots[i];
dot.update();
}
}
// ボロノイ境界線の計算
// 長い線分をつくってから、それぞれの交点を計算してトリミングしていきます。
private function setVoronoi():void {
var a:Number;
var b:Number;
var a0:Number;
var b0:Number;
var a1:Number;
var b1:Number;
var x:Number;
var y:Number;
var x0:Number;
var y0:Number;
var x1:Number;
var y1:Number;
var n:uint = dots.length;
var m:uint = n + 3;
// 各dotについて、dot同士と画面境界の線分をつくる
// sx,syは線分の開始点, ex,eyは終端点とでも
for (var i:int = 0; i < n; i++) {
x0 = dots[i].x;
y0 = dots[i].y;
var idx1:int = i * m + i + 1; // 以降の線分は[i][i+1]~[i][m-1]の間に格納する
// 相手をするdot
for (var j:int = i + 1; j < n; j++) {
x1 = dots[j].x;
y1 = dots[j].y;
// 垂直二等分線を求める。
// aは傾き、bは切片
if (x1 == x0) {
a = 0;
} else if (y1 == y0) {
a = 10000;
} else {
a = -1 / ((y1 - y0) / (x1 - x0));
}
b = (y0 + y1) / 2 - a * (x0 + x1) / 2;
// 45度以下の傾きなら画面境界のx座標でぶったぎる
// それ以上の傾きならy座標でぶったぎる
if (a > -1 && a <= 1) {
sx[idx1] = 0;
sy[idx1] = a * sx[idx1] + b;
ex[idx1] = STAGE_WIDTH - 1;
ey[idx1] = a * ex[idx1] + b;
} else {
sy[idx1] = 0;
sx[idx1] = (sy[idx1] - b) / a;
ey[idx1] = STAGE_HEIGHT - 1;
ex[idx1] = (ey[idx1] - b) / a;
}
idx1++;
}
// 画面境界
sx[idx1] = 0;
sy[idx1] = 0;
ex[idx1] = STAGE_WIDTH;
ey[idx1] = 0;
idx1++;
sx[idx1] = 0;
sy[idx1] = 0;
ex[idx1] = 0;
ey[idx1] = STAGE_HEIGHT;
idx1++;
sx[idx1] = STAGE_WIDTH;
sy[idx1] = 0;
ex[idx1] = STAGE_WIDTH;
ey[idx1] = STAGE_HEIGHT;
idx1++;
sx[idx1] = 0;
sy[idx1] = STAGE_HEIGHT;
ex[idx1] = STAGE_WIDTH;
ey[idx1] = STAGE_HEIGHT;
}
// それぞれの線分たちを見てトリミングしていく
// 各dotについて
for (i = 0; i < n; i++) {
x0 = dots[i].x;
y0 = dots[i].y;
// 各線分(S1とする)について(jは線分をつくった相手のdotのインデックス)
for (j = 0; j < m + 1; j++) {
if (j != i) {
if (j > i) {
idx1 = i * m + j;
} else {
idx1 = j * m + i;
}
// -Number.MAX_VALUEだったらトリミング対象にしない(後述)
if (sx[idx1] > -Number.MAX_VALUE) {
// S1の傾き・切片をとる
a0 = (ey[idx1] - sy[idx1]) / (ex[idx1] - sx[idx1]);
b0 = sy[idx1] - a0 * sx[idx1];
// dotについてできているもう一個の線分(S2)をとってくる。
// S1-S2間でS2をトリミングする。S1は、iとjが逆になっているときトリミングされる。
for (var k:int = i + 1; k < m + 1; k++) {
if (k != j) {
var idx2:int = i * m + k;
if (sx[idx2] > -Number.MAX_VALUE) {
// S2の傾き・切片をとる
a1 = (ey[idx2] - sy[idx2]) / (ex[idx2] - sx[idx2]);
b1 = sy[idx2] - a1 * sx[idx2];
// S1とS2の交点を求める
x = -(b1 - b0) / (a1 - a0);
y = a0 * x + b0;
// S1からみて、dotとS2の開始点が反対方向にあれば
if ((a0 * x0 + b0 - y0) * (a0 * sx[idx2] + b0 - sy[idx2]) < 0) {
// S2の開始点をS1とS2の交点にする(トリミング)
sx[idx2] = x;
sy[idx2] = y;
}
// S1からみて、dotとS2の終端点が反対方向にあれば
if ((a0 * x0 + b0 - y0) * (a0 * ex[idx2] + b0 - ey[idx2]) < 0) {
// この上のトリミングが行われている場合、
// S1からみて、S2の全体がdotと逆方向にあるため、
// S2はもう表示する必要がない。
// よってトリミング対象から外す。
if(sx[idx2] == x) {
sx[idx2] = -Number.MAX_VALUE;
} else {
// S2の開始点をS1とS2の交点にする(トリミング)
ex[idx2] = x;
ey[idx2] = y;
}
}
}
}
}
}
}
}
}
}
// ボロノイ境界線の描画
private function drawVolonoi():void {
lineLayer.graphics.clear();
lineLayer.graphics.lineStyle(0, 0x666666);
var n:uint = dots.length;
var m:uint = n + 3;
for (var i:int = 0; i < n; i++) {
var idx:uint = i * m + i + 1;
for (var j:int = i + 1; j < m + 1; j++) {
if (sx[idx] > -Number.MAX_VALUE) {
lineLayer.graphics.moveTo(sx[idx], sy[idx]);
lineLayer.graphics.lineTo(ex[idx], ey[idx]);
}
idx++;
}
}
}
// マウスイベント
private function clickHandler(event:MouseEvent):void {
if (textField) {
removeChild(textField);
textField = null;
}
addDot(mouseX, mouseY);
}
// Dot をコンテナ上に追加する
private function addDot(x:Number, y:Number):void {
var dot:Dot = new Dot();
dot.x = x;
dot.y = y;
dots.push(dot);
dotLayer.addChild(dot);
}
}
}
import flash.display.Shape;
import flash.events.Event;
class Dot extends Shape {
private const RADIUS:uint = 3;
private var vx:Number = 2.0; // X軸ベロシティ
private var vy:Number = 2.0; // Y軸ベロシティ
private var sw:Number; // ステージ幅
private var sh:Number; // ステージ高
public function Dot() {
graphics.beginFill(0xCC0033);
graphics.drawCircle(0, 0, RADIUS);
graphics.endFill();
addEventListener(Event.ADDED_TO_STAGE, addHandler);
}
private function addHandler(event:Event):void {
removeEventListener(Event.ADDED_TO_STAGE, addHandler);
sw = stage.stageWidth;
sh = stage.stageHeight;
if (Math.random() < 0.5) {
vx *= -1;
}
if (Math.random() < 0.5) {
vy *= -1;
}
}
// 移動
public function update():void {
x += vx;
y += vy;
if (x < RADIUS) {
x = RADIUS;
vx *= -1;
}
if (x > sw - RADIUS) {
x = sw - RADIUS;
vx *= -1;
}
if (y < RADIUS) {
y = RADIUS;
vy *= -1;
}
if (y > sh - RADIUS) {
y = sh - RADIUS;
vy *= -1;
}
}
}