Class 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.

    • Constructor Detail

      • Tessellator

        private Tessellator()
    • Method Detail

      • 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​(Polygon polygon,
                                                             Tessellator.Node outerNode)
        Links every hole into the outer loop, producing a single-ring polygon without holes. *
      • 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

      • 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
      • 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,
                                             double lon,
                                             double lat)
        returns true if the lon, lat point is colinear w/ the provided a and b point
      • 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
      • 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
      • 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,
                                                    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)
      • notifyMonitorSplitEnd

        private static void notifyMonitorSplitEnd​(int depth,
                                                  Tessellator.Monitor monitor)