/**
* Copyright Aquioux ( http://wonderfl.net/user/Aquioux )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/xKnl
*/
/**
* Voronoi Letter
* Usase : key down "Alphabet" or "Number" or "Number of tenkey".
* if no reaction, click stage and key down.
* 使い方 : アルファベットキー、数字キー、テンキーの数字キー、いずれかを押してください。
* 反応しないときは、一度ステージをクリックしてからキーを押してください。
*
* 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://wonderfl.net/c/3TKq
* @see http://wonderfl.net/c/iNy0
*
* 解説 : http://aquioux.blog48.fc2.com/blog-entry-735.html
*
* @author Aquioux(Yoshida, Akio)
*/
package {
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Graphics;
import flash.display.GraphicsEndFill;
import flash.display.GraphicsPath;
import flash.display.GraphicsPathCommand;
import flash.display.GraphicsSolidFill;
import flash.display.GraphicsStroke;
import flash.display.IGraphicsData;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.KeyboardEvent;
import flash.geom.Matrix;
import flash.geom.Point;
import flash.geom.Rectangle;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFormat;
[SWF(width = "465", height = "465", frameRate = "30", backgroundColor = "#FFFFFF")]
public class Main extends Sprite {
// 母点生成用定数
private const FONT_SIZE:uint = 48;
private const INTERVAL_X:Number = 9.5;
private const INTERVAL_Y:Number = 9.5;
private const W:Number = stage.stageWidth / INTERVAL_X;
private const H:Number = stage.stageHeight / INTERVAL_Y;
private const CX:Number = stage.stageWidth / 2;
private const CY:Number = stage.stageHeight / 2;
// 母点動作用定数
private const SPRING:Number = 0.05; // バネ係数
private const FRICTION:Number = 0.79; // 摩擦係数
private const PI2:Number = Math.PI * 2;
private const FREQ:uint = 8;
private const FREQ2:uint = FREQ * 2 + 1;
private const OFFSET:uint = 3;
private const OFFSET2:uint = OFFSET * 2 + 1;
// 文字を転写する BitmapData
private var bmd_:BitmapData;
// 母点格納
private var generators_:Vector.<Number2>;
// ボロノイ図作図クラス
private var fortune_:Fortune;
// キャンバス
private var canvas_:Sprite;
// GraphicsData
private var graphicsData:Vector.<IGraphicsData>;
private var path:GraphicsPath;
// コンストラクタ
public function Main() {
// ボロノイ辺描画用 GraphicsData 生成
createGraphicsData();
// キャンバス生成
canvas_ = new Sprite();
addChild(canvas_);
// ボロノイ辺作図クラス生成
fortune_ = new Fortune();
// 母点生成
createGenerators("A");
addEventListener(Event.ENTER_FRAME, enterFrameHandler);
stage.addEventListener(KeyboardEvent.KEY_DOWN, keyDownHandler);
}
// 母点生成
private function createGenerators(letter:String):void {
createGenerator(letter);
fortune_.points = generators_;
}
private function createGenerator(letter:String):void {
const TRANSPARENT:uint = 0x00000000;
const COLOR:uint = 0xFF000000;
// TextField の生成
var tFormat:TextFormat = new TextFormat("_sans", FONT_SIZE, COLOR);
var tField:TextField = new TextField();
tField.defaultTextFormat = tFormat;
tField.text = letter;
tField.autoSize = TextFieldAutoSize.LEFT;
// TextField を BitmapData へ転写
var bmd1:BitmapData = new BitmapData(tField.textWidth, tField.textHeight, true, TRANSPARENT);
bmd1.draw(tField, new Matrix(1, 0, 0, 1, -2, -2));
// 上記 BitmapData から 文字部分のみを抜き出す
var rect:Rectangle = bmd1.getColorBoundsRect(0xFF000000, TRANSPARENT, false);
// 文字部分のサイズの BitmapData へ転写
var bmd2:BitmapData = new BitmapData(rect.width, rect.height, true, TRANSPARENT);
bmd2.draw(bmd1, new Matrix(1, 0, 0, 1, -rect.x, -rect.y));
// 上記 BitmapData をスキャン対象サイズの BitmapData へ転写
bmd_ = new BitmapData(W, H, true, TRANSPARENT);
bmd_.draw(bmd2, new Matrix(1, 0, 0, 1, (W - bmd2.width) / 2, (H - bmd2.height) / 2));
// 使用済みの BitmapData を解放
bmd1.dispose();
bmd2.dispose();
// BitmapData をスキャン
var flg:Boolean = false;
generators_ = new Vector.<Number2>();
for (var y:int = 0; y < H; y++) {
for (var x:int = 0; x < W; x++) {
var color:uint = bmd_.getPixel32(x, y);
var alpha:uint = (color >> 24) & 0xFF;
if (alpha > 0x79) {
flg = true;
} else {
if (Math.random() < 0.01) flg = true;
}
if (flg) {
var generator:Number2 = new Number2();
generator.localX = x * INTERVAL_X + int(Math.random() * OFFSET2) - OFFSET;
generator.localY = y * INTERVAL_Y + int(Math.random() * OFFSET2) - OFFSET;
var radian:Number = Math.random() * PI2;
generator.x = Math.cos(radian) * 300 + CX;
generator.y = Math.sin(radian) * 300 + CY;
generators_.push(generator);
flg = false;
}
}
}
// 使用済みの BitmapData を解放
bmd_.dispose();
}
// ボロノイ辺描画用 GraphicsData 生成
private function createGraphicsData():void {
// 線の定義
var stroke:GraphicsStroke = new GraphicsStroke();
stroke.thickness = 0;
stroke.fill = new GraphicsSolidFill(0x000000);
// パスの定義
path = new GraphicsPath(null, null);
// 描画データをパッケージング
graphicsData = new Vector.<IGraphicsData>();
graphicsData.push(stroke);
graphicsData.push(path);
graphicsData.push(new GraphicsEndFill());
}
private function enterFrameHandler(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;
var g:Graphics = canvas_.graphics;
g.clear();
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 diff:Number = Math.floor(Math.random() * FREQ2) - FREQ;
var radian:Number = Math.random() * PI2;
var dx:Number = localX + Math.cos(radian) * diff;
var dy:Number = localY + Math.sin(radian) * diff;
vx += (dx - x) * SPRING;
vy += (dy - y) * SPRING;
vx *= FRICTION;
vy *= FRICTION;
x += vx;
y += vy;
generator.x = x;
generator.y = y;
generator.vx = vx;
generator.vy = vy;
}
private function keyDownHandler(e:KeyboardEvent):void {
var flg:Boolean = false;
var keyCode:int = e.keyCode;
if ((keyCode >= 48) && (keyCode <= 57)) flg = true; // 数字キー（キーボード）
if ((keyCode >= 96) && (keyCode <= 105)) flg = true; // 数字キー（テンキー）
if ((keyCode >= 65) && (keyCode <= 91)) flg = true; // アルファベットキー（キーボード）
if (flg) createGenerators(String.fromCharCode(e.charCode));
}
}
}
//package {
/*public*/ class Number2 {
// 既定座標
public function get localX():Number { return _localX; }
public function set localX(value:Number):void { _localX = value; }
private var _localX:Number;
public function get localY():Number { return _localY; }
public function set localY(value:Number):void { _localY = value; }
private var _localY:Number;
// 現在座標
public function get x():Number { return _x; }
public function set x(value:Number):void { _x = value; }
private var _x:Number;
public function get y():Number { return _y; }
public function set y(value:Number):void { _y = value; }
private var _y:Number;
// 速度
public function get vx():Number { return _vx; }
public function set vx(value:Number):void { _vx = value; }
private var _vx:Number = 0;
public function get vy():Number { return _vy; }
public function set vy(value:Number):void { _vy = value; }
private var _vy:Number = 0;
public function Number2() {
}
}
//}
//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 {
/*
* 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;
}
}
//}