- java.lang.Object
-
- org.apache.lucene.geo.Tessellator
-
public final class Tessellator extends java.lang.Object
Computes a triangular mesh tessellation for a given polygon.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.
- Requires valid polygons:
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static interface
Tessellator.Monitor
Implementation of this interface will receive calls with internal data at each step of the triangulation algorithm.protected static class
Tessellator.Node
Circular Doubly-linked list used for polygon coordinatesprivate static class
Tessellator.State
state of the tessellated split - avoids recursionstatic class
Tessellator.Triangle
Triangle in the tessellated mesh
-
Field Summary
Fields Modifier and Type Field Description private static int
VERTEX_THRESHOLD
-
Constructor Summary
Constructors Modifier Constructor Description private
Tessellator()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description private 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
checkIntersectionPoint(Tessellator.Node a, Tessellator.Node b)
private static 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 Tessellator.Node
cureLocalIntersections(Tessellator.Node startNode, java.util.List<Tessellator.Triangle> tessellation, boolean mortonOptimized)
Iterate through all polygon nodes and remove small local self-intersections *private static java.util.List<Tessellator.Triangle>
earcutLinkedList(java.lang.Object polygon, Tessellator.Node currEar, java.util.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 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 Tessellator.Node
eliminateHoles(java.util.List<Tessellator.Node> holeList, java.util.Map<Tessellator.Node,?> holeListPolygons, Tessellator.Node outerNode)
private static Tessellator.Node
eliminateHoles(Polygon polygon, Tessellator.Node outerNode)
Links every hole into the outer loop, producing a single-ring polygon without holes.private static Tessellator.Node
eliminateHoles(XYPolygon polygon, Tessellator.Node outerNode)
private static Tessellator.Node
fetchHoleBridge(Tessellator.Node holeNode, Tessellator.Node outerNode)
David Eberly's algorithm for finding a bridge between a hole and outer polygonprivate static Tessellator.Node
fetchLeftmost(Tessellator.Node start)
Finds the left-most hole of a polygon ring.private static Tessellator.Node
filterPoints(Tessellator.Node start, Tessellator.Node end)
Eliminate colinear/duplicate points from the doubly linked listprivate static java.util.List<Point>
getPoints(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 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 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 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 boolean
isLocallyInside(Tessellator.Node a, Tessellator.Node b)
private static boolean
isMortonEdgeFromPolygon(Tessellator.Node a, Tessellator.Node b)
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 boolean
isValidDiagonal(Tessellator.Node a, Tessellator.Node b)
Determines whether a diagonal between two polygon nodes lies within a polygon interior.private static boolean
isVertexEquals(Tessellator.Node a, double x, double y)
Determines if two point vertices are equal.private static boolean
isVertexEquals(Tessellator.Node a, Tessellator.Node b)
Determines if two point vertices are equal.static 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 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 void
mortonCheckIntersection(Tessellator.Node a, Tessellator.Node b)
Uses morton code for speed to determine whether or not and edge defined by a and b overlaps with a polygon edgeprivate static boolean
mortonIsEar(Tessellator.Node ear)
Uses morton code for speed to determine whether or a polygon node forms a valid ear w/ adjacent nodesprivate static void
notifyMonitor(java.lang.String status, Tessellator.Monitor monitor, Tessellator.Node start, java.util.List<Tessellator.Triangle> tessellation)
private static void
notifyMonitor(Tessellator.State state, int depth, Tessellator.Monitor monitor, Tessellator.Node start, java.util.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 boolean
pointInPolygon(java.util.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 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 void
sortByMorton(Tessellator.Node start)
Interlinks polygon nodes in Z-Order.private static void
sortByMortonWithReset(Tessellator.Node start)
Interlinks polygon nodes in Z-Order.private static boolean
splitEarcut(java.lang.Object polygon, Tessellator.Node start, java.util.List<Tessellator.Triangle> tessellation, boolean mortonOptimized, Tessellator.Monitor monitor, int depth)
Attempt to split a polygon and independently triangulate each side.private static Tessellator.Node
splitPolygon(Tessellator.Node a, Tessellator.Node b, boolean edgeFromPolygon)
Links two polygon vertices using a bridge.private static 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 java.util.List<Tessellator.Triangle>
tessellate(Polygon polygon, boolean checkSelfIntersections)
static java.util.List<Tessellator.Triangle>
tessellate(Polygon polygon, boolean checkSelfIntersections, Tessellator.Monitor monitor)
static java.util.List<Tessellator.Triangle>
tessellate(XYPolygon polygon, boolean checkSelfIntersections)
static java.util.List<Tessellator.Triangle>
tessellate(XYPolygon polygon, boolean checkSelfIntersections, Tessellator.Monitor monitor)
-
-
-
Field Detail
-
VERTEX_THRESHOLD
private static final int VERTEX_THRESHOLD
- See Also:
- Constant Field Values
-
-
Method Detail
-
tessellate
public static java.util.List<Tessellator.Triangle> tessellate(Polygon polygon, boolean checkSelfIntersections)
-
tessellate
public static java.util.List<Tessellator.Triangle> tessellate(Polygon polygon, boolean checkSelfIntersections, Tessellator.Monitor monitor)
-
tessellate
public static java.util.List<Tessellator.Triangle> tessellate(XYPolygon polygon, boolean checkSelfIntersections)
-
tessellate
public static java.util.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
private static final Tessellator.Node eliminateHoles(XYPolygon polygon, Tessellator.Node outerNode)
-
eliminateHoles
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. *
-
eliminateHoles
private static final Tessellator.Node eliminateHoles(java.util.List<Tessellator.Node> holeList, java.util.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
-
getSharedVertex
private static Tessellator.Node getSharedVertex(Tessellator.Node polygon, Tessellator.Node vertex)
Check if the provided vertex is in the polygon and return it *
-
fetchLeftmost
private static final Tessellator.Node fetchLeftmost(Tessellator.Node start)
Finds the left-most hole of a polygon ring. *
-
earcutLinkedList
private static final java.util.List<Tessellator.Triangle> earcutLinkedList(java.lang.Object polygon, Tessellator.Node currEar, java.util.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
private static final boolean isEar(Tessellator.Node ear, boolean mortonOptimized)
Determines whether a polygon node forms a valid ear with adjacent nodes. *
-
mortonIsEar
private static final boolean mortonIsEar(Tessellator.Node ear)
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, java.util.List<Tessellator.Triangle> tessellation, boolean mortonOptimized)
Iterate through all polygon nodes and remove small local self-intersections *
-
splitEarcut
private static final boolean splitEarcut(java.lang.Object polygon, Tessellator.Node start, java.util.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
private static void checkIntersection(Tessellator.Node a, boolean isMorton)
Computes if edge defined by a and b overlaps with a polygon edge *
-
mortonCheckIntersection
private static final void mortonCheckIntersection(Tessellator.Node a, Tessellator.Node b)
Uses morton code for speed to determine whether or not and edge defined by a and b overlaps with a polygon edge
-
checkIntersectionPoint
private static void checkIntersectionPoint(Tessellator.Node a, Tessellator.Node b)
-
isEdgeFromPolygon
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 *
-
isMortonEdgeFromPolygon
private static final boolean isMortonEdgeFromPolygon(Tessellator.Node a, Tessellator.Node b)
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
private static boolean isValidDiagonal(Tessellator.Node a, Tessellator.Node b)
Determines whether a diagonal between two polygon nodes lies within a polygon interior. (This determines the validity of the ray.) *
-
isCWPolygon
private static boolean isCWPolygon(Tessellator.Node start, Tessellator.Node end)
Determine whether the polygon defined between node start and node end is CW
-
signedArea
private static double signedArea(Tessellator.Node start, Tessellator.Node end)
Determine the signed area between node start and node end
-
isLocallyInside
private static final boolean isLocallyInside(Tessellator.Node a, Tessellator.Node b)
-
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
private static final void sortByMortonWithReset(Tessellator.Node start)
Interlinks polygon nodes in Z-Order. It reset the values on the z values*
-
sortByMorton
private static final void sortByMorton(Tessellator.Node start)
Interlinks polygon nodes in Z-Order. *
-
tathamSort
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.html
-
filterPoints
private static final Tessellator.Node filterPoints(Tessellator.Node start, Tessellator.Node end)
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
private static final void removeNode(Tessellator.Node node, boolean edgeFromPolygon)
Removes a node from the doubly linked list
-
isVertexEquals
private static final boolean isVertexEquals(Tessellator.Node a, Tessellator.Node b)
Determines if two point vertices are equal. *
-
isVertexEquals
private static final boolean isVertexEquals(Tessellator.Node a, double x, double y)
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(java.util.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
private static java.util.List<Point> getPoints(Tessellator.Node start)
-
notifyMonitorSplit
private static void notifyMonitorSplit(int depth, Tessellator.Monitor monitor, Tessellator.Node searchNode, Tessellator.Node diagonalNode)
-
notifyMonitorSplitEnd
private static void notifyMonitorSplitEnd(int depth, Tessellator.Monitor monitor)
-
notifyMonitor
private static void notifyMonitor(Tessellator.State state, int depth, Tessellator.Monitor monitor, Tessellator.Node start, java.util.List<Tessellator.Triangle> tessellation)
-
notifyMonitor
private static void notifyMonitor(java.lang.String status, Tessellator.Monitor monitor, Tessellator.Node start, java.util.List<Tessellator.Triangle> tessellation)
-
-