public final class Tessellator
extends java.lang.Object
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:
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.
Modifier and Type | Class and Description |
---|---|
protected static class |
Tessellator.Node
Circular Doubly-linked list used for polygon coordinates
|
private static class |
Tessellator.State
state of the tessellated split - avoids recursion
|
static class |
Tessellator.Triangle
Triangle in the tessellated mesh
|
Modifier and Type | Field and Description |
---|---|
private static int |
VERTEX_THRESHOLD |
Modifier | Constructor and Description |
---|---|
private |
Tessellator() |
Modifier and Type | Method and Description |
---|---|
private static double |
area(double aX,
double aY,
double bX,
double bY,
double cX,
double cY)
Compute signed area of triangle
|
private static Tessellator.Node |
createDoublyLinkedList(Polygon polygon,
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)
Iterate through all polygon nodes and remove small local self-intersections
|
private static java.util.List<Tessellator.Triangle> |
earcutLinkedList(Tessellator.Node currEar,
java.util.List<Tessellator.Triangle> tessellation,
Tessellator.State state,
boolean mortonOptimized)
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)
Finds a bridge between vertices that connects a hole with an outer ring, and links it
|
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 |
fetchHoleBridge(Tessellator.Node holeNode,
Tessellator.Node outerNode)
David Eberly's algorithm for finding a bridge between a hole and outer polygon
see: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
|
private 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 list
|
private static Tessellator.Node |
insertNode(Polygon polygon,
int index,
int vertexIndex,
Tessellator.Node lastNode)
Creates a node and optionally links it with a previous node in a circular doubly-linked list
|
private static boolean |
isEar(Tessellator.Node ear,
boolean mortonOptimized)
Determines whether a polygon node forms a valid ear with adjacent nodes.
|
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 |
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 polygon
|
private static boolean |
mortonIsEar(Tessellator.Node ear)
Uses morton code for speed to determine whether or a polygon node forms a valid ear w/ adjacent nodes
|
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
|
static 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 method
|
private static void |
removeNode(Tessellator.Node node)
Removes a node from the doubly linked list
|
private 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(Tessellator.Node start,
java.util.List<Tessellator.Triangle> tessellation,
boolean mortonIndexed)
Attempt to split a polygon and independently triangulate each side.
|
private static Tessellator.Node |
splitPolygon(Tessellator.Node a,
Tessellator.Node b)
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.html
|
static java.util.List<Tessellator.Triangle> |
tessellate(Polygon polygon)
Produces an array of vertices representing the triangulated result set of the Points array
|
private static final int VERTEX_THRESHOLD
public static final java.util.List<Tessellator.Triangle> tessellate(Polygon polygon)
private static final Tessellator.Node createDoublyLinkedList(Polygon polygon, int startIndex, GeoUtils.WindingOrder windingOrder)
private static final Tessellator.Node eliminateHoles(Polygon polygon, Tessellator.Node outerNode)
private static final void eliminateHole(Tessellator.Node holeNode, Tessellator.Node outerNode)
private static final Tessellator.Node fetchHoleBridge(Tessellator.Node holeNode, Tessellator.Node outerNode)
private static final Tessellator.Node fetchLeftmost(Tessellator.Node start)
private static final java.util.List<Tessellator.Triangle> earcutLinkedList(Tessellator.Node currEar, java.util.List<Tessellator.Triangle> tessellation, Tessellator.State state, boolean mortonOptimized)
private static final boolean isEar(Tessellator.Node ear, boolean mortonOptimized)
private static final boolean mortonIsEar(Tessellator.Node ear)
private static final Tessellator.Node cureLocalIntersections(Tessellator.Node startNode, java.util.List<Tessellator.Triangle> tessellation)
private static final boolean splitEarcut(Tessellator.Node start, java.util.List<Tessellator.Triangle> tessellation, boolean mortonIndexed)
private static final Tessellator.Node splitPolygon(Tessellator.Node a, Tessellator.Node b)
private static final boolean isValidDiagonal(Tessellator.Node a, Tessellator.Node b)
private static final boolean isLocallyInside(Tessellator.Node a, Tessellator.Node b)
private static final boolean middleInsert(Tessellator.Node start, double x0, double y0, double x1, double y1)
private static final boolean isIntersectingPolygon(Tessellator.Node start, double x0, double y0, double x1, double y1)
public static final boolean linesIntersect(double aX0, double aY0, double aX1, double aY1, double bX0, double bY0, double bX1, double bY1)
private static final void sortByMortonWithReset(Tessellator.Node start)
private static final void sortByMorton(Tessellator.Node start)
private static final void tathamSort(Tessellator.Node list)
private static final Tessellator.Node filterPoints(Tessellator.Node start, Tessellator.Node end)
private static final Tessellator.Node insertNode(Polygon polygon, int index, int vertexIndex, Tessellator.Node lastNode)
private static final void removeNode(Tessellator.Node node)
private static final boolean isVertexEquals(Tessellator.Node a, Tessellator.Node b)
private static final boolean isVertexEquals(Tessellator.Node a, double x, double y)
private static double area(double aX, double aY, double bX, double bY, double cX, double cY)
private static boolean pointInEar(double x, double y, double ax, double ay, double bx, double by, double cx, double cy)
public static boolean pointInTriangle(double x, double y, double ax, double ay, double bx, double by, double cx, double cy)
public static final boolean pointInPolygon(java.util.List<Tessellator.Triangle> tessellation, double lat, double lon)