This is inspired by mapbox's earcut algorithm (https://github.com/mapbox/earcut) which is a modification to FIST (https://www.cosy.sbg.ac.at/~held/projects/triang/triang.html) written by Martin Held, and ear clipping (https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf) written by David Eberly.
Notes:
- Requires valid polygons:
- No self intersections
- Holes may only touch at one vertex
- Polygon must have an area (e.g., no "line" boxes)
- sensitive to overflow (e.g, subatomic values such as E-200 can cause unexpected behavior)
The code is a modified version of the javascript implementation provided by MapBox under the following license:
ISC License
Copyright (c) 2016, Mapbox
Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH' REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic interface
Implementation of this interface will receive calls with internal data at each step of the triangulation algorithm.protected static class
Circular Doubly-linked list used for polygon coordinatesprivate static enum
state of the tessellated split - avoids recursionstatic final class
Triangle in the tessellated mesh -
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate static double
area
(double aX, double aY, double bX, double bY, double cX, double cY) Compute signed area of triangleprivate static void
checkIntersection
(Tessellator.Node a, boolean isMorton) Computes if edge defined by a and b overlaps with a polygon edge *private static void
private static final Tessellator.Node
createDoublyLinkedList
(double[] x, double[] y, GeoUtils.WindingOrder polyWindingOrder, boolean isGeo, int startIndex, GeoUtils.WindingOrder windingOrder) Creates a circular doubly linked list using polygon points.private static final Tessellator.Node
cureLocalIntersections
(Tessellator.Node startNode, List<Tessellator.Triangle> tessellation, boolean mortonOptimized) Iterate through all polygon nodes and remove small local self-intersections *private static final List<Tessellator.Triangle>
earcutLinkedList
(Object polygon, Tessellator.Node currEar, List<Tessellator.Triangle> tessellation, Tessellator.State state, boolean mortonOptimized, Tessellator.Monitor monitor, int depth) Main ear slicing loop which triangulates the vertices of a polygon, provided as a doubly-linked list.private static final void
eliminateHole
(Tessellator.Node holeNode, Tessellator.Node outerNode, double holeMinX, double holeMaxX, double holeMinY, double holeMaxY) Finds a bridge between vertices that connects a hole with an outer ring, and links itprivate static final Tessellator.Node
eliminateHoles
(List<Tessellator.Node> holeList, Map<Tessellator.Node, ?> holeListPolygons, Tessellator.Node outerNode) private static final Tessellator.Node
eliminateHoles
(Polygon polygon, Tessellator.Node outerNode) Links every hole into the outer loop, producing a single-ring polygon without holes.private static final Tessellator.Node
eliminateHoles
(XYPolygon polygon, Tessellator.Node outerNode) private static final Tessellator.Node
fetchHoleBridge
(Tessellator.Node holeNode, Tessellator.Node outerNode) David Eberly's algorithm for finding a bridge between a hole and outer polygonprivate static final Tessellator.Node
fetchLeftmost
(Tessellator.Node start) Finds the left-most hole of a polygon ring.private static final Tessellator.Node
filterPoints
(Tessellator.Node start, Tessellator.Node end) Eliminate colinear/duplicate points from the doubly linked listgetPoints
(Tessellator.Node start) private static Tessellator.Node
getSharedVertex
(Tessellator.Node polygon, Tessellator.Node vertex) Check if the provided vertex is in the polygon and return it *private static final Tessellator.Node
insertNode
(double[] x, double[] y, int index, int vertexIndex, Tessellator.Node lastNode, boolean isGeo) Creates a node and optionally links it with a previous node in a circular doubly-linked listprivate static boolean
isCWPolygon
(Tessellator.Node start, Tessellator.Node end) Determine whether the polygon defined between node start and node end is CWprivate static final boolean
isEar
(Tessellator.Node ear, boolean mortonOptimized) Determines whether a polygon node forms a valid ear with adjacent nodes.private static boolean
isEdgeFromPolygon
(Tessellator.Node a, Tessellator.Node b, boolean isMorton) Computes if edge defined by a and b overlaps with a polygon edge *private static final boolean
isIntersectingPolygon
(Tessellator.Node start, double x0, double y0, double x1, double y1) Determines if the diagonal of a polygon is intersecting with any polygon elements.private static final boolean
private static final boolean
Uses morton code for speed to determine whether or not and edge defined by a and b overlaps with a polygon edgeprivate static boolean
isPointInLine
(Tessellator.Node a, Tessellator.Node b, double lon, double lat) returns true if the lon, lat point is colinear w/ the provided a and b pointprivate static boolean
isPointInLine
(Tessellator.Node a, Tessellator.Node b, Tessellator.Node point) private static final boolean
Determines whether a diagonal between two polygon nodes lies within a polygon interior.private static final boolean
isVertexEquals
(Tessellator.Node a, double x, double y) Determines if two point vertices are equal.private static final boolean
Determines if two point vertices are equal.static final boolean
linesIntersect
(double aX0, double aY0, double aX1, double aY1, double bX0, double bY0, double bX1, double bY1) Determines whether two line segments intersect.private static final boolean
middleInsert
(Tessellator.Node start, double x0, double y0, double x1, double y1) Determine whether the middle point of a polygon diagonal is contained within the polygonprivate static final void
Uses morton code for speed to determine whether or not and edge defined by a and b overlaps with a polygon edgeprivate static final boolean
Uses morton code for speed to determine whether or a polygon node forms a valid ear w/ adjacent nodesprivate static void
notifyMonitor
(String status, Tessellator.Monitor monitor, Tessellator.Node start, List<Tessellator.Triangle> tessellation) private static void
notifyMonitor
(Tessellator.State state, int depth, Tessellator.Monitor monitor, Tessellator.Node start, List<Tessellator.Triangle> tessellation) private static void
notifyMonitorSplit
(int depth, Tessellator.Monitor monitor, Tessellator.Node searchNode, Tessellator.Node diagonalNode) private static void
notifyMonitorSplitEnd
(int depth, Tessellator.Monitor monitor) private static boolean
pointInEar
(double x, double y, double ax, double ay, double bx, double by, double cx, double cy) Compute whether point is in a candidate earstatic final boolean
pointInPolygon
(List<Tessellator.Triangle> tessellation, double lat, double lon) Brute force compute if a point is in the polygon by traversing entire triangulation todo: speed this up using either binary tree or prefix coding (filtering by bounding box of triangle)static boolean
pointInTriangle
(double x, double y, double ax, double ay, double bx, double by, double cx, double cy) compute whether the given x, y point is in a triangle; uses the winding order methodprivate static final void
removeNode
(Tessellator.Node node, boolean edgeFromPolygon) Removes a node from the doubly linked listprivate static double
signedArea
(Tessellator.Node start, Tessellator.Node end) Determine the signed area between node start and node endprivate static final void
sortByMorton
(Tessellator.Node start) Interlinks polygon nodes in Z-Order.private static final void
Interlinks polygon nodes in Z-Order.private static final boolean
splitEarcut
(Object polygon, Tessellator.Node start, List<Tessellator.Triangle> tessellation, boolean mortonOptimized, Tessellator.Monitor monitor, int depth) Attempt to split a polygon and independently triangulate each side.private static final Tessellator.Node
splitPolygon
(Tessellator.Node a, Tessellator.Node b, boolean edgeFromPolygon) Links two polygon vertices using a bridge.private static final void
tathamSort
(Tessellator.Node list) Simon Tatham's doubly-linked list O(n log n) mergesort see: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.htmlstatic List<Tessellator.Triangle>
tessellate
(Polygon polygon, boolean checkSelfIntersections) static List<Tessellator.Triangle>
tessellate
(Polygon polygon, boolean checkSelfIntersections, Tessellator.Monitor monitor) static List<Tessellator.Triangle>
tessellate
(XYPolygon polygon, boolean checkSelfIntersections) static List<Tessellator.Triangle>
tessellate
(XYPolygon polygon, boolean checkSelfIntersections, Tessellator.Monitor monitor)
-
Field Details
-
VERTEX_THRESHOLD
private static final int VERTEX_THRESHOLD- See Also:
-
-
Constructor Details
-
Tessellator
private Tessellator()
-
-
Method Details
-
tessellate
public static List<Tessellator.Triangle> tessellate(Polygon polygon, boolean checkSelfIntersections) -
tessellate
public static List<Tessellator.Triangle> tessellate(Polygon polygon, boolean checkSelfIntersections, Tessellator.Monitor monitor) -
tessellate
public static List<Tessellator.Triangle> tessellate(XYPolygon polygon, boolean checkSelfIntersections) -
tessellate
public static List<Tessellator.Triangle> tessellate(XYPolygon polygon, boolean checkSelfIntersections, Tessellator.Monitor monitor) -
createDoublyLinkedList
private static final Tessellator.Node createDoublyLinkedList(double[] x, double[] y, GeoUtils.WindingOrder polyWindingOrder, boolean isGeo, int startIndex, GeoUtils.WindingOrder windingOrder) Creates a circular doubly linked list using polygon points. The order is governed by the specified winding order -
eliminateHoles
-
eliminateHoles
Links every hole into the outer loop, producing a single-ring polygon without holes. * -
eliminateHoles
private static final Tessellator.Node eliminateHoles(List<Tessellator.Node> holeList, Map<Tessellator.Node, ?> holeListPolygons, Tessellator.Node outerNode) -
eliminateHole
private static final void eliminateHole(Tessellator.Node holeNode, Tessellator.Node outerNode, double holeMinX, double holeMaxX, double holeMinY, double holeMaxY) Finds a bridge between vertices that connects a hole with an outer ring, and links it -
fetchHoleBridge
private static final Tessellator.Node fetchHoleBridge(Tessellator.Node holeNode, Tessellator.Node outerNode) David Eberly's algorithm for finding a bridge between a hole and outer polygonsee: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
-
fetchLeftmost
Finds the left-most hole of a polygon ring. * -
earcutLinkedList
private static final List<Tessellator.Triangle> earcutLinkedList(Object polygon, Tessellator.Node currEar, List<Tessellator.Triangle> tessellation, Tessellator.State state, boolean mortonOptimized, Tessellator.Monitor monitor, int depth) Main ear slicing loop which triangulates the vertices of a polygon, provided as a doubly-linked list. * -
isEar
Determines whether a polygon node forms a valid ear with adjacent nodes. * -
mortonIsEar
Uses morton code for speed to determine whether or a polygon node forms a valid ear w/ adjacent nodes -
cureLocalIntersections
private static final Tessellator.Node cureLocalIntersections(Tessellator.Node startNode, List<Tessellator.Triangle> tessellation, boolean mortonOptimized) Iterate through all polygon nodes and remove small local self-intersections * -
splitEarcut
private static final boolean splitEarcut(Object polygon, Tessellator.Node start, List<Tessellator.Triangle> tessellation, boolean mortonOptimized, Tessellator.Monitor monitor, int depth) Attempt to split a polygon and independently triangulate each side. Return true if the polygon was splitted * -
checkIntersection
Computes if edge defined by a and b overlaps with a polygon edge * -
mortonCheckIntersection
Uses morton code for speed to determine whether or not and edge defined by a and b overlaps with a polygon edge -
checkIntersectionPoint
-
isEdgeFromPolygon
Computes if edge defined by a and b overlaps with a polygon edge * -
isMortonEdgeFromPolygon
Uses morton code for speed to determine whether or not and edge defined by a and b overlaps with a polygon edge -
isPointInLine
private static boolean isPointInLine(Tessellator.Node a, Tessellator.Node b, Tessellator.Node point) -
isPointInLine
private static boolean isPointInLine(Tessellator.Node a, Tessellator.Node b, double lon, double lat) returns true if the lon, lat point is colinear w/ the provided a and b point -
splitPolygon
private static final Tessellator.Node splitPolygon(Tessellator.Node a, Tessellator.Node b, boolean edgeFromPolygon) Links two polygon vertices using a bridge. * -
isValidDiagonal
Determines whether a diagonal between two polygon nodes lies within a polygon interior. (This determines the validity of the ray.) * -
isCWPolygon
Determine whether the polygon defined between node start and node end is CW -
signedArea
Determine the signed area between node start and node end -
isLocallyInside
-
middleInsert
private static final boolean middleInsert(Tessellator.Node start, double x0, double y0, double x1, double y1) Determine whether the middle point of a polygon diagonal is contained within the polygon -
isIntersectingPolygon
private static final boolean isIntersectingPolygon(Tessellator.Node start, double x0, double y0, double x1, double y1) Determines if the diagonal of a polygon is intersecting with any polygon elements. * -
linesIntersect
public static final boolean linesIntersect(double aX0, double aY0, double aX1, double aY1, double bX0, double bY0, double bX1, double bY1) Determines whether two line segments intersect. * -
sortByMortonWithReset
Interlinks polygon nodes in Z-Order. It reset the values on the z values* -
sortByMorton
Interlinks polygon nodes in Z-Order. * -
tathamSort
Simon Tatham's doubly-linked list O(n log n) mergesort see: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html -
filterPoints
Eliminate colinear/duplicate points from the doubly linked list -
insertNode
private static final Tessellator.Node insertNode(double[] x, double[] y, int index, int vertexIndex, Tessellator.Node lastNode, boolean isGeo) Creates a node and optionally links it with a previous node in a circular doubly-linked list -
removeNode
Removes a node from the doubly linked list -
isVertexEquals
Determines if two point vertices are equal. * -
isVertexEquals
Determines if two point vertices are equal. * -
area
private static double area(double aX, double aY, double bX, double bY, double cX, double cY) Compute signed area of triangle -
pointInEar
private static boolean pointInEar(double x, double y, double ax, double ay, double bx, double by, double cx, double cy) Compute whether point is in a candidate ear -
pointInTriangle
public static boolean pointInTriangle(double x, double y, double ax, double ay, double bx, double by, double cx, double cy) compute whether the given x, y point is in a triangle; uses the winding order method -
pointInPolygon
public static final boolean pointInPolygon(List<Tessellator.Triangle> tessellation, double lat, double lon) Brute force compute if a point is in the polygon by traversing entire triangulation todo: speed this up using either binary tree or prefix coding (filtering by bounding box of triangle) -
getPoints
-
notifyMonitorSplit
private static void notifyMonitorSplit(int depth, Tessellator.Monitor monitor, Tessellator.Node searchNode, Tessellator.Node diagonalNode) -
notifyMonitorSplitEnd
-
notifyMonitor
private static void notifyMonitor(Tessellator.State state, int depth, Tessellator.Monitor monitor, Tessellator.Node start, List<Tessellator.Triangle> tessellation) -
notifyMonitor
private static void notifyMonitor(String status, Tessellator.Monitor monitor, Tessellator.Node start, List<Tessellator.Triangle> tessellation)
-