Module org.apache.lucene.core
Package org.apache.lucene.geo

Class Tessellator

java.lang.Object
org.apache.lucene.geo.Tessellator
public final class Tessellator extends 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.

  • Field Details

  • 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

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

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

      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(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 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, List<Tessellator.Triangle> tessellation)

    • notifyMonitor

      private static void notifyMonitor(String status, Tessellator.Monitor monitor, Tessellator.Node start, List<Tessellator.Triangle> tessellation)