Package org.apache.lucene.geo

Class Tessellator

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.

Nested Class Summary

Nested Classes

Modifier and Type	Class	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

Field Summary

Fields

Modifier and Type	Field	Description
private static int	VERTEX_THRESHOLD

Constructor Summary

Constructors

Modifier	Constructor	Description
private	Tessellator()

Method Summary

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 triangle
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)	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 it
private 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 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	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 list
private static boolean	isCWPolygon(Tessellator.Node start, Tessellator.Node end)	Determine whether the polygon defined between node start and node end is CW
private 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 edge
private static boolean	isPointInLine(Tessellator.Node a, Tessellator.Node b, double lon, double lat)
private 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 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, boolean edgeFromPolygon)	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(java.lang.Object polygon, Tessellator.Node start, java.util.List<Tessellator.Triangle> tessellation, boolean mortonOptimized)	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.html
static java.util.List<Tessellator.Triangle>	tessellate(Polygon polygon)
static java.util.List<Tessellator.Triangle>	tessellate(XYPolygon polygon)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

VERTEX_THRESHOLD

private static final int VERTEX_THRESHOLD

See Also:

Constant Field Values

Constructor Detail

Tessellator

private Tessellator()

Method Detail

tessellate

public static final java.util.List<Tessellator.Triangle> tessellate(Polygon polygon)

tessellate

public static final java.util.List<Tessellator.Triangle> tessellate(XYPolygon polygon)

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 polygon see: 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)

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)

Attempt to split a polygon and independently triangulate each side. Return true if the polygon was splitted

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)

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 final 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

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)