Class XTessellator


  • public final class XTessellator
    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  XTessellator.Node
      Circular Doubly-linked list used for polygon coordinates
      static class  XTessellator.Triangle
      Triangle in the tessellated mesh
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      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.
      static boolean pointInPolygon​(java.util.List<XTessellator.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
      static java.util.List<XTessellator.Triangle> tessellate​(org.apache.lucene.geo.Polygon polygon)
      Produces an array of vertices representing the triangulated result set of the Points array
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Method Detail

      • tessellate

        public static java.util.List<XTessellator.Triangle> tessellate​(org.apache.lucene.geo.Polygon polygon)
        Produces an array of vertices representing the triangulated result set of the Points array
      • linesIntersect

        public 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.
      • 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 boolean pointInPolygon​(java.util.List<XTessellator.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)