Author: tomithy Date: 2010-08-10 21:30:17 -0700 (Tue, 10 Aug 2010) New Revision: 21330
Modified: cytoscapeweb/branches/gsoc2010/gbeb/src/gbeb/util/delaunay/Delaunay.as Log: -Version 0.9 Cleaned up codes. Modified: cytoscapeweb/branches/gsoc2010/gbeb/src/gbeb/util/delaunay/Delaunay.as =================================================================== --- cytoscapeweb/branches/gsoc2010/gbeb/src/gbeb/util/delaunay/Delaunay.as 2010-08-11 04:12:37 UTC (rev 21329) +++ cytoscapeweb/branches/gsoc2010/gbeb/src/gbeb/util/delaunay/Delaunay.as 2010-08-11 04:30:17 UTC (rev 21330) @@ -1,152 +1,110 @@ -// Main implementation of the source code is by Zachary and can be found on http://indiemaps.com/blog/2008/05/delaunay-triangulation-in-actionscript-3/ -// Other static methods are added to interface with GBEB +/* +This file is part of Cytoscape Web. +Copyright (c) 2009, The Cytoscape Consortium (www.cytoscape.org) +The Cytoscape Consortium is: +- Agilent Technologies +- Institut Pasteur +- Institute for Systems Biology +- Memorial Sloan-Kettering Cancer Center +- National Center for Integrative Biomedical Informatics +- Unilever +- University of California San Diego +- University of California San Francisco +- University of Toronto + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ + package gbeb.util.delaunay -{ - import flash.display.DisplayObjectContainer; - import flash.display.Shape; - import flash.display.Sprite; - import flash.text.TextField; +{ + /** + * Abstract utility class used for Dalaunay Triangulation + * ain implementation of the source code is by Zachary and can be found on http://indiemaps.com/blog/2008/05/ + * delaunay-triangulation-in-actionscript-3/ + */ - import gbeb.view.operator.router.MeshEdge; - import gbeb.view.operator.router.MeshNode; - public class Delaunay { - public static var EPSILON=0.000001; - public function Delaunay() { - // constructor does nothing class is a container for static methods - } + // ========[ CONSTANTS ]==================================================================== - /* - draw the circumcircles of the resultant triangular mesh - not useful, just maybe looks cool - for now, just change circle display properties in the method (below) itself - */ - static function circumCircles(clip:DisplayObjectContainer) { - //function not done yet - } + public static var EPSILON:Number = 0.000001; - /* - Return TRUE if a point (xp,yp) is inside the circumcircle made up - of the points (x1,y1), (x2,y2), (x3,y3) - The circumcircle centre is returned in (xc,yc) and the radius r - NOTE: A point on the edge is inside the circumcircle - */ - static function CircumCircle(xp,yp,x1,y1,x2,y2,x3,y3,circle:XYZ):Boolean { - var m1,m2,mx1,mx2,my1,my2; - var dx,dy,rsqr,drsqr; - var xc, yc, r; - - /* Check for coincident points */ - - if ( Math.abs(y1-y2) < EPSILON && Math.abs(y2-y3) < EPSILON ) - { - trace("CircumCircle: Points are coincident."); - return false; - } - - if ( Math.abs(y2-y1) < EPSILON ) - { - m2 = - (x3-x2) / (y3-y2); - mx2 = (x2 + x3) / 2.0; - my2 = (y2 + y3) / 2.0; - xc = (x2 + x1) / 2.0; - yc = m2 * (xc - mx2) + my2; - } - else if ( Math.abs(y3-y2) < EPSILON ) - { - m1 = - (x2-x1) / (y2-y1); - mx1 = (x1 + x2) / 2.0; - my1 = (y1 + y2) / 2.0; - xc = (x3 + x2) / 2.0; - yc = m1 * (xc - mx1) + my1; - } - else - { - m1 = - (x2-x1) / (y2-y1); - m2 = - (x3-x2) / (y3-y2); - mx1 = (x1 + x2) / 2.0; - mx2 = (x2 + x3) / 2.0; - my1 = (y1 + y2) / 2.0; - my2 = (y2 + y3) / 2.0; - xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2); - yc = m1 * (xc - mx1) + my1; - } - - dx = x2 - xc; - dy = y2 - yc; - rsqr = dx*dx + dy*dy; - r = Math.sqrt(rsqr); - - dx = xp - xc; - dy = yp - yc; - drsqr = dx*dx + dy*dy; - - circle.x = xc; - circle.y = yc; - circle.z = r; - - return ( drsqr <= rsqr ? true : false ); + + // ========[ CONSTRUCTOR ]================================================================== + + /** + * This constructor will throw an error, as this is an abstract class. + */ + + public function Delaunay() { + throw new Error("This is an abstract class."); } - /* - Triangulation subroutine - Takes as input, an array of vertices in pxyz - each vertex should be an instance of the XYZ class + // ========[ PUBLIC METHODS ]=============================================================== - Returned is an array of triangular faces in the array v - These triangles are arranged in a consistent clockwise order. - The triangle array 'v' should be malloced to 3 * nv - The vertex array pxyz must be big enough to hold 3 more points - The vertex array must be sorted in increasing x values say + /** + *Triangulation subroutine: Takes as input, an array of vertices in pxyz each vertex should be an instance of the XYZ class + + *Returned is an array of triangular faces in the array v. These triangles are arranged in a consistent clockwise order. + *The triangle array 'v' should be malloced to 3 * nv. The vertex array pxyz must be big enough to hold 3 more points + *The vertex array must be sorted in increasing x values say */ public static function triangulate(pxyz:Array):Array { var v:Array=new Array(); - var nv = pxyz.length; + var nv:Number = pxyz.length; for (i=0; i < (nv*3); i++) { v[i]=new ITriangle(); } - trace("Delaunay: Triangulating..."); - // the points must be sorted on the x dimension for the rest to work pxyz.sortOn("x", Array.NUMERIC); - var complete:Array = null; - var edges:Array = null; - var nedge = 0; - var trimax, emax = 200; - var status = 0; + var complete:Array = null; + var edges:Array = null; + var nedge:int = 0; + var trimax:Number, emax:Number = 200; + //var status = 0; var inside:Boolean; - var xp, yp, x1, y1, x2, y2, x3, y3, xc, yc, r; - var xmin, xmax, ymin, ymax, xmid, ymid; - var dx, dy, dmax; + var xp:Number, yp:Number, x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number; + var xc:Number, yc:Number, r:Number; + var xmin:Number, xmax:Number, ymin:Number, ymax:Number, xmid:Number, ymid:Number; + var dx:Number, dy:Number, dmax:Number; - var ntri = 0; + var ntri:int = 0; - /* Allocate memory for the completeness list, flag for each triangle */ + // Allocate memory for the completeness list, flag for each triangle trimax = 4*nv; complete = new Array(); - for (var ic=0; ic<trimax; ic++) complete[ic] = false; + for (var ic:int=0; ic<trimax; ic++) complete[ic] = false; - /* Allocate memory for the edge list */ + // Allocate memory for the edge list edges = new Array(); - for (var ie=0; ie<emax; ie++) edges[ie] = new IEdge(); + for (var ie:int=0; ie<emax; ie++) edges[ie] = new IEdge(); - /* - Find the maximum and minimum vertex bounds. - This is to allow calculation of the bounding triangle - */ + + // Find the maximum and minimum vertex bounds. This is to allow calculation of the bounding triangle xmin = pxyz[0].x; ymin = pxyz[0].y; xmax = xmin; ymax = ymin; - for (var i=1;i<nv;i++) + for (var i:int=1;i<nv;i++) { if (pxyz[i].x < xmin) xmin = pxyz[i].x; if (pxyz[i].x > xmax) xmax = pxyz[i].x; @@ -159,13 +117,10 @@ xmid = (xmax + xmin) / 2.0; ymid = (ymax + ymin) / 2.0; - /* - Set up the supertriangle - This is a triangle which encompasses all the sample points. - The supertriangle coordinates are added to the end of the - vertex list. The supertriangle is the first triangle in - the triangle list. - */ + + // Set up the supertriangle + // This is a triangle which encompasses all the sample points. The supertriangle coordinates are added to the end of the + // vertex list. The supertriangle is the first triangle in the triangle list. pxyz[nv] = new XYZ(); pxyz[nv+1] = new XYZ(); pxyz[nv+2] = new XYZ(); @@ -186,23 +141,21 @@ complete[0] = false; ntri = 1; - /* - Include each point one at a time into the existing mesh - */ + + // Include each point one at a time into the existing mesh + for (i=0;i<nv;i++) { xp = pxyz[i].x; yp = pxyz[i].y; nedge = 0; - /* - Set up the edge buffer. - If the point (xp,yp) lies inside the circumcircle then the - three edges of that triangle are added to the edge buffer - and that triangle is removed. - */ + + // Set up the edge buffer. If the point (xp,yp) lies inside the circumcircle then the + // three edges of that triangle are added to the edge buffer and that triangle is removed. + var circle:XYZ = new XYZ(); - for (var j=0;j<ntri;j++) + for (var j:int=0;j<ntri;j++) { if (complete[j]) continue; @@ -217,14 +170,13 @@ if (xc + r < xp) complete[j] = true; if (inside) { - /* Check that we haven't exceeded the edge list size */ + // Check that we haven't exceeded the edge list size if (nedge+3 >= emax) { - trace("crazy if statement"); emax += 100; - var edges_n = new Array(); - for (ie=0; ie<emax; ie++) edges_n[ie] = new IEdge(); - for (var zfj=0; zfj<edges.length; zfj++) { + var edges_n:Array = new Array(); + for (var ie:int=0; ie<emax; ie++) edges_n[ie] = new IEdge(); + for (var zfj:int=0; zfj<edges.length; zfj++) { edges_n[zfj] = edges[zfj]; } edges = edges_n; @@ -244,16 +196,12 @@ j--; } } - - /* - Tag multiple edges - Note: if all triangles are specified anticlockwise then all - interior edges are opposite pointing in direction. - */ + + // Tag multiple edges. Note: if all triangles are specified anticlockwise then all + // interior edges are opposite pointing in direction. for (j=0;j<nedge-1;j++) { - //if ( !(edges[j].p1 < 0 && edges[j].p2 < 0) ) - for (var k=j+1;k<nedge;k++) + for (var k:int=j+1;k<nedge;k++) { if ((edges[j].p1 == edges[k].p2) && (edges[j].p2 == edges[k].p1)) { @@ -262,7 +210,7 @@ edges[k].p1 = -1; edges[k].p2 = -1; } - /* Shouldn't need the following, see note above */ + // Shouldn't need the following, see note above if ((edges[j].p1 == edges[k].p1) && (edges[j].p2 == edges[k].p2)) { edges[j].p1 = -1; @@ -273,11 +221,8 @@ } } - /* - Form new triangles for the current point - Skipping over any tagged edges. - All edges are arranged in clockwise order. - */ + // Form new triangles for the current point. Skipping over any tagged edges. + // All edges are arranged in clockwise order. for (j=0;j<nedge;j++) { if (edges[j].p1 == -1 || edges[j].p2 == -1) @@ -291,10 +236,7 @@ } } - /* - Remove triangles with supertriangle vertices - These are triangles which have a vertex number greater than nv - */ + // Remove triangles with supertriangle vertices. These are triangles which have a vertex number greater than nv. for (i=0;i<ntri;i++) { if (v[i].p1 >= nv || v[i].p2 >= nv || v[i].p3 >= nv) @@ -311,133 +253,64 @@ return v; } - - /* - public static method drawDelaunay - - takes standard output of Delaunay as input (arrays of points and triangles) - draws the triangulation on the passed-in display object container - */ - public static function drawDelaunay(tris:Array, points:Array, clip:DisplayObjectContainer, toLabel:Boolean = false) { - var p = new Sprite(); // for the points - var t = new Sprite(); // for the triangles - var TriCounter:int = 0; + //Return TRUE if a point (xp,yp) is inside the circumcircle made up of the points (x1,y1), (x2,y2), (x3,y3) + //The circumcircle centre is returned in (xc,yc) and the radius r. NOTE: A point on the edge is inside the circumcircle + private static function CircumCircle(xp:Number, yp:Number, x1:Number, y1:Number, x2:Number, y2:Number, + x3:Number, y3:Number, circle:XYZ):Boolean { - clip.addChild(t); - clip.addChild(p); - if (toLabel) { - var l:Sprite = new Sprite(); // for the labels - clip.addChild(l); - } + var m1:Number,m2:Number,mx1:Number,mx2:Number,my1:Number,my2:Number; + var dx:Number,dy:Number,rsqr:Number,drsqr:Number; + var xc:Number, yc:Number, r:Number; - for each(var point:XYZ in points) { - if (point==null) continue; - var circ:Shape = new Shape(); - circ.graphics.beginFill(0x42C0FB); - circ.graphics.drawCircle(0,0,4); - circ.graphics.endFill(); - circ.x = point.x; - circ.y = point.y; - p.addChild(circ); - - if (toLabel) { - var tf = new TextField(); - tf.text = point.z; - tf.x = point.x + 1; - tf.y = -(point.y + 13); - l.addChild(tf); - } - } - for each(var tri in tris) { - with (t.graphics) { - lineStyle(1.5, 0x42C0FB); - moveTo(points[tri.p1].x, points[tri.p1].y); - lineTo(points[tri.p2].x, points[tri.p2].y); - lineTo(points[tri.p3].x, points[tri.p3].y); - lineTo(points[tri.p1].x, points[tri.p1].y); - TriCounter++; - } - } + /* Check for coincident points */ - var testGraphics:Sprite = new Sprite(); - testGraphics.graphics.beginFill(0x000000); - testGraphics.graphics.drawCircle(100, 100, 50); - testGraphics.graphics.endFill(); - - //clip.addChild(testGraphics); - trace("Delaunay: Finished Triangulating. There are", TriCounter, "triangles"); - } - - public static function convertToMeshEdges(triangles:Array, points:Array, meshNodes:Array):Array - { - var meshEdgeArray:Array = []; - var meshEdge:MeshEdge; - - var mapArray:Array = []; //variable length array to store the index mapping of meshEdges to points array - for(var i:int = 0; i < points.length; i++) + if ( Math.abs(y1-y2) < EPSILON && Math.abs(y2-y3) < EPSILON ) { - mapArray.push(new Array()); + return false; //CircumCircle points are coincident. } - trace("Delaunay: pointArray.length: " + points.length); - - for each (var tri:ITriangle in triangles) + if ( Math.abs(y2-y1) < EPSILON ) { - meshEdge = generateEdge(tri.p1, tri.p2, points, meshNodes, mapArray, meshEdgeArray); - if( meshEdge != null) meshEdgeArray.push(meshEdge); - - meshEdge = generateEdge(tri.p2, tri.p3, points, meshNodes, mapArray, meshEdgeArray); - if( meshEdge != null) meshEdgeArray.push(meshEdge); - - meshEdge = generateEdge(tri.p3, tri.p1, points, meshNodes, mapArray, meshEdgeArray); - if( meshEdge != null) meshEdgeArray.push(meshEdge); + m2 = - (x3-x2) / (y3-y2); + mx2 = (x2 + x3) / 2.0; + my2 = (y2 + y3) / 2.0; + xc = (x2 + x1) / 2.0; + yc = m2 * (xc - mx2) + my2; } - - trace("Delaunay: Finished Conversion: convertToMeshEdges: " + meshEdgeArray.length + " edges have been created!"); - return meshEdgeArray; - } - - private static function generateEdge(sourceIdx:int, targetIdx:int, points:Array, meshNodes:Array, mapArray:Array, meshEdgeArray:Array):MeshEdge - { - var meshEdge:MeshEdge; - var sourceAssigned:Boolean = false; - var targetAssigned:Boolean = false; - - //checking mapArray to see if the Edge has already been created - //reads: if edge, as defined by the the start and ends points exists, return - if( (mapArray[sourceIdx] as Array).indexOf(targetIdx) != -1) return null; - if( (mapArray[targetIdx] as Array).indexOf(sourceIdx) != -1) return null; - //trace("Delanunay catching errantEdges at ( " + sourceIdx + "," + targetIdx + " )"); - - (mapArray[sourceIdx] as Array).push(targetIdx); - meshEdge = new MeshEdge(); - - meshEdge.x1 = points[sourceIdx].x; meshEdge.y1 = points[sourceIdx].y; - meshEdge.x2 = points[targetIdx].x; meshEdge.y2 = points[targetIdx].y; - - //trace("Delaunay: " + meshEdge.x1, meshEdge.y1 + " | " + meshEdge.x2, meshEdge.y2); - if(Math.abs(meshEdge.x1 - meshEdge.x2) < 0.01 && Math.abs(meshEdge.y1 - meshEdge.y2) < 0.01) return null; - - for each(var node:MeshNode in meshNodes) + else if ( Math.abs(y3-y2) < EPSILON ) { - if( Math.abs(node.x - meshEdge.x1) < 0.1 && Math.abs(node.y - meshEdge.y1) < 0.1) - { - meshEdge.source = node; - sourceAssigned = true; - } else if (Math.abs(node.x - meshEdge.x2) < 0.1 && Math.abs(node.y - meshEdge.y2) < 0.1) - { - meshEdge.target = node; - targetAssigned = true; - } - if(sourceAssigned && targetAssigned) break; + m1 = - (x2-x1) / (y2-y1); + mx1 = (x1 + x2) / 2.0; + my1 = (y1 + y2) / 2.0; + xc = (x3 + x2) / 2.0; + yc = m1 * (xc - mx1) + my1; } + else + { + m1 = - (x2-x1) / (y2-y1); + m2 = - (x3-x2) / (y3-y2); + mx1 = (x1 + x2) / 2.0; + mx2 = (x2 + x3) / 2.0; + my1 = (y1 + y2) / 2.0; + my2 = (y2 + y3) / 2.0; + xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2); + yc = m1 * (xc - mx1) + my1; + } - if(!(sourceAssigned && targetAssigned)) trace("Delaunay: generateEdge: This edge either does not have a target or a source or both!"); + dx = x2 - xc; + dy = y2 - yc; + rsqr = dx*dx + dy*dy; + r = Math.sqrt(rsqr); - meshEdge.name = "mE" + meshEdgeArray.length; //debug: meshEdgeArray is passed in strictly for debug purposes. Can be removed. + dx = xp - xc; + dy = yp - yc; + drsqr = dx*dx + dy*dy; - //trace("Delaunay: generateEdge: An Edge spanning " + sourceIdx + ", " + targetIdx + " has been created"); - return meshEdge; + circle.x = xc; + circle.y = yc; + circle.z = r; + + return ( drsqr <= rsqr ? true : false ); } }//end of class -- You received this message because you are subscribed to the Google Groups "cytoscape-cvs" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/cytoscape-cvs?hl=en.
