igeo
Class IVoronoi2D

java.lang.Object
  extended by igeo.IVoronoi2D

public class IVoronoi2D
extends java.lang.Object

Class to calculate Delaunay triangulation out of 2D points.

Author:
Satoru Sugihara

Nested Class Summary
static class IVoronoi2D.RadialComparator
           
 
Constructor Summary
IVoronoi2D()
           
 
Method Summary
static IVec2 circumcenter(IVec2[] t)
           
static IVec2 circumcenter(IVec2 t1, IVec2 t2, IVec2 t3)
           
static IVec2[] closeWithBoundary(IVec2[] openPts, IVec2 minUV, IVec2 maxUV)
           
static IVec2[] edgePoint(IVec2 vertex, IVec2[] triangle)
          get two other edge points of a triangle other than the given vertex
static IVec2[][] getPolygons(IVec2[] pts)
          Getting voronoi polygons out of array of 2D points
static IVec2[][] getPolygons(IVec2[] pts, IVec2 minUV, IVec2 maxUV)
          Getting voronoi polygons out of array of 2D points.
static boolean insideBoundary(IVec2 pt, IVec2 minUV, IVec2 maxUV)
           
static boolean insideTriangle(IVec2 pt, IVec2 tr1, IVec2 tr2, IVec2 tr3)
           
static IVec2 intersectWithBoundary(IVec2 ptIn, IVec2 ptOut, IVec2[] boundary)
           
static IVec2[] pointsInsideBoundary(IVec2[] pts, IVec2 minUV, IVec2 maxUV, boolean close)
          check all points in pts is in boundary and if not, remove and insert an intersection point with the boundary
static IVec2[] removeDuplicatedPoint(IVec2[] pts, double tolerance)
           
static java.util.ArrayList<IVec2> sortTriangleEdgePoint(IVec2 center, java.util.ArrayList<IVec2[]> triangles)
          when a point is surrounded by triangles, sort triangles in the order they are touching.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

IVoronoi2D

public IVoronoi2D()
Method Detail

getPolygons

public static IVec2[][] getPolygons(IVec2[] pts)
Getting voronoi polygons out of array of 2D points

Returns:
array of triangles, which consist of array of 3 points of IVec2

getPolygons

public static IVec2[][] getPolygons(IVec2[] pts,
                                    IVec2 minUV,
                                    IVec2 maxUV)
Getting voronoi polygons out of array of 2D points.

Parameters:
minUV - minimum corner of boundary rectangle
maxUV - maximum corner of boundary rectangle
Returns:
array of polygons and triangles; IVec2[0] is polygons and IVec[1] is triangles.

removeDuplicatedPoint

public static IVec2[] removeDuplicatedPoint(IVec2[] pts,
                                            double tolerance)

insideTriangle

public static boolean insideTriangle(IVec2 pt,
                                     IVec2 tr1,
                                     IVec2 tr2,
                                     IVec2 tr3)

intersectWithBoundary

public static IVec2 intersectWithBoundary(IVec2 ptIn,
                                          IVec2 ptOut,
                                          IVec2[] boundary)

insideBoundary

public static boolean insideBoundary(IVec2 pt,
                                     IVec2 minUV,
                                     IVec2 maxUV)

pointsInsideBoundary

public static IVec2[] pointsInsideBoundary(IVec2[] pts,
                                           IVec2 minUV,
                                           IVec2 maxUV,
                                           boolean close)
check all points in pts is in boundary and if not, remove and insert an intersection point with the boundary


closeWithBoundary

public static IVec2[] closeWithBoundary(IVec2[] openPts,
                                        IVec2 minUV,
                                        IVec2 maxUV)

sortTriangleEdgePoint

public static java.util.ArrayList<IVec2> sortTriangleEdgePoint(IVec2 center,
                                                               java.util.ArrayList<IVec2[]> triangles)
when a point is surrounded by triangles, sort triangles in the order they are touching. The sort direction is not defined. It can be either clockwise or counterclockwise.

Returns:
sorted array of edge points. if it's closed, the first and the last points are same

edgePoint

public static IVec2[] edgePoint(IVec2 vertex,
                                IVec2[] triangle)
get two other edge points of a triangle other than the given vertex


circumcenter

public static IVec2 circumcenter(IVec2 t1,
                                 IVec2 t2,
                                 IVec2 t3)

circumcenter

public static IVec2 circumcenter(IVec2[] t)