webカムもっちりボロノイ図
webカム映像からランダムで画素をサンプリングして
K-Means法でクラスタリングして、もっちりボロノイ図に
はっきり言って何が何だか分からない。
@author
/**
* Copyright knd ( http://wonderfl.net/user/knd )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/txg6
*/
// forked from knd's もっちりボロノイ図
package
{
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.GraphicsSolidFill;
import flash.display.GraphicsStroke;
import flash.display.IGraphicsData;
import flash.display.IGraphicsFill;
import flash.display.Sprite;
import flash.events.Event;
import flash.geom.Point;
import flash.media.Camera;
import flash.media.Video;
/**
* webカム映像からランダムで画素をサンプリングして
* K-Means法でクラスタリングして、もっちりボロノイ図に
*
* はっきり言って何が何だか分からない。
* @author
*/
[SWF(width="465",height="465",backgroundColor="0x0",frameRate="30")]
public class KMeanVoronoi extends Sprite
{
private const W:Number = 465;
private const H:Number = 465;
//サンプリングしたRGB-XYを5次元空間にプロットするときの重み付け
private const R2U:Number = 0.54;
private const G2V:Number = 1.08;
private const B2W:Number = 0.18;
//UVW座標をRGBにもどす
private const U2R:Number = 1 / R2U;
private const V2G:Number = 1 / G2V;
private const W2B:Number = 1 / B2W;
private const COL:uint = 8;
private const ROW:uint = 7;
private const K:uint = COL * ROW; //クラスター数
private const S:uint = K * 35; //1フレームあたりのサンプル数
private const TOTAL_S:uint = K * 200; //クラスター重心の更新に使うサンプル総数
private const SURVIVAL:Number = Number(TOTAL_S - S) / Number(TOTAL_S);
private const MOCCHIRI:Boolean = true;
private var camera:Camera;
private var video:Video;
private var bmd:BitmapData;
private var clusters:Vector.<ClusterVector>;
private var points:Vector.<Point>;
private var fills:Vector.<IGraphicsFill>;
private var strokes:Vector.<GraphicsStroke>;
private var f:Fortune;
private var gd:Vector.<IGraphicsData>;
public function KMeanVoronoi()
{
var i:uint;
camera = Camera.getCamera();
camera.setMode(W, H, 30);
video = new Video(W, H);
if (camera) video.attachCamera(camera);
bmd = new BitmapData(W, H, false);
clusters = new Vector.<ClusterVector>();
for (i = 0; i< K; i++)
{
var cv:ClusterVector = new ClusterVector();
cv.x = W / COL * (i % COL + 0.5);
cv.y = H / ROW * (uint(i / COL) + 0.5);
clusters[i] = cv;
}
points = new Vector.<Point>();
fills = new Vector.<IGraphicsFill>();
strokes = new Vector.<GraphicsStroke>();
gd = new Vector.<IGraphicsData>();
for (i = 0; i < K; i++)
{
points[i] = new Point(clusters[i].x, clusters[i].y);
}
f = new Fortune(points, 0, 0, W, H);
for (i = 0; i < K; i++)
{
fills[i] = new GraphicsSolidFill();
strokes[i] = new GraphicsStroke(0);
strokes[i].fill = new GraphicsSolidFill();
gd.push(strokes[i], fills[i], f.graphicsPaths[i]);
}
addEventListener(Event.ENTER_FRAME, loop);
}
private function loop(e:Event):void
{
bmd.draw(video);
var i:uint, j:uint;
var cv:ClusterVector, pt:Point, clr:uint;
for (j = 0; j< S; j++)
{
var px:Number = W * Math.random();
var py:Number = H * Math.random();
var pv:Vector5D = makeVector5D(px, py, bmd.getPixel(px, py));
var minDist:Number = Number.MAX_VALUE;
var dist:Number;
for (i = 0; i< K; i++)
{
dist = pv.distance(clusters[i]);
if (dist < minDist)
{
cv = clusters[i];
minDist = dist;
}
}
cv.add(pv);
}
for (i = 0; i< K; i++)
{
cv = clusters[i];
cv.update(SURVIVAL);
pt = points[i];
pt.x = cv.x;
pt.y = cv.y;
clr = getColorOf(cv);
GraphicsSolidFill(fills[i]).color = clr;
GraphicsSolidFill(strokes[i].fill).color = 0x808080 | ((clr & 0xfefefe) >>> 1);
}
f.update(MOCCHIRI);
graphics.clear();
graphics.drawGraphicsData(gd);
}
private function makeVector5D(pixelX:Number, pixelY:Number, rgbColor:uint):Vector5D
{
var pv:Vector5D = new Vector5D();
pv.x = pixelX;
pv.y = pixelY;
pv.u = ((rgbColor >> 16) & 0xff) * R2U;
pv.v = ((rgbColor >> 8) & 0xff) * G2V;
pv.w = (rgbColor & 0xff) * B2W;
return pv;
}
private function getColorOf(pv:Vector5D):uint
{
var r:uint = pv.u * U2R;
r > 0xff? (r = 0xff): null;
var g:uint = pv.v * V2G;
g > 0xff? (g = 0xff): null;
var b:uint = pv.w * W2B;
b > 0xff? (b = 0xff): null;
return (r << 16) | (g << 8) | b;
}
}
}
internal class Vector5D
{
public var u:Number = 0;
public var v:Number = 0;
public var w:Number = 0;
public var x:Number = 0;
public var y:Number = 0;
public function distance(pv:Vector5D):Number
{
var du:Number = pv.u - u;
var dv:Number = pv.v - v;
var dw:Number = pv.w - w;
var dx:Number = pv.x - x;
var dy:Number = pv.y - y;
return Math.sqrt(du * du + dv * dv + dw * dw + dx * dx + dy * dy); //Euclid distance
//du < 0? (du = -du): null;
//dv < 0? (dv = -dv): null;
//dw < 0? (dw = -dw): null;
//dx < 0? (dx = -dx): null;
//dy < 0? (dy = -dy): null;
//return du + dv + dw + dx + dy; //Manhattan distance
}
}
internal class ClusterVector extends Vector5D
{
public var count:Number = 0;
private var tempCount:Number = 0;
private var uSum:Number = 0, vSum:Number = 0, wSum:Number = 0, xSum:Number = 0, ySum:Number = 0;
public function add(pv:Vector5D):void
{
tempCount += 1;
uSum += pv.u;
vSum += pv.v;
wSum += pv.w;
xSum += pv.x;
ySum += pv.y;
}
public function update(survival:Number):void
{
if (tempCount > 0)
{
var div:Number = 1 / tempCount;
u = uSum * div;
v = vSum * div;
w = wSum * div;
x = xSum * div;
y = ySum * div;
count = tempCount;
}
else
{
x += 10 * (0.5 - Math.random());
y += 10 * (0.5 - Math.random());
}
tempCount *= survival;
uSum *= survival;
vSum *= survival;
wSum *= survival;
xSum *= survival;
ySum *= survival;
}
}
import flash.display.GraphicsSolidFill;
import flash.display.GraphicsStroke;
import flash.display.IGraphicsData;
import flash.display.GraphicsPath;
import flash.display.GraphicsPathCommand;
import flash.geom.Point;
internal class Fortune
{
private var _length:int;
private var _points:Vector.<Point>;
private var _cells:Vector.<FortuneCell>;
private var _graphicsPaths:Vector.<IGraphicsData>;
private var _topY:Number;
private var _leftX:Number;
private var _rightX:Number;
private var _bottomY:Number;
private var _topBounds:YBoundaryCell;
private var _leftBounds:XBoundaryCell;
private var _rightBounds:XBoundaryCell;
private var _bottomBounds:YBoundaryCell;
private var _waitCellsHead:FortuneCell;
private var _activeCellsHead:FortuneCell;
private var _beachLineLeftmost:BeachLine;
private var _beachLineTop:Number;
private var _sweepLine:Number;
public function Fortune(points:Vector.<Point>,
topBoundary:Number, leftBoundary:Number, rightBoundary:Number, bottomBoundary:Number)
{
_length = points.length;
_points = points;
_cells = new Vector.<FortuneCell>(_length);
_graphicsPaths = new Vector.<IGraphicsData>();
for (var i:int = 0; i< _length; i++)
{
_cells[i] = new FortuneCell(points[i]);
_graphicsPaths[i] = _cells[i].graphicsPath;
}
_topBounds = new YBoundaryCell(topBoundary);
_leftBounds = new XBoundaryCell(leftBoundary);
_rightBounds = new XBoundaryCell(rightBoundary);
_bottomBounds = new YBoundaryCell(bottomBoundary);
_topY = topBoundary;
_leftX = leftBoundary;
_rightX = rightBoundary;
_bottomY = bottomBoundary;
}
public function update(curve:Boolean = false):void
{
reset();
//追加待ちの母点または評価待ちのボロノイ点候補が残っていて、かつ境界内にbeachlineが残っていれば
while (_waitCellsHead)
{
//待ちリストの先頭を取り出して評価
var newCell:FortuneCell = _waitCellsHead;
_waitCellsHead = _waitCellsHead.next;
//この時点で評価対象のセルは待ちリストにもアクティブリストにも含まれない
//sweeplineの移動
sweepTo(newCell.y);
//考え得るボロノイ点候補について調査
checkNewCell(newCell);
//アクティブなセルとしてリストに追加
newCell.next = _activeCellsHead;
_activeCellsHead = newCell;
}
//最後に各セルで保持しているGraphicsPathを更新する
for (var i:int = 0; i< _length; i++)
{
_cells[i].updateGraphicsPath(curve);
}
}
//新しい母点が関わりうるボロノイ点について調査
private function checkNewCell(newCell:FortuneCell):void
{
var vp:VoronoiPoint;
var ncx:Number = newCell.x;
var chkBL:BeachLine = _beachLineLeftmost;
if (chkBL) do
{
if (ncx <= chkBL.rightEndX)
{
break;
}
} while (chkBL = chkBL.right);
checkBeachLine(newCell, chkBL);
}
// 新しい点をbeachlineに沿って
// 他のボロノイ母点とボロノイ点を作りうるかどうか評価していく
private function checkBeachLine(newCell:FortuneCell, centerBL:BeachLine):void
{
var vp:VoronoiPoint;
var cell:FortuneCell;
var leftCell:FortuneCell;
var rightCell:FortuneCell;
var cot:Number; // 追加点を中心としたcot(=x/y)の値が右に行くにつれて小さくなっていくように
var centerCot:Number;
var leftCot:Number;
var rightCot:Number;
var leftBL:BeachLine;
var rightBL:BeachLine;
// 新しく追加されるセル点の真上の放物線からスタート
// 左に移動しながらボロノイ点候補を探す
leftBL = centerBL;
cell = leftCell = centerBL.cell;
cot = leftCot = cell.getCot(newCell);
while (leftBL = leftBL.left)
{
leftCell = leftBL.cell;
leftCot = leftCell.getCot(newCell);
if (leftCot > cot)
{
vp = new VoronoiPoint(newCell, leftCell, cell);
if (testVoronoi(vp))
{
vp.fix();
cell = leftCell;
cot = leftCot;
}
}
}
//左境界に達したらぐるっと下境界を評価
leftCell = _leftBounds;
vp = new VoronoiPoint(newCell, leftCell, cell);
if (testVoronoi(vp))
{
vp.fix();
cell = leftCell;
}
leftCell = _bottomBounds;
vp = new VoronoiPoint(newCell, leftCell, cell);
if (testVoronoi(vp))
{
vp.fix();
}
// 右に移動しながらボロノイ点候補を探す
rightBL = centerBL;
cell = rightCell = centerBL.cell;
cot = rightCot = cell.getCot(newCell);
while (rightBL = rightBL.right)
{
rightCell = rightBL.cell;
rightCot = rightCell.getCot(newCell);
if (rightCot < cot)
{
vp = new VoronoiPoint(newCell, rightCell, cell);
if (testVoronoi(vp))
{
vp.fix();
cell = rightCell;
cot = rightCot;
}
}
}
rightCell = _rightBounds
vp = new VoronoiPoint(newCell, rightCell, cell);
if (testVoronoi(vp))
{
vp.fix();
cell = rightCell;
}
rightCell = _bottomBounds
vp = new VoronoiPoint(newCell, rightCell, cell);
if (testVoronoi(vp))
{
vp.fix();
}
}
/**
* sweeplineを移動しbeachlineとアクティブなセルを更新する
* コストがかかるのでこのメソッドの呼び出しを極力少なく
* @param y
*/
private function sweepTo(y:Number):void
{
_sweepLine = y;
var cell:FortuneCell = _activeCellsHead;
var beachLineCell:FortuneCell;
var lX:Number = _leftX;
var yVal:Number;
var leftmostY:Number = - Number.MAX_VALUE;
//左境界と放物線の交点が最も下にくるセルを探す
do
{
cell.updateParabola(y);
yVal = cell.getParabolaY(lX);
if (yVal > leftmostY)
{
leftmostY = yVal;
beachLineCell = cell;
}
} while ( cell = cell.next);
_beachLineTop = leftmostY;
beachLineCell.isBeachLine = true;
//このセルの放物線からbeachlineが始まる
var leftCell:FortuneCell = beachLineCell;
_beachLineLeftmost = new BeachLine(leftCell);
var leftBL:BeachLine = _beachLineLeftmost;
leftBL.left = null;
var rightBL:BeachLine;
var solX:QuadraticSolution;
var xVal:Number;
var rX:Number;
//放物線の交点からbeachlineを構成するセルと交点を順に調査
for (;;)
{
cell = _activeCellsHead;
rX = _rightX;
do
{
if (cell === leftCell)
{
continue;
}
solX = leftCell.getIntersectionX(cell);
if (solX)
{
xVal = solX.xSmaller;
if (xVal > lX && xVal < rX)
{
rX = xVal;
beachLineCell = cell;
}
else
{
xVal = solX.xBigger;
if (xVal > lX && xVal < rX)
{
rX = xVal;
beachLineCell = cell;
}
}
}
} while (cell = cell.next);
if (leftCell != beachLineCell && rX < _rightX)
{
yVal = leftCell.getParabolaY(rX);
beachLineCell.isBeachLine = true;
rightBL = new BeachLine(beachLineCell);
rightBL.left = leftBL;
leftBL.right = rightBL;
leftBL.rightEndX = rX;
if (yVal < _beachLineTop)
{
_beachLineTop = yVal;
}
lX = rX;
leftBL = rightBL;
leftCell = beachLineCell;
}
else
{
rX = _rightX;
yVal = leftCell.getParabolaY(rX);
leftBL.right = null;
leftBL.rightEndX = rX;
if (yVal < _beachLineTop)
{
_beachLineTop = yVal;
}
break;
}
}
//beachlineを構成しないセルはリストから外す
while (!_activeCellsHead.isBeachLine)
{
_activeCellsHead = _activeCellsHead.next;
}
cell = _activeCellsHead;
var prevCell:FortuneCell = cell;
while (cell = cell.next)
{
if (!cell.isBeachLine)
{
prevCell.next = cell.next;
}
else
{
prevCell = cell;
}
}
}
/**
* 全セルをリセット
* y昇順にソートし待ちリストに追加しなおす
*/
private function reset():void
{
_sweepLine = _topY;
_waitCellsHead = null;
_activeCellsHead = _topBounds;
_beachLineLeftmost = new BeachLine(_topBounds);
_beachLineTop = - Number.MAX_VALUE;
for (var i:int = 0; i< _length; i++)
{
var cell:FortuneCell = _cells[i];
cell.setPosition(_points[i]);
addWaitCell(cell);
}
}
/**
* セルの評価待ちリストにy昇順になるように追加
* @param cell
*/
private function addWaitCell(cell:FortuneCell):void
{
var cy:Number = cell.y;
if (cy < _sweepLine)
{
return;
}
if (!_waitCellsHead || cy < _waitCellsHead.y)
{
cell.next = _waitCellsHead;
_waitCellsHead = cell;
return;
}
var chkCell:FortuneCell = _waitCellsHead;
var prevCell:FortuneCell = chkCell;
while (chkCell = chkCell.next)
{
if (cy < chkCell.y)
{
prevCell.next = cell;
cell.next = chkCell;
return;
}
prevCell = chkCell;
}
prevCell.next = cell;
}
//ボロノイ点候補を評価して確定してもよければtrue
private function testVoronoi(vp:VoronoiPoint):Boolean
{
return !(isOutBounds(vp) || containsActiveCell(vp) || containsWaitCell(vp))
}
//ボロノイ点候補の円の中に現在評価待ちのセル点があったら真
private function containsWaitCell(vp:VoronoiPoint):Boolean
{
//trace("containsWaitCell():");
var cell:FortuneCell = _waitCellsHead;
var vt:Number = vp.t;
if (cell && cell.y < vt) do
{
if (vp.contains(cell))
{ //評価待ちセル母点を1つでも円の中に含めば真を返す
return true;
}
var tst:uint = 0;
}while ((cell = cell.next) && cell.y < vt);
//待ちリストの終端に達するか、追加時期がボロノイ点の評価タイミングを超える場合には
return false;
}
// ボロノイ点候補の円の中に現在beachlineを作っているセル点があったら真
private function containsActiveCell(vp:VoronoiPoint):Boolean
{
//trace("containsActiveCell():");
var cell:FortuneCell = _activeCellsHead;
var vt:Number = vp.t;
if (cell) do
{
if (cell is YBoundaryCell)
{ //top境界がbeachlineの一部の場合があるので
continue;
}
if (vp.contains(cell))
{ //アクティブなセル母点を1つでも円の中に含めば真を返す
return true;
}
}while (cell = cell.next);
//リストの終端に達する場合には偽
return false;
}
// ボロノイ点候補が境界の外にあったら真
private function isOutBounds(vp:VoronoiPoint):Boolean
{
//trace("isOuntBounds():");
var vx:Number = vp.x;
var vy:Number = vp.y;
return vx < _leftX || vx > _rightX || vy < _topY || vy > _bottomY;
}
public function get graphicsPaths():Vector.<IGraphicsData> { return _graphicsPaths; }
}
internal class FortuneCell
{
public var x:Number, y:Number;
public var a:Number, b:Number, c:Number;
public var next:FortuneCell;
public var isBeachLine:Boolean;
private var _graphicsPath:GraphicsPath;
private var _leftWallStart:CellWallPt;
private var _rightWallStart:CellWallPt;
public function FortuneCell(position:Point)
{
setPosition(position);
isBeachLine = false;
_graphicsPath = new GraphicsPath();
}
/**
* 引数のPointオブジェクトで母点位置を更新
* @param pt
*/
public function setPosition(position:Point):void
{
x = position.x;
y = position.y;
next = null;
_leftWallStart = null;
_rightWallStart = null;
}
/**
* 母点を焦点とする放物線を指定した準線位置で更新する
* y = ax^2 + 2bx + c の形式で内部的に保持
* @param directrix
*/
public function updateParabola(directrix:Number):void
{
a = - 0.5 / (directrix - y);
b = - x * a;
c = 0.5 * (directrix + y) - x * b;
isBeachLine = false;
}
/**
* 現在の放物線についてxに対するyの値を返す
* @param parabolaX
* @return
*/
public function getParabolaY(parabolaX:Number):Number
{
return (a * parabolaX + 2 * b) * parabolaX + c;
}
/**
* 他のセルの放物線との交点を求める
* @param fc
* @return
*/
public function getIntersectionX(fc:FortuneCell):QuadraticSolution
{
return QuadraticSolution.solve(a - fc.a, b - fc.b, c - fc.c);
}
/**
* セルの左側にボロノイ点を追加する。
* 時計回りなので左側ではy降順に並ぶ。
* @param vp
*/
public function addLeftWall(vp:VoronoiPoint):void
{
//trace(this);
//trace("add to left ", vp);
var newPt :CellWallPt = new CellWallPt(vp.x, vp.y);
var vpy:Number = vp.y;
if (!_leftWallStart || vpy > _leftWallStart.y)
{
newPt.next = _leftWallStart;
_leftWallStart = newPt;
return;
}
var chkPt:CellWallPt = _leftWallStart;
var prevPt:CellWallPt = chkPt;
do
{
if (vpy > chkPt.y)
{
prevPt.next = newPt;
newPt.next = chkPt;
return;
}
prevPt = chkPt;
} while (chkPt = chkPt.next) ;
prevPt.next = newPt;
}
/**
* セルの右側にボロノイ点を追加する。
* 時計回りなので右側ではy昇順に並ぶ。
* @param vp
*/
public function addRightWall(vp:VoronoiPoint):void
{
var newPt :CellWallPt = new CellWallPt(vp.x, vp.y);
var vpy:Number = vp.y;
if (!_rightWallStart || vpy < _rightWallStart.y)
{
newPt.next = _rightWallStart;
_rightWallStart = newPt;
return;
}
var chkPt:CellWallPt = _rightWallStart;
var prevPt:CellWallPt = chkPt;
do
{
if (vpy < chkPt.y)
{
prevPt.next = newPt;
newPt.next = chkPt;
return;
}
prevPt = chkPt;
} while (chkPt = chkPt.next) ;
prevPt.next = newPt;
}
/**
* セルの多角形を描く為のGraphicsPathオブジェクトを返す
*/
public function updateGraphicsPath(curve:Boolean = false):void
{
var pathCmds:Vector.<int>, pathData:Vector.<Number>;
var cmdsL:int, dataL:int;
var cx:Number, cy:Number;
var chkPt:CellWallPt;
if (_leftWallStart || _rightWallStart)
{
if (curve)
{
pathCmds = new Vector.<int>();
pathData = new Vector.<Number>();
_graphicsPath.commands = pathCmds;
_graphicsPath.data = pathData;
cmdsL = 0;
dataL = 0;
pathCmds[cmdsL++] = GraphicsPathCommand.MOVE_TO;
chkPt = _leftWallStart;
if (chkPt)
{
cx = chkPt.x;
cy = chkPt.y;
while (chkPt = chkPt.next)
{
pathData[dataL++] = cx;
pathData[dataL++] = cy;
pathData[dataL++] = 0.5 * (chkPt.x + cx);
pathData[dataL++] = 0.5 * (chkPt.y + cy);
cx = chkPt.x;
cy = chkPt.y;
pathCmds[cmdsL++] = GraphicsPathCommand.CURVE_TO;
}
chkPt = _rightWallStart;
}
else
{
chkPt = _rightWallStart;
cx = chkPt.x;
cy = chkPt.y;
}
if (chkPt) do
{
pathData[dataL++] = cx;
pathData[dataL++] = cy;
pathData[dataL++] = 0.5 * (chkPt.x + cx);
pathData[dataL++] = 0.5 * (chkPt.y + cy);
cx = chkPt.x;
cy = chkPt.y;
pathCmds[cmdsL++] = GraphicsPathCommand.CURVE_TO;
}while (chkPt = chkPt.next);
pathData[dataL++] = cx;
pathData[dataL++] = cy;
pathData[dataL++] = 0.5 * (pathData[0] + cx);
pathData[dataL++] = 0.5 * (pathData[1] + cy);
pathCmds[cmdsL++] = GraphicsPathCommand.CURVE_TO;
pathData.reverse();
pathData.push(pathData[0], pathData[1]);
pathData.reverse();
}
else
{
pathCmds = new Vector.<int>();
pathData = new Vector.<Number>();
_graphicsPath.commands = pathCmds;
_graphicsPath.data = pathData;
cmdsL = 0;
dataL = 0;
pathCmds[cmdsL++] = GraphicsPathCommand.MOVE_TO;
chkPt = _leftWallStart;
if (chkPt) do
{
pathData[dataL++] = chkPt.x;
pathData[dataL++] = chkPt.y;
pathCmds[cmdsL++] = GraphicsPathCommand.LINE_TO;
}while (chkPt = chkPt.next);
chkPt = _rightWallStart;
if (chkPt) do
{
pathData[dataL++] = chkPt.x;
pathData[dataL++] = chkPt.y;
pathCmds[cmdsL++] = GraphicsPathCommand.LINE_TO;
}while (chkPt = chkPt.next);
pathData[dataL++] = pathData[0];
pathData[dataL++] = pathData[1];
//trace(pathCmds.length, pathData.length);
}
}
}
public function getCot(cell:FortuneCell):Number
{
return (cell.x - this.x) / (cell.y - this.y);
}
public function get graphicsPath():GraphicsPath { return _graphicsPath; }
}
internal class CellWallPt
{
public var x:Number;
public var y:Number;
//clockwise next
public var next:CellWallPt;
public function CellWallPt(x:Number, y:Number)
{
this.x = x;
this.y = y;
}
}
internal class VoronoiPoint
{
private var _newCell:FortuneCell, _cellX:FortuneCell, _cellY:FortuneCell;
public var x:Number, y:Number;
public var r2:Number, r:Number;
public var t:Number;
public var next:VoronoiPoint;
/**
* ボロノイ点を作る母点または境界を指定してボロノイ点を求める
* @param newCell 新しく追加されたボロノイ点
* @param cellX 現時点でbeachlineを作るボロノイ点またはx境界
* @param cellY
*/
public function VoronoiPoint(newCell:FortuneCell, cellX:FortuneCell, cellY:FortuneCell)
{
_newCell = newCell;
if (cellX is YBoundaryCell || cellY is XBoundaryCell)
{
_cellX = cellY;
_cellY = cellX;
cellX = _cellX;
cellY = _cellY;
}
else
{
_cellX = cellX;
_cellY = cellY;
}
var isXboundary:Boolean = cellX is XBoundaryCell;
var isYboundary:Boolean = cellY is YBoundaryCell;
// Lx+My=N を連立させて解く
if (!isXboundary)
{
var lX:Number = newCell.x - cellX.x;
var mX:Number = newCell.y - cellX.y;
var nX:Number = 0.5 * (lX * (newCell.x + cellX.x) + mX * (newCell.y + cellX.y));
}
if (!isYboundary)
{
var lY:Number = newCell.x - cellY.x;
var mY:Number = newCell.y - cellY.y;
var nY:Number = 0.5 * (lY * (newCell.x + cellY.x) + mY * (newCell.y + cellY.y));
}
if (isXboundary || isYboundary)
{
x = isXboundary? cellX.x: ((nX - mX * cellY.y) / lX);
y = isYboundary? cellY.y: ((nY - lY * cellX.x) / mY);
}
else
{
var lm:Number = lX * mY - lY * mX;
var nm:Number = nX * mY - nY * mX;
var ml:Number = mX * lY - mY * lX;
var nl:Number = nX * lY - nY * lX;
x = nm / lm;
y = nl / ml;
}
var dx:Number = newCell.x - x;
var dy:Number = newCell.y - y;
r2 = dx * dx + dy * dy;
r = Math.sqrt(r2);
t = y + r;
}
/**
* ある母点を円中に含むかどうか
* @param cell
* @return
*/
public function contains(cell:FortuneCell):Boolean
{
if (cell == _cellX || cell == _cellY || cell == _newCell)
{
return false;
}
var dx:Number = cell.x - x;
if (dx > r)
{
return false;
}
var dy:Number = cell.y - y;
if (dx > r)
{
return false;
}
return r2 > dx * dx + dy * dy;
}
/**
* 新しいボロノイ点として確定し、各セルに追加する
*/
public function fix():void
{
var isXboundary:Boolean = _cellX is XBoundaryCell;
var isYboundary:Boolean = _cellY is YBoundaryCell;
var nx:Number = _newCell.x;
var xx:Number = _cellX.x;
var yx:Number = _cellY.x;
if (isYboundary)
{
if (nx > xx)
{
_newCell.addLeftWall(this);
isXboundary? null: _cellX.addRightWall(this);
}
else
{
_newCell.addRightWall(this);
isXboundary? null: _cellX.addLeftWall(this);
}
}
else if(isXboundary)
{
if (nx > xx)
{
_newCell.addLeftWall(this);
_cellY.addLeftWall(this);
}
else
{
_newCell.addRightWall(this);
_cellY.addRightWall(this);
}
}
else
{
if (nx > xx)
{
_newCell.addLeftWall(this);
if (xx > yx)
{
_cellX.addLeftWall(this);
_cellY.addRightWall(this);
}
else
{
_cellY.addLeftWall(this);
_cellX.addRightWall(this);
}
}
else
{
_cellX.addLeftWall(this);
if (nx > yx)
{
_newCell.addLeftWall(this);
_cellY.addRightWall(this);
}
else
{
_cellY.addLeftWall(this);
_newCell.addRightWall(this);
}
}
}
}
}
internal class QuadraticSolution
{
public var xSmaller:Number;
public var xBigger:Number;
/**
* 2次方程式 ax^2 + 2bx + c = 0 の解を返す
* @param a
* @param b
* @param c
*/
public static function solve(a:Number, b:Number, c:Number):QuadraticSolution
{
if (a == 0)
{
return null;
}
var det:Number = b * b - a * c;
if (det < 0)
{
return null;
}
var ia:Number = 1.0 / a;
var p:Number = -b * ia;
var q:Number = Math.sqrt(det) * (a > 0.0?ia: -ia);
var qs:QuadraticSolution = new QuadraticSolution();
qs.xSmaller = p - q;
qs.xBigger = p + q;
return qs;
}
}
internal class BoundaryCell extends FortuneCell
{
public function BoundaryCell(x:Number = 0, y:Number = 0)
{
super(new Point(x, y));
}
override public function addLeftWall(vp:VoronoiPoint):void { }
override public function addRightWall(vp:VoronoiPoint):void { }
override public function updateParabola(directrix:Number):void { }
}
internal class XBoundaryCell extends BoundaryCell
{
public function XBoundaryCell(x:Number)
{
super(x, 0);
super.a = NaN;
super.b = NaN;
super.c = NaN;
}
override public function getIntersectionX(fc:FortuneCell):QuadraticSolution
{
var qs:QuadraticSolution = new QuadraticSolution();
if (fc.x > x)
{
qs.xSmaller = x;
qs.xBigger = NaN;
}
else
{
qs.xSmaller = NaN;
qs.xBigger = x;
}
return qs;
}
override public function getParabolaY(parabolaX:Number):Number
{
return NaN;
}
override public function getCot(cell:FortuneCell):Number
{
return cell.x > x? Number.POSITIVE_INFINITY: Number.NEGATIVE_INFINITY;
}
}
internal class YBoundaryCell extends BoundaryCell
{
public function YBoundaryCell(y:Number)
{
super(0, y);
super.a = 0;
super.b = 0;
super.c = y;
}
override public function getIntersectionX(fc:FortuneCell):QuadraticSolution
{
return QuadraticSolution.solve(fc.a, fc.b, fc.c - y);
}
override public function getParabolaY(parabolaX:Number):Number
{
return y;
}
override public function getCot(cell:FortuneCell):Number
{
return 0.0;
}
}
internal class BeachLine
{
public var cell:FortuneCell;
public var right:BeachLine;
public var left:BeachLine;
public var rightEndX:Number;
public function BeachLine(cell:FortuneCell = null)
{
this.cell = cell;
}
}