/**
* Copyright Aquioux ( http://wonderfl.net/user/Aquioux )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/6d2m
*/
/*
Bubble Harp のパチモン (fake Bubble Harp)
[Usase] Draw : Drag stage.
[Usase] Reset :"C" key down.
Scott Snibbe /@snibbe [Profile, iPhone, iPad, oF] - Dynamic Systems Series | CreativeApplications.Net
@see http://www.creativeapplications.net/iphone/scott-snibbe-profile-iphone-ipad-of/
Fortune's algorithm - Wikipedia, the free encyclopedia
@see http://en.wikipedia.org/wiki/Fortune's_algorithm
Controul > Speedy Voronoi diagrams in as3/flash
@see http://blog.controul.com/2009/05/speedy-voronoi-diagrams-in-as3flash/
解説：@see http://aquioux.net/blog/?p=609
@author Aquioux(Yoshida, Akio)
*/
package {
import flash.display.Graphics;
import flash.display.GraphicsPath;
import flash.display.GraphicsPathCommand;
import flash.display.IGraphicsData;
import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.KeyboardEvent;
import flash.events.MouseEvent;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFormat;
import frocessing.color.ColorHSV;
[SWF(width = "465", height = "465", frameRate = "30", backgroundColor = "#000000")]
public class Main extends Sprite {
// 母点動作用定数
private const SPRING:Number = 0.05; // バネ係数
private const FRICTION:Number = 0.9; // 摩擦係数
private const PI2:Number = Math.PI * 2; // 360度分のラジアン
private const FREQ:uint = 1; // 母点のゆらぎ
private const FREQ2:uint = FREQ * 2; // 上記の2倍
// 各種フラグ
private var isDown_:Boolean = false; // 母点生成判定
private var isFirst_:Boolean = true; // 処理が初回か否か
// 母点格納
private var generators_:Vector.<Number2>;
// ボロノイ図作図クラス
private var fortune_:Fortune;
// キャンバス
private var canvas_:Shape;
// GraphicsData
private var graphicsData:Vector.<IGraphicsData>;
private var path:GraphicsPath;
// 表示色用
private var hsv_:ColorHSV;
private var tField:TextField;
// コンストラクタ
public function Main() {
setup();
// 取説
tField = new TextField();
tField.defaultTextFormat = new TextFormat(null, null, 0xFFFFFF);
tField.autoSize = TextFieldAutoSize.LEFT;
tField.text = "ステージドラッグで描画。\n\"C\" キーダウンでリセット。\n\nDraw : Drag stage.\nReset : \"C\" key down.";
tField.x = (stage.stageWidth - tField.width) / 2;
tField.y = (stage.stageHeight - tField.height) / 2;
addChild(tField);
stage.addEventListener(MouseEvent.MOUSE_DOWN, firstDownHandler);
}
// 起動後、最初のマウスダウン
private function firstDownHandler(e:MouseEvent):void {
stage.removeEventListener(MouseEvent.MOUSE_DOWN, arguments.callee);
removeChild(tField);
tField = null;
downHandler(null);
stage.addEventListener(MouseEvent.MOUSE_DOWN, downHandler);
stage.addEventListener(MouseEvent.MOUSE_UP, upHandler);
stage.addEventListener(MouseEvent.MOUSE_MOVE, moveHandler);
stage.addEventListener(MouseEvent.CLICK, clickHandler);
stage.addEventListener(KeyboardEvent.KEY_DOWN, keyHandler);
}
private function setup():void{
// ボロノイ辺描画用 GraphicsData 生成
path = new GraphicsPath();
graphicsData = new Vector.<IGraphicsData>();
graphicsData.push(path);
// 表示色用
hsv_ = new ColorHSV(0, 0.5);
// 下地生成
var base:Shape = new Shape();
addChild(base);
var g:Graphics = base.graphics;
g.beginFill(0x0);
g.drawRect(0, 0, stage.stageWidth, stage.stageHeight);
g.endFill();
// キャンバス生成
canvas_ = new Shape();
addChild(canvas_);
// ボロノイ辺作図クラス生成
fortune_ = new Fortune();
// 母点格納 Vector 生成
generators_ = new Vector.<Number2>();
}
// マウスハンドラ
private function downHandler(e:MouseEvent):void {
isDown_ = true;
if (isFirst_) {
createGenerator();
addEventListener(Event.ENTER_FRAME, update);
isFirst_ = false;
}
}
private function upHandler(e:MouseEvent):void {
isDown_ = false;
}
private function moveHandler(e:MouseEvent):void {
if (isDown_) createGenerator();
}
private function clickHandler(e:MouseEvent):void {
isDown_ = true;
moveHandler(e);
isDown_ = false;
}
// 母点の生成
private function createGenerator():void {
var generator:Number2 = new Number2();
generator.x = generator.localX = mouseX;
generator.y = generator.localY = mouseY;
generators_.push(generator);
fortune_.points = generators_;
}
// アップデート
private function update(event:Event):void {
// 母点位置更新
var n:uint = generators_.length;
for (var i:int = 0; i < n; i++) {
generatorUpdate(generators_[i]);
}
// ボロノイ点更新
var points:Vector.<Number2> = fortune_.compute();
// ボロノイ辺更新
var start:Number2; // ボロノイ辺の起点
var end:Number2; // ボロノイ辺の終点
var commands:Vector.<int> = new Vector.<int>();
var data:Vector.<Number> = new Vector.<Number>();
n = points.length;
for (i = 0; i < n; i += 2) {
start = points[i];
end = points[i + 1];
commands.push(GraphicsPathCommand.MOVE_TO, GraphicsPathCommand.LINE_TO);
data.push(start.x, start.y, end.x, end.y);
}
path.commands = commands;
path.data = data;
// 表示色の計算
hsv_.h += 0.5;
var color:uint = hsv_.value;
// 描画開始
var g:Graphics = canvas_.graphics;
g.clear();
g.lineStyle(2, color); // 母点は線を太く
// 母点の描画
n = generators_.length;
for (i = 0; i < n; i++) {
var generator:Number2 = generators_[i];
g.drawCircle(generator.x, generator.y, 1);
}
// ボロノイ辺の描画
g.lineStyle(0, color); // 辺は線を細く
g.drawGraphicsData(graphicsData);
}
// 母点の位置更新
private function generatorUpdate(generator:Number2):void {
// 変数の取り出し
var localX:Number = generator.localX;
var localY:Number = generator.localY;
var vx:Number = generator.vx;
var vy:Number = generator.vy;
var x:Number = generator.x;
var y:Number = generator.y;
// ゆらいだ到達値の計算
var len:Number = Math.floor(Math.random() * FREQ2) - FREQ;
var angle:Number = Math.random() * PI2;
var reachX:Number = localX + Math.cos(angle) * len;
var reachY:Number = localY + Math.sin(angle) * len;
// 変数の更新
vx += (reachX - x) * SPRING;
vy += (reachY - y) * SPRING;
vx *= FRICTION;
vy *= FRICTION;
x += vx;
y += vy;
// 変数の書き戻し
generator.x = x;
generator.y = y;
generator.vx = vx;
generator.vy = vy;
}
// リセット
private function keyHandler(e:KeyboardEvent):void {
if (e.keyCode == 67) { // "C" キー
canvas_.graphics.clear();
removeEventListener(Event.ENTER_FRAME, update);
isFirst_ = true;
generators_ = null;
generators_ = new Vector.<Number2>();
}
}
}
}
//package {
/*
* An implementation of Steve Fortune's algorithm for computing voronoi diagrams.
* @author Matt Brubeck
*
* Modifications and optimisations:
* ** Data structures are adapted to what's available to as3.
* ** The beachline intersection lookup is optimised,
* intersecting begins only near the probable intersection.
* ** Functions are massively inlined.
*
* Todo list:
* ** Provide for bounding box intersection,
* ** Inline the 'intersection' method.
* ** Design a good datastructure for the solution, which would
* ideally contain enough neighbourhood info for region rendering,
* extrusion and intrusion of edges and pathfinding.
*
* Original c++ code
* http://www.cs.hmc.edu/~mbrubeck/voronoi.html
*/
/*public*/ class Fortune {
/////////
/////////
///////// Datastructures.
// Points are provided as a vector, which is sorted by x (increasing) before the sweep.
public var points : Vector.<Number2>;
// Bounding box.
private var x0 : Number;
// private var x1 : Number;
// private var y0 : Number;
// private var y1 : Number;
// Root of the frontline and next arc to be removed.
private var root : Arc;
private var next : Arc;
// Reusable objects and pools.
private var o : Number2 = new Number2;
private static var arcPoolD : Arc;
////////
////////
//////// API.
/**
* Computes the Voronoi decomposition of the plane.
* @return A vector or vertices in pairs, describing segments ready for drawing.
*/
public function compute () : Vector.<Number2>
{
//
//
// Clear the output.
var out : Vector.<Number2> = new Vector.<Number2>,
len : int = 0;
//
//
// Clear the state.
root = null;
next = null;
//
//
// Read the pools.
var key : * ,
arcPool : Arc = arcPoolD;
//
//
// Vars:
var i : int,
j : int,
w : Number,
x : Number,
a : Arc,
b : Arc,
// s : Seg,
z : Number2,
p : Number2 = points [ 0 ],
points : Vector.<Number2> = points,
n : int = points.length,
// Circle events check inlined.
circle : Boolean,
eventX : Number,
c : Arc,
d : Arc,
aa : Number2,
bb : Number2,
cc : Number2,
A : Number,
B : Number,
C : Number,
D : Number,
E : Number,
F : Number,
G : Number;
//
// y0 = p.y;
// y1 = p.y;
//
//
// Sort points by x coord, compute the bounding box.
///// Currently insertion sort. Quicksort?
w = points [ 0 ].x;
for ( i = 1; i < n; i ++ )
{
p = points [ i ];
// Keep track of the bounding box.
// if ( p.y < y0 )
// y0 = p.y;
// else if ( p.y > y1 )
// y1 = p.y;
// Insertion sort.
x = p.x;
if ( x < w )
{
j = i;
while ( ( j > 0 ) && ( points [ int ( j - 1 ) ].x > x ) )
{
points [ j ] = points [ int ( j - 1 ) ];
j--;
}
points [ j ] = p;
}
else
w = x;
}
// Get x bounds.
x0 = points [ 0 ].x;
// x1 = points [ n - 1 ].x;
// Add margins to the bounding box.
/*
var dx : Number = (x1 - x0 + 1) / 5.0,
dy : Number = dy = (y1 - y0 + 1) / 5.0;
x0 -= dx;
x1 += dx;
y0 -= dy;
y1 += dy;
// trace ( x0, x1, y0, y1 );
//*/
//
//
// Process.
i = 0;
p = points [ 0 ];
x = p.x;
for ( ;; )
{
//
// Check circle events. /////////////////////////
if ( a )
{
// Check for arc a.
circle = false;
if ( a.prev && a.next )
{
aa = a.prev.p,
bb = a.p,
cc = a.next.p;
// Algorithm from O'Rourke 2ed p. 189.
A = bb.x - aa.x,
B = bb.y - aa.y,
C = cc.x - aa.x,
D = cc.y - aa.y;
// Check that bc is a "right turn" from ab.
if ( A * D - C * B <= 0 )
{
E = A * ( aa.x + bb.x ) + B * ( aa.y + bb.y ),
F = C * ( aa.x + cc.x ) + D * ( aa.y + cc.y ),
G = 2 * ( A * ( cc.y - bb.y ) - B * ( cc.x - bb.x ) );
// Check for colinearity.
// if ( G > 0.000000001 || G < -0.000000001 )
if ( G )
{
// Point o is the center of the circle.
o.x = ( D * E - B * F ) / G;
o.y = ( A * F - C * E ) / G;
// o.x plus radius equals max x coordinate.
A = aa.x - o.x;
B = aa.y - o.y;
eventX = o.x + Math.sqrt ( A * A + B * B );
if ( eventX >= w )
circle = true;
}
}
}
// Remove from queue.
if ( a.right )
a.right.left = a.left;
if ( a.left )
a.left.right = a.right;
if ( a == next )
next = a.right;
// Record event.
if ( circle )
{
a.endX = eventX;
if ( a.endP )
{
a.endP.x = o.x;
a.endP.y = o.y;
}
else
{
a.endP = o;
o = new Number2;
}
d = next;
if ( !d )
{
next = a;
}
else for ( ;; )
{
if ( d.endX >= eventX )
{
a.left = d.left;
if ( d.left )
d.left.right = a;
if ( next == d )
next = a;
a.right = d;
d.left = a;
break;
}
if ( !d.right )
{
d.right = a;
a.left = d;
a.right = null;
break;
}
d = d.right;
}
}
else
{
a.endX = NaN;
a.endP = null;
a.left = null;
a.right = null;
}
// Push next arc to check.
if ( b )
{
a = b;
b = null;
continue;
}
if ( c )
{
a = c;
c = null;
continue;
}
a = null;
}
//////////////////////////////////////////////////
//
if ( next && next.endX <= x )
{
//
// Handle next circle event.
// Get the next event from the queue. ///////////
a = next;
next = a.right;
if ( next )
next.left = null;
a.right = null;
//DEBUG*/ Debug.frontRemove ( a, root );
// Start a new edge.
// s = new Seg;
// s.start = a.endP;
// Remove the associated arc from the front.
if ( a.prev )
{
a.prev.next = a.next;
// a.prev.s1 = s;
a.prev.v1 = a.endP;
}
if ( a.next )
{
a.next.prev = a.prev;
// a.next.s0 = s;
a.next.v0 = a.endP;
}
// Finish the edges before and after a.
/*
if ( a.s0 && !a.s0.done )
{
a.s0.done = true;
// a.s0.end = a.endP;
out [ len ++ ] = a.s0.start;
out [ len ++ ] = a.endP;
}
if ( a.s1 && !a.s1.done )
{
a.s1.done = true;
// a.s1.end = a.endP;
out [ len ++ ] = a.s1.start;
out [ len ++ ] = a.endP;
}
*/
if ( a.v0 )
{
out [ len ++ ] = a.v0;
a.v0 = null;
out [ len ++ ] = a.endP;
}
if ( a.v1 )
{
out [ len ++ ] = a.v1;
a.v1 = null;
out [ len ++ ] = a.endP;
}
// Keep a ref for collection.
d = a;
// Recheck circle events on either side of p:
w = a.endX;
if ( a.prev )
{
b = a.prev;
a = a.next;
}
else
{
a = a.next;
b = null;
}
c = null;
// Collect.
d.v0 = null;
d.v1 = null;
d.p = null;
d.prev = null;
d.endX = NaN;
d.endP = null;
d.next = arcPool;
arcPool = d;
//////////////////////////////////////////////////
//
}
else
{
if ( !p )
break;
//
// Handle next site event. //////////////////////
if ( !root ) {
// root = new Arc;
if ( arcPool )
{
root = arcPool;
arcPool = arcPool.next;
root.next = null;
}
else
root = new Arc;
root.p = p;
//DEBUG*/ Debug.frontInsert ( root, root );
}
else
{
z = new Number2;
// Find the first arc with a point below p,
// and start searching for the intersection around it.
a = root.next;
if ( a )
{
while ( a.next )
{
a = a.next;
if ( a.p.y >= p.y )
break;
}
// Find the intersecting curve.
intersection ( a.prev.p, a.p, p.x, z );
if ( z.y <= p.y )
{
// Search for the intersection to the south of i.
while ( a.next )
{
a = a.next;
intersection ( a.prev.p, a.p, p.x, z );
if ( z.y >= p.y )
{
a = a.prev;
break;
}
}
}
else
{
// Search for the intersection above i.
a = a.prev;
while ( a.prev )
{
a = a.prev;
intersection ( a.p, a.next.p, p.x, z );
if ( z.y <= p.y )
{
a = a.next;
break;
}
}
}
}
else
a = root;
// New parabola will intersect arc a. Duplicate a.
if ( a.next )
{
// b = new Arc;
if ( arcPool )
{
b = arcPool;
arcPool = arcPool.next;
b.next = null;
}
else
b = new Arc;
b.p = a.p;
b.prev = a;
b.next = a.next;
a.next.prev = b;
a.next = b;
}
else
{
// b = new Arc;
if ( arcPool )
{
b = arcPool;
arcPool = arcPool.next;
b.next = null;
}
else
b = new Arc;
b.p = a.p;
b.prev = a;
a.next = b;
}
// a.next.s1 = a.s1;
a.next.v1 = a.v1;
// Find the point of intersection.
z.y = p.y;
z.x = ( a.p.x * a.p.x + ( a.p.y - p.y ) * ( a.p.y - p.y ) - p.x * p.x )
/ ( 2 * a.p.x - 2 * p.x );
// Add p between i and i->next.
// b = new Arc;
if ( arcPool )
{
b = arcPool;
arcPool = arcPool.next;
b.next = null;
}
else
b = new Arc;
b.p = p;
b.prev = a;
b.next = a.next;
a.next.prev = b;
a.next = b;
a = a.next; // Now a points to the new arc.
// Add new half-edges connected to i's endpoints.
/*
s = new Seg;
s.start = z;
a.prev.s1 = a.s0 = s;
s = new Seg;
s.start = z;
a.next.s0 = a.s1 = s;
*/
a.prev.v1 = z;
a.next.v0 = z;
a.v0 = z;
a.v1 = z;
// Check for new circle events around the new arc:
b = a.next;
a = a.prev;
c = null;
w = p.x;
//DEBUG*/ Debug.frontInsert ( a, root );
}
//////////////////////////////////////////////////
//
i ++;
if ( i >= n )
{
p = null;
x = Number.MAX_VALUE;
}
else
{
p = points [ i ];
x = p.x;
}
}
}
//*/
/*
// Clean up dangling edges.
// Advance the sweep line so no parabolas can cross the bounding box.
x = x1;
x = x1 + ( x1 - x0 ) + ( y1 - y0 );
x *= 2;
// Extend each remaining segment to the new parabola intersections.
var arc : Arc = root;
for ( ;; )
{
if ( arc.s1 )
arc.s1.finish ( intersection ( arc.p, arc.next.p, x, new Number2 ) );
arc = arc.next;
if ( !arc.next )
break;
}
//*/
//
//
// Store the pools.
arcPoolD = arcPool;
//
//
// Return the result ready for drawing.
return out;
}
/**
* Where do two parabolas intersect?
* @param p0 A Number2 object describing the site for the first parabola.
* @param p1 A Number2 object describing the site for the second parabola.
* @param l The location of the sweep line.
* @param res A Number2 object in which to store the intersection.
* @return The point of intersection.
*/
public function intersection ( p0 : Number2, p1 : Number2, l : Number, res : Number2 ) : Number2
{
var p : Number2 = p0,
ll : Number = l * l;
if ( p0.x == p1.x )
res.y = ( p0.y + p1.y ) / 2;
else if ( p1.x == l )
res.y = p1.y;
else if ( p0.x == l )
{
res.y = p0.y;
p = p1;
}
else
{
// Use the quadratic formula.
var z0 : Number = 0.5 / ( p0.x - l ); // 1 / ( 2*(p0.x - l) )
var z1 : Number = 0.5 / ( p1.x - l ); // 1 / ( 2*(p1.x - l) )
var a : Number = z0 - z1;
var b : Number = -2 * ( p0.y * z0 - p1.y * z1 );
var c : Number = ( p0.y * p0.y + p0.x * p0.x - ll ) * z0
- ( p1.y * p1.y + p1.x * p1.x - ll ) * z1;
res.y = ( - b - Math.sqrt ( b * b - 4 * a * c ) ) / ( 2 * a );
}
// Plug back into one of the parabola equations.
res.x = ( p.x * p.x + ( p.y - res.y ) * ( p.y - res.y ) - ll )
/ ( 2 * p.x - 2 * l );
return res;
}
}
//}
//package {
/*public*/ class Arc {
public var p : Number2;
public var next : Arc;
public var prev : Arc;
// public var s0 : Seg;
// public var s1 : Seg;
public var v0 : Number2;
public var v1 : Number2;
// Circle event data :
public var left : Arc;
public var right : Arc;
public var endX : Number;
public var endP : Number2;
}
//}
//package {
/*public*/ class Number2 {
// 既定座標
public function get localX():Number { return _localX; }
public function set localX(value:Number):void { _localX = value; }
private var _localX:Number = 0.0;
public function get localY():Number { return _localY; }
public function set localY(value:Number):void { _localY = value; }
private var _localY:Number = 0.0;
// 現在座標
public function get x():Number { return _x; }
public function set x(value:Number):void { _x = value; }
private var _x:Number = 0.0;
public function get y():Number { return _y; }
public function set y(value:Number):void { _y = value; }
private var _y:Number = 0.0;
// 速度
public function get vx():Number { return _vx; }
public function set vx(value:Number):void { _vx = value; }
private var _vx:Number = 0.0;
public function get vy():Number { return _vy; }
public function set vy(value:Number):void { _vy = value; }
private var _vy:Number = 0.0;
public function Number2() {
}
}
//}