Attempt to replicate:
http://lab.polygonal.de/wp-content/assets/110722/flash.html
The problem is my algorithm crosses lines and i can't figure out any way to do so without the polygonal library.
Any help?
Can you tell me how this study area is called ? Maybe some sort of book that explains / teaches the basic terminology of patterns and algorithms. Thanks for the "Delaunay Triangulation"
/**
* Copyright WLAD ( http://wonderfl.net/user/WLAD )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/32wl
*/
package
{
import flash.display.Sprite;
public class NodeTest extends Sprite
{
private var map:NodeMap;
public function NodeTest()
{
map = new NodeMap();
addChild(map);
stage.addEventListener('click', onClick);
}
private function onClick(e:*= null):void
{
var n:Node = new Node();
map.addNode( mouseX, mouseY );
}
}
}
import flash.display.Sprite;
import flash.geom.Point;
class NodeMap extends Sprite
{
static public const RADIUS:int = 30;
public var nodes:Vector.<Node>;
public function NodeMap()
{
nodes = new Vector.<Node>();
}
public function addNode( x:Number, y:Number ):void
{
var n:Node = new Node( );
n.x = x; n.y = y;
var contactNodes:Vector.<Node> = nearestNodes( n, 3 );
// Check if the point ( x , y ) is too close to one of the nodes
if ( contactNodes == null ) return;
// If there is more then 2 nodes in list
if ( contactNodes.length == 3 )
{
// Check if the node is in the middle
if ( isInsideTriangle
(
contactNodes[0].position,
contactNodes[1].position,
contactNodes[2].position,
n.position
))
// If true set the surrounding nodes as connected
n.connectMany( contactNodes );
// Else connect the closest two
else n.connectMany( new <Node>[ contactNodes[0], contactNodes[1] ] );
}
else
{
// If there is less then 3 nodes in the list, it's safe to connect them all
if( nodes.length == 2 ) n.connectMany( new <Node>[ nodes[0], nodes[1] ] );
else if ( nodes.length == 1 ) n.connectMany( new <Node>[ nodes[0] ] );
// Else keep the
}
n.id = nodes.push( n );
//c.addEventListener(MouseEvent.CLICK, onCircleClick);
//circles.push( c );
//addChild( c );
//graphics.clear();
//drawArrows();
draw();
}
public function nearestNodes( node:Node, count:int = 3, data:Vector.<Node> = null ):Vector.<Node>
{
if ( data == null ) data = new Vector.<Node>();
if ( count == 0 ) return data;
var nearestDist:Number = Infinity, dist:Number;
var nearest:Node = null, test:Node;
// Scan all nodes
for ( var i:int = 0; i < nodes.length; ++i )
{
// Read test node
test = nodes[ i ];
// Prevent same node test checking
if ( test == node ) continue;
// Calc target node and test node distance
dist = node.distance( test );
// Check if too close
if ( dist < RADIUS ) return null;
// Current test node must not be in data list
if ( data.indexOf( test ) != -1 ) continue;
if ( dist < nearestDist )
{
nearestDist = dist;
nearest = test;
}
}
// If node was found, add to data
if( nearest ) data.push( nearest );
// Recursive call
return nearestNodes( node, count - 1, data );
}
public function draw():void
{
graphics.clear();
var n:Node, c:Node;
for (var i:int = 0; i < nodes.length; i++ )
{
n = nodes[i];
graphics.beginFill(0x0);
graphics.drawRect(n.x - 2, n.y - 2, 4, 4);
graphics.endFill();
for ( var j:int = 0; j < n.connected.length; j++ )
{
c = n.connected[j];
graphics.lineStyle(1, 0x0);
graphics.moveTo( n.x, n.y );
graphics.lineTo( c.x, c.y );
}
}
}
}
class Node
{
/// Unique identity number - optional
public var id:int = 0;
/// x position of the node
public var x:Number = 0;
/// y position of the node
public var y:Number = 0;
/// F - force ( the sum of g and h )
public var f:Number = 0;
/// G - distance of the current node to the starting node
public var g:Number = 0;
/// H - linear distance to the goal ( approximation )
public var h:Number = 0;
public var parent:Node = null;
public var connected:Vector.<Node> = null;
public function Node()
{
connected = new Vector.<Node>();
}
public function distance( to:Node ):Number
{
return Point.distance( to.position, position );
}
public function get position():Point
{
return new Point( x, y );
}
public function connectMany( nodes:Vector.<Node> ):void
{
for each( var n:Node in nodes ) connect( n );
}
public function connect( n:Node ):void
{
var double:Boolean = false;
for ( var i:int = 0; i < connected.length; ++i )
if ( connected[i] == n ) double = true
if ( !double ) {
connected.push( n );
n.connect( this );
}
}
public function toString():String
{
//return "<Node[3]:(x:23, y:64), F(100) = G(30) + H(70), ParentId[23], Connected[1,4,5,6,7]>";
var nodes:String = connected == null ? "null" : (connected.length == 0 ? "nun" : "");
if ( nodes == "" ) for each (var n:Node in connected) nodes += n.id.toString() + (connected.indexOf(n) < connected.length - 1? ", " : "");
return "< Node[" + id.toString() + "]:(X:" + x.toFixed(1) +
", Y:" + y.toFixed(1) + "), F(" + f.toFixed(1) +
") = G(" + g.toFixed(1) + ") + H(" + h.toFixed(1) +
"), ParentId[" + (parent == null ? "null" : parent.id.toString()) +
"], Connected[" + nodes + "] >";
return "Node[" + id.toString() + "]"
}
}
/**
* //http://www.emanueleferonato.com/2012/06/18/algorithm-to-determine-if-a-point-is-inside-a-triangle-with-mathematics-no-hit-test-involved/
*
* @param A Triangle first point
* @param B Triangle second point
* @param C Triangle third point
* @param P Test point - check if it's located inside the triangle
* @return True if the point P is located inside the Triangle, false if not
*/
function isInsideTriangle(A:Point, B:Point, C:Point, P:Point):Boolean
{
var planeAB:Number = (A.x - P.x) * (B.y - P.y) - (B.x - P.x) * (A.y - P.y);
var planeBC:Number = (B.x - P.x) * (C.y - P.y) - (C.x - P.x) * (B.y - P.y);
var planeCA:Number = (C.x - P.x) * (A.y - P.y) - (A.x - P.x) * (C.y - P.y);
return sign( planeAB ) == sign( planeBC ) && sign( planeBC ) == sign( planeCA );
}
/// Faster then Math.abs(n)/n - return +1 for [0, Infinity) and -1 for (-Infinity, 0) - 0 will return +1
function sign(n:Number):int {
return n < 0 ? -1 : +1;
// Return +1, -1 or 0
//return ( n > 0 ? 1 : ( n < 0 ? -1 : 0 ) );
}