igeo
Class IDelaunay2D

java.lang.Object
  extended by igeo.IDelaunay2D

public class IDelaunay2D
extends java.lang.Object

Class to calculate Delaunay triangulation out of 2D points.

Author:
Satoru Sugihara

Nested Class Summary
static class IDelaunay2D.EdgeCounter
           
static class IDelaunay2D.FaceIndex
           
 
Field Summary
static double maxDistToCheck
           
 
Constructor Summary
IDelaunay2D()
           
 
Method Summary
static boolean checkDirectionOfInnerCircumcirclePoint(IVec2[] pts, IVec2[][] edgePts, int ptIdx1, int ptIdx2, int ptIdx3, int ptIdx4, int innerPtNum)
           
static boolean checkDirectionOnEdgePoints(IVec2[] pts, IVec2[][] edgePts, int ptIdx1, int ptIdx2, int ptIdx3, int innerPtNum)
           
static boolean checkFaceDirection(IVec2[] pts, IDelaunay2D.EdgeCounter edgeCount, int ptIdx1, int ptIdx2, int ptIdx3)
           
static void checkNakedEdge(IVec2[] pts, java.util.ArrayList<IDelaunay2D.FaceIndex> faceIdx, java.util.ArrayList<IVec2[]> triangles, IDelaunay2D.EdgeCounter edgeCount)
           
static double determinant(double v11, double v12, double v13, double v21, double v22, double v23, double v31, double v32, double v33)
           
static IDelaunay2D.FaceIndex findTriangleIndexWithEdge(java.util.ArrayList<IDelaunay2D.FaceIndex> faceIdx, int ptIdx1, int ptIdx2)
           
static IVec2[] findTriangleWithIndex(IVec2[] pts, java.util.ArrayList<IVec2[]> triangles, int index1, int index2, int index3)
           
static IVec2[] getAdjacentPointsOnEdgeLoop(IVec2[][] edgePts, IVec2 pt)
           
static IVec[][] getEdges(IVec[] pts)
          Getting edges of 2D delaunay triangles out of array of 3D points and projection vector.
static IVec[][] getEdges(IVec[] pts, IVecI projectionDir)
          Getting edges of 2D delaunay triangles out of array of 3D points and projection vector.
static IVec2[][] getEdges(IVec2[] pts)
          Getting edges of delaunay triangles out of array of 2D points
static IVecI[][] getEdges(IVecI[] pts)
          Getting edges of 2D delaunay triangles out of array of 3D points and projection vector.
static IVecI[][] getEdges(IVecI[] pts, IVecI projectionDir)
          Getting edges of 2D delaunay triangles out of array of 3D points and projection vector.
static IMesh getMesh(IVecI[] pts)
          Getting delaunay triangles out of array of 3D points interpreted as 2D points on XY plane.
static IVec[][] getTriangles(IVec[] pts)
          Getting delaunay triangles out of array of 3D points interpreted as 2D points on XY plane.
static IVec[][] getTriangles(IVec[] pts, IVecI projectionDir)
          Getting delaunay triangles out of array of 3D points interpreted as 2D points on a projected plane.
static IVec2[][] getTriangles(IVec2[] pts)
          Getting delaunay triangles out of array of 2D points
static IVec2[][] getTriangles(IVec2[] innerPts, IVec2[][] edgePts)
          Calculates Delaunay triangles out of array of 2D points
static IVecI[][] getTriangles(IVecI[] pts)
          Getting delaunay triangles out of array of 3D points interpreted as 2D points on XY plane.
static IVecI[][] getTriangles(IVecI[] pts, IVecI projectionDir)
          Getting delaunay triangles out of array of 3D points interpreted as 2D points on a projected plane.
static IVecI[][] getTriangles(IVecI[] pts, IVecI planeDir, IVecI planePt)
          Getting delaunay triangles out of array of 3D points interpreted as 2D points on a specified plane.
static boolean isClockwise(IVec2 pt1, IVec2 pt2, IVec2 pt3)
           
static boolean isFaceCrossing(IVec2[] pts, IDelaunay2D.EdgeCounter edgeCount, int ptIdx1, int ptIdx2, int ptIdx3)
           
static boolean isFaceDirectionOnEdgeCorrect(IVec2[][] edgePts, IVec2 pt, IVec2 vertexPt1, IVec2 vertexPt2)
           
static boolean isFaceDirectionOnEdgeCorrect(IVec2 edgePt1, IVec2 edgePt2, IVec2 vertexPt)
           
static boolean isInsideCircumcircle(IVec2 pt, IVec2 trianglePt1, IVec2 trianglePt2, IVec2 trianglePt3)
           
static boolean isPointInsideEdge(IVec2 pt, IVec2 edgePt1, IVec2 edgePt2, IVec2 edgePt3)
           
static boolean isPointsIntersectiongWithEdge(IVec2 pt1, IVec2 pt2, IVec2 edgePt1, IVec2 edgePt2, IVec2 edgePt3)
           
static boolean isSameTriangle(IVec2[] triangle, IVec2 pt1, IVec2 pt2, IVec2 pt3)
           
static boolean isVertexOnSameSide(IVec2 edgePt1, IVec2 edgePt2, IVec2 vertexPt1, IVec2 vertexPt2)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

maxDistToCheck

public static double maxDistToCheck
Constructor Detail

IDelaunay2D

public IDelaunay2D()
Method Detail

getTriangles

public static IVec2[][] getTriangles(IVec2[] innerPts,
                                     IVec2[][] edgePts)
Calculates Delaunay triangles out of array of 2D points

Parameters:
innerPts - points inside edges defined by edgePts
edgePts - points on the edge (the edge should be naked having only one triangle touching); order of edge points needs to be counter clockwise for outer trim loop, clockwise for inner hole trim loop.
Returns:
array of triangles, which consist of array of 3 points of IVec2

getTriangles

public static IVecI[][] getTriangles(IVecI[] pts)
Getting delaunay triangles out of array of 3D points interpreted as 2D points on XY plane.

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

getTriangles

public static IVecI[][] getTriangles(IVecI[] pts,
                                     IVecI projectionDir)
Getting delaunay triangles out of array of 3D points interpreted as 2D points on a projected plane.

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

getTriangles

public static IVecI[][] getTriangles(IVecI[] pts,
                                     IVecI planeDir,
                                     IVecI planePt)
Getting delaunay triangles out of array of 3D points interpreted as 2D points on a specified plane.

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

getTriangles

public static IVec[][] getTriangles(IVec[] pts)
Getting delaunay triangles out of array of 3D points interpreted as 2D points on XY plane.

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

getTriangles

public static IVec[][] getTriangles(IVec[] pts,
                                    IVecI projectionDir)
Getting delaunay triangles out of array of 3D points interpreted as 2D points on a projected plane.

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

getTriangles

public static IVec2[][] getTriangles(IVec2[] pts)
Getting delaunay triangles out of array of 2D points

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

getMesh

public static IMesh getMesh(IVecI[] pts)
Getting delaunay triangles out of array of 3D points interpreted as 2D points on XY plane.

Returns:
a mesh.

getEdges

public static IVec2[][] getEdges(IVec2[] pts)
Getting edges of delaunay triangles out of array of 2D points

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

getEdges

public static IVecI[][] getEdges(IVecI[] pts)
Getting edges of 2D delaunay triangles out of array of 3D points and projection vector.

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

getEdges

public static IVecI[][] getEdges(IVecI[] pts,
                                 IVecI projectionDir)
Getting edges of 2D delaunay triangles out of array of 3D points and projection vector.

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

getEdges

public static IVec[][] getEdges(IVec[] pts)
Getting edges of 2D delaunay triangles out of array of 3D points and projection vector.

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

getEdges

public static IVec[][] getEdges(IVec[] pts,
                                IVecI projectionDir)
Getting edges of 2D delaunay triangles out of array of 3D points and projection vector.

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

isInsideCircumcircle

public static boolean isInsideCircumcircle(IVec2 pt,
                                           IVec2 trianglePt1,
                                           IVec2 trianglePt2,
                                           IVec2 trianglePt3)

isClockwise

public static boolean isClockwise(IVec2 pt1,
                                  IVec2 pt2,
                                  IVec2 pt3)

determinant

public static double determinant(double v11,
                                 double v12,
                                 double v13,
                                 double v21,
                                 double v22,
                                 double v23,
                                 double v31,
                                 double v32,
                                 double v33)

isFaceCrossing

public static boolean isFaceCrossing(IVec2[] pts,
                                     IDelaunay2D.EdgeCounter edgeCount,
                                     int ptIdx1,
                                     int ptIdx2,
                                     int ptIdx3)

isVertexOnSameSide

public static boolean isVertexOnSameSide(IVec2 edgePt1,
                                         IVec2 edgePt2,
                                         IVec2 vertexPt1,
                                         IVec2 vertexPt2)

isFaceDirectionOnEdgeCorrect

public static boolean isFaceDirectionOnEdgeCorrect(IVec2 edgePt1,
                                                   IVec2 edgePt2,
                                                   IVec2 vertexPt)

isFaceDirectionOnEdgeCorrect

public static boolean isFaceDirectionOnEdgeCorrect(IVec2[][] edgePts,
                                                   IVec2 pt,
                                                   IVec2 vertexPt1,
                                                   IVec2 vertexPt2)

isPointsIntersectiongWithEdge

public static boolean isPointsIntersectiongWithEdge(IVec2 pt1,
                                                    IVec2 pt2,
                                                    IVec2 edgePt1,
                                                    IVec2 edgePt2,
                                                    IVec2 edgePt3)

isPointInsideEdge

public static boolean isPointInsideEdge(IVec2 pt,
                                        IVec2 edgePt1,
                                        IVec2 edgePt2,
                                        IVec2 edgePt3)

checkFaceDirection

public static boolean checkFaceDirection(IVec2[] pts,
                                         IDelaunay2D.EdgeCounter edgeCount,
                                         int ptIdx1,
                                         int ptIdx2,
                                         int ptIdx3)

checkDirectionOnEdgePoints

public static boolean checkDirectionOnEdgePoints(IVec2[] pts,
                                                 IVec2[][] edgePts,
                                                 int ptIdx1,
                                                 int ptIdx2,
                                                 int ptIdx3,
                                                 int innerPtNum)

getAdjacentPointsOnEdgeLoop

public static IVec2[] getAdjacentPointsOnEdgeLoop(IVec2[][] edgePts,
                                                  IVec2 pt)

checkDirectionOfInnerCircumcirclePoint

public static boolean checkDirectionOfInnerCircumcirclePoint(IVec2[] pts,
                                                             IVec2[][] edgePts,
                                                             int ptIdx1,
                                                             int ptIdx2,
                                                             int ptIdx3,
                                                             int ptIdx4,
                                                             int innerPtNum)

checkNakedEdge

public static void checkNakedEdge(IVec2[] pts,
                                  java.util.ArrayList<IDelaunay2D.FaceIndex> faceIdx,
                                  java.util.ArrayList<IVec2[]> triangles,
                                  IDelaunay2D.EdgeCounter edgeCount)

findTriangleWithIndex

public static IVec2[] findTriangleWithIndex(IVec2[] pts,
                                            java.util.ArrayList<IVec2[]> triangles,
                                            int index1,
                                            int index2,
                                            int index3)

isSameTriangle

public static boolean isSameTriangle(IVec2[] triangle,
                                     IVec2 pt1,
                                     IVec2 pt2,
                                     IVec2 pt3)

findTriangleIndexWithEdge

public static IDelaunay2D.FaceIndex findTriangleIndexWithEdge(java.util.ArrayList<IDelaunay2D.FaceIndex> faceIdx,
                                                              int ptIdx1,
                                                              int ptIdx2)
Parameters:
ptIdx1 - requirement: ptIdx1 < ptIdx2