ボロノイ領域分割2
離散ボロノイ分割の勉強．
「2次元離散ボロノイ図をO(1)の計算時間で描く方法」(http://ci.nii.ac.jp/naid/110003315533)を参考に実装したもの．
ランダムな900点を母点としてそこを中心とする円を拡げることでボロノイ図を描写．
勉強のためにアニメーションにした．
/**
* Copyright Dorara ( http://wonderfl.net/user/Dorara )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/6QG8
*/
package
{
import flash.display.*;
import flash.events.*;
[SWF(width="465", height="465")]
public class Main extends Sprite
{
private var pts:Array; //母点情報
private var sp:Sprite; //点を表示するsprite
private var canvas:BitmapData; //領域を表示するBitmapData
private var jj:int; //距離データのインデックス
private var colormap:Array; //各母点の色情報
private var dist:Array; //距離データ
private var mpN:int = 900; //母点の個数(適当)
public function Main():void
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
//ここからはじまれ
private function init(e:Event = null):void
{
removeEventListener(Event.ADDED_TO_STAGE, init);
this.stage.scaleMode = StageScaleMode.NO_SCALE;
this.stage.align = StageAlign.TOP_LEFT;
canvas = new BitmapData(this.stage.stageWidth, this.stage.stageHeight, false, 0x0);
this.addChild(new Bitmap(canvas));
sp = new Sprite();
this.addChild(sp);
//母点の作成(ランダムに)
pts = new Array();
for (var i:int = 0; i < mpN; i++)
{
var xx:int = this.stage.stageWidth * Math.random();
var yy:int = this.stage.stageHeight * Math.random();
pts.push( { x:xx, y:yy, d2:0, e2:0 } );
sp.graphics.beginFill(0x0);
sp.graphics.drawCircle(xx, yy, 2);
sp.graphics.endFill();
}
//領域の色を決める
colormap = new Array();
for (var l:int = 0; l < pts.length; l++)
{
colormap.push((int)(0xfffffe * Math.random())+1); //0x0を初期値としたいため
}
//距離データの作成
dist = new Array();
for (i = 0; i < this.stage.stageWidth; i++)
{
for (var j:int = 0; j <= i; j++)
{
dist.push( { x:i, y:j, r2:(i * i + j * j) } );
}
}
dist.sortOn("r2", Array.NUMERIC); //距離でソート
jj = 0; //距離データのインデックスを先頭に
this.addEventListener(Event.ENTER_FRAME, onEnterFrame);
}
private function onEnterFrame(e:Event):void
{
draw(); //円を拡げる描写
}
//画面内かどうか
private function inRange(x:int, y:int):Boolean
{
return (0 <= x && x < canvas.width && 0 <= y && y < canvas.height);
}
//母点から(離散)ボロノイ領域を計算する
private function draw(): void
{
var n_pts:int = 0; //残っている母点数
for (var i:int = 0; i < pts.length; i++)
{
if (pts[i].d2 >= 0) {
n_pts++;
}
}
if (n_pts == 0) return; //残っていないなら終了
if (jj >= dist.length) return; //あり得ないけど，距離データの最大値を超えたら終了
//距離データ
var dxj:int = dist[jj].x;
var dyj:int = dist[jj].y;
var r2j:int = dist[jj].r2;
for (var k:int = 0; k < pts.length; k++)
{
if (pts[k].d2 < 0) continue;
//母点情報
var dxi:int = pts[k].x;
var dyi:int = pts[k].y;
var d2i:int = pts[k].d2;
var dci:uint = colormap[k];
//母点から変化分だけ移動させた位置すべてに対して色を付けられるならつける
var flg:Boolean = false; //1箇所以上画素に色を付けられたかどうか
if (dxj == 0 && dyj == 0) {
if (inRange(dxi + dxj, dyi + dyj) && canvas.getPixel(dxi + dxj, dyi + dyj) == 0x0) {
flg = true;
canvas.setPixel32(dxi + dxj, dyi + dyj, dci);
}
}
else if (dxj != 0 && dyj == 0) {
if (inRange(dxi + dxj, dyi + 0) && canvas.getPixel(dxi + dxj, dyi + 0) == 0x0) {
flg = true;
canvas.setPixel32(dxi + dxj, dyi + 0, dci);
}
if (inRange(dxi + 0, dyi - dxj) && canvas.getPixel(dxi + 0, dyi - dxj) == 0x0) {
flg = true;
canvas.setPixel32(dxi + 0, dyi - dxj, dci);
}
if (inRange(dxi - dxj, dyi + 0) && canvas.getPixel(dxi - dxj, dyi + 0) == 0x0) {
flg = true;
canvas.setPixel32(dxi - dxj, dyi + 0, dci);
}
if (inRange(dxi + 0, dyi + dxj) && canvas.getPixel(dxi + 0, dyi + dxj) == 0x0) {
flg = true;
canvas.setPixel32(dxi + 0, dyi + dxj, dci);
}
}
else if (dxj == dyj) {
if (inRange(dxi + dxj, dyi + dyj) && canvas.getPixel(dxi + dxj, dyi + dyj) == 0x0) {
flg = true;
canvas.setPixel32(dxi + dxj, dyi + dyj, dci);
}
if (inRange(dxi + dxj, dyi - dyj) && canvas.getPixel(dxi + dxj, dyi - dyj) == 0x0) {
flg = true;
canvas.setPixel32(dxi + dxj, dyi - dyj, dci);
}
if (inRange(dxi - dxj, dyi - dyj) && canvas.getPixel(dxi - dxj, dyi - dyj) == 0x0) {
flg = true;
canvas.setPixel32(dxi - dxj, dyi - dyj, dci);
}
if (inRange(dxi - dxj, dyi + dyj) && canvas.getPixel(dxi - dxj, dyi + dyj) == 0x0) {
flg = true;
canvas.setPixel32(dxi - dxj, dyi + dyj, dci);
}
}
else {
if (inRange(dxi + dxj, dyi + dyj) && canvas.getPixel(dxi + dxj, dyi + dyj) == 0x0) {
flg = true;
canvas.setPixel32(dxi + dxj, dyi + dyj, dci);
}
if (inRange(dxi + dxj, dyi - dyj) && canvas.getPixel(dxi + dxj, dyi - dyj) == 0x0) {
flg = true;
canvas.setPixel32(dxi + dxj, dyi - dyj, dci);
}
if (inRange(dxi - dxj, dyi - dyj) && canvas.getPixel(dxi - dxj, dyi - dyj) == 0x0) {
flg = true;
canvas.setPixel32(dxi - dxj, dyi - dyj, dci);
}
if (inRange(dxi - dxj, dyi + dyj) && canvas.getPixel(dxi - dxj, dyi + dyj) == 0x0) {
flg = true;
canvas.setPixel32(dxi - dxj, dyi + dyj, dci);
}
//反転
if (inRange(dxi + dyj, dyi + dxj) && canvas.getPixel(dxi + dyj, dyi + dxj) == 0x0) {
flg = true;
canvas.setPixel32(dxi + dyj, dyi + dxj, dci);
}
if (inRange(dxi + dyj, dyi - dxj) && canvas.getPixel(dxi + dyj, dyi - dxj) == 0x0) {
flg = true;
canvas.setPixel32(dxi + dyj, dyi - dxj, dci);
}
if (inRange(dxi - dyj, dyi - dxj) && canvas.getPixel(dxi - dyj, dyi - dxj) == 0x0) {
flg = true;
canvas.setPixel32(dxi - dyj, dyi - dxj, dci);
}
if (inRange(dxi - dyj, dyi + dxj) && canvas.getPixel(dxi - dyj, dyi + dxj) == 0x0) {
flg = true;
canvas.setPixel32(dxi - dyj, dyi + dxj, dci);
}
}
//終了判定
if (flg)
{
pts[k].d2 = r2j;
} else {
pts[k].e2 = r2j;
if (pts[k].e2 > d2i + (int)(2 * Math.sqrt(d2i)) + 1) {
//if (Math.sqrt(pts[k].e2) - Math.sqrt(pts[k].d2) > 1.0){
pts[k].d2 = -1; //母点を削除
}
}
}
jj++; //次の距離データへ
}
}
}