- 积分
- 136114
- 注册时间
- 2014-12-27
- 最后登录
- 2024-3-20
- 在线时间
- 602 小时
- 威望
- 562
- 贡献
- 29
- 金币
- 52618
- 钢镚
- 1422
- 交易凭证
- 1
- 分享
- 0
- 精华
- 33
- 帖子
- 2094
- 主题
- 1742
TA的每日心情 | 擦汗 2018-4-10 15:18 |
---|
签到天数: 447 天 [LV.9]以坛为家II
超级版主
- 威望
- 562
- 贡献
- 29
- 金币
- 52618
- 钢镚
- 1422
|
- /**
- * Sketch of Voronoi
- * I will recommend seeing in "FULL SCREEN" mode.
- * http://alumican.net/#/c/cells
- *
- * based on 超速ボロノイ図 by fumix
- * @see http://wonderfl.net/c/3TKq/
- *
- * 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/
- *
- * @author Yukiya Okuda<alumican.net>
- */
- package
- {
- import com.flashdynamix.utils.SWFProfiler;
- import flash.display.Graphics;
- import flash.display.Shape;
- import flash.display.Sprite;
- import flash.display.StageAlign;
- import flash.display.StageQuality;
- import flash.display.StageScaleMode;
- import flash.events.Event;
-
- public class Main extends Sprite
- {
- private const N:int = 700;
-
- private const PI:Number = Math.PI;
- private const PI2:Number = PI * 2;
- private const TO_DEGREE:Number = 180 / PI;
- private const TO_RADIAN:Number = PI / 180;
-
- private var _fortune:Fortune;
- private var _points:Vector.<Number2>;
- private var _pointCount:int;
- private var _first:Number2;
- private var _oldMouseX:Number;
- private var _oldMouseY:Number;
- private var _background:Shape;
- private var _canvas:Shape;
- private var _range:Number;
-
- public function Main():void
- {
- Wonderfl.disable_capture();
- addEventListener(Event.ADDED_TO_STAGE, _init);
- }
-
- private function _init(e:Event):void
- {
- removeEventListener(Event.ADDED_TO_STAGE, _init);
-
- stage.align = StageAlign.TOP_LEFT;
- stage.scaleMode = StageScaleMode.NO_SCALE;
- stage.quality = StageQuality.MEDIUM;
- stage.frameRate = 60;
-
- var sw:Number = stage.stageWidth,
- sh:Number = stage.stageHeight;
-
- _fortune = new Fortune();
-
- _background = addChild( new Shape() ) as Shape;
- _background.graphics.beginFill(0x0);
- _background.graphics.drawRect(0, 0, sw, sh);
- _background.graphics.endFill();
-
- _canvas = addChild( new Shape() ) as Shape;
-
- _points = new Vector.<Number2>(N);
- var p:Number2;
- var old:Number2;
- for (var i:int = 0; i < N; ++i)
- {
- _points[i] = p = new Number2();
-
- if (_first == null)
- {
- old = _first = p;
- }
- else
- {
- old.next = p;
- old = p;
- }
- }
-
- _oldMouseX = mouseX;
- _oldMouseY = mouseY;
-
- addEventListener(Event.ENTER_FRAME, _update);
- stage.addEventListener(Event.RESIZE, _resize);
- _resize(null);
-
- SWFProfiler.init(this);
- }
-
- private function _resize(e:Event):void
- {
- var sw:Number = stage.stageWidth,
- sh:Number = stage.stageHeight;
-
- _background.width = sw;
- _background.height = sh;
- _range = 100 * (Math.min(sw, sh) / 465);
-
- var p:Number2 = _first;
- do
- {
- var px:Number = p.x = Math.random() * sw;
- var py:Number = p.y = Math.random() * sh;
- var angle:Number = Math.atan2(py - sh * 0.5, px - sw * 0.5);
- p.defaultVx = p.vx = 0.3 * Math.cos(angle);
- p.defaultVy = p.vy = 0.3 * Math.sin(angle);
- }
- while (p = p.next);
- }
-
- private function _update(e:Event):void
- {
- _interaction();
- _draw();
- }
-
- private function _interaction():void
- {
- var sw:Number = stage.stageWidth,
- sh:Number = stage.stageHeight,
- cx:Number = sw * 0.5,
- cy:Number = sh * 0.5,
- mx:Number = mouseX,
- my:Number = mouseY,
- dx:Number,
- dy:Number,
- dist2:Number,
- px:Number,
- py:Number,
- mvx:Number = mx - _oldMouseX,
- mvy:Number = my - _oldMouseY,
- ms2:Number = Math.sqrt(mvx * mvx + mvy * mvy),
- angle:Number,
- power:Number,
- mag:Number = _range * 0.5;
-
- var p:Number2 = _first;
- do
- {
- px = p.x;
- py = p.y;
-
- if (px < 0 || px > sw || py < 0 || py > sh)
- {
- angle = Math.random() * PI2;
-
- p.x = cx + (Math.random() - 0.5) * 5;
- p.y = cy + (Math.random() - 0.5) * 5;
- p.vx = (Math.random() - 0.5) * 1 * Math.cos(angle);
- p.vy = (Math.random() - 0.5) * 1 * Math.sin(angle);
- p.defaultVx = p.vx;
- p.defaultVy = p.vy;
- }
- else
- {
- dx = px - mx;
- dy = py - my;
-
- dist2 = dx * dx + dy * dy;
- angle = Math.atan2(dy, dx);
-
- power = mag / dist2 * ms2;
- p.vx += power * Math.cos(angle);
- p.vy += power * Math.sin(angle);
- }
-
- p.defaultVx *= 1.005;
- p.defaultVy *= 1.005;
-
- p.vx += (p.defaultVx - p.vx) * 0.05;
- p.vy += (p.defaultVy - p.vy) * 0.05;
-
- p.x += p.vx;
- p.y += p.vy;
- }
- while (p = p.next);
-
- _fortune.points = _points;
-
- _oldMouseX = mx;
- _oldMouseY = my;
- }
-
- private function _draw():void
- {
- var segments:Vector.<Number2> = _fortune.compute(),
- g:Graphics = _canvas.graphics,
- p:Number2 = _first,
- i:int,
- n:int = segments.length,
- st:Number2,
- ed:Number2,
- dx:Number,
- dy:Number,
- dist2:Number,
- thickness:Number,
- range:Number = _range,
- mx:Number = mouseX,
- my:Number = mouseY,
- stX:Number,
- stY:Number,
- edX:Number,
- edY:Number;
-
- g.clear();
- for (i = 0; i < n; i += 2)
- {
- st = segments[i ];
- ed = segments[i + 1];
- stX = st.x;
- stY = st.y;
- edX = ed.x;
- edY = ed.y;
-
- dx = (edX + stX) * 0.5 - mx;
- dy = (edY + stY) * 0.5 - my;
- dist2 = Math.sqrt(dx * dx + dy * dy);
- thickness = (dist2 < range) ? (10 * (range - dist2) / range) : 0;
-
- g.lineStyle(thickness, 0x333333);
- g.moveTo(stX, stY);
- g.lineTo(edX, edY);
- }
-
- g.lineStyle(0, 0xffffff, 0.8);
- do
- {
- g.drawCircle(p.x, p.y, 1);
- }
- while (p = p.next);
- }
- }
- }
- //package
- //{
- /*public*/ class Number2
- {
- public var x:Number;
- public var y:Number;
- public var vx:Number;
- public var vy:Number;
- public var next:Number2;
- public var defaultVx:Number;
- public var defaultVy:Number;
-
- public function Number2(x:Number = 0, y:Number = 0, vx:Number = 0, vy:Number = 0):void
- {
- this.x = x;
- this.y = y;
- this.defaultVx = this.vx = vx;
- this.defaultVy = this.vy = vy;
- }
- }
- //}
- //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;
- }
- }
- //}
复制代码
本文来自:http://wonderfl.net/c/iNy0
|
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
|