igeo

Class IDelaunay2D

java.lang.Object

igeo.IDelaunay2D

public class IDelaunay2D
extends java.lang.Object

Class to calculate Delaunay triangulation out of 2D points.

Author:

Satoru Sugihara

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	IDelaunay2D.EdgeCounter
static class	IDelaunay2D.FaceIndex

Field Summary

Fields

Modifier and Type	Field and Description
static double	maxDistToCheck

Constructor Summary

Constructors

Constructor and Description
IDelaunay2D()

Method Summary

Methods

Modifier and Type	Method and Description
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[]	getOutline(IVec[] pts) Getting outline (hull) points of delaunay triangles out of array of 3D points
static IVec[]	getOutline(IVec[] pts, IVecI projectionDir) Getting outline (hull) points of delaunay triangles out of array of 3D points and projection direction.
static IVec2[]	getOutline(IVec2[] pts) Getting outline (hull) points of delaunay triangles out of array of 2D points
static IVecI[]	getOutline(IVecI[] pts) Getting outline (hull) points of delaunay triangles out of array of 3D points
static IVecI[]	getOutline(IVecI[] pts, IVecI projectionDir) Getting outline (hull) points of delaunay triangles out of array of 3D points and projection direction.
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 pairs of IVec2 points, which represent edges.

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 pairs of IVec2 points, which represent edges.

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 pairs of IVec2 points, which represent edges.

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 pairs of IVec2 points, which represent edges.

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 pairs of IVec2 points, which represent edges.

getOutline

public static IVec2[] getOutline(IVec2[] pts)

Getting outline (hull) points of delaunay triangles out of array of 2D points

Returns:

array of IVec2 points which reprenst outline polyline

getOutline

public static IVecI[] getOutline(IVecI[] pts)

Getting outline (hull) points of delaunay triangles out of array of 3D points

Returns:

array of IVec2 points which reprenst outline polyline

getOutline

public static IVecI[] getOutline(IVecI[] pts,
                 IVecI projectionDir)

Getting outline (hull) points of delaunay triangles out of array of 3D points and projection direction.

Returns:

array of IVec2 points which reprenst outline polyline

getOutline

public static IVec[] getOutline(IVec[] pts)

Getting outline (hull) points of delaunay triangles out of array of 3D points

Returns:

array of IVec2 points which reprenst outline polyline

getOutline

public static IVec[] getOutline(IVec[] pts,
                IVecI projectionDir)

Getting outline (hull) points of delaunay triangles out of array of 3D points and projection direction.

Returns:

array of IVec2 points which reprenst outline polyline

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