Class EdgeTree

  • Direct Known Subclasses:
    Polygon2D

    public abstract class EdgeTree
    extends Object
    2D line/polygon geometry implementation represented as a balanced interval tree of edges.

    Construction takes O(n log n) time for sorting and tree construction. relate() are O(n), but for most practical lines and polygons are much faster than brute force.

    NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.
    • Field Detail

      • minLat

        public final double minLat
        minimum latitude of this geometry's bounding box area
      • maxLat

        public final double maxLat
        maximum latitude of this geometry's bounding box area
      • minLon

        public final double minLon
        minimum longitude of this geometry's bounding box area
      • maxLon

        public final double maxLon
        maximum longitude of this geometry's bounding box area
      • maxY

        protected double maxY
        maximum latitude of this component or any of its children
      • maxX

        protected double maxX
        maximum longitude of this component or any of its children
      • splitX

        protected boolean splitX
        which dimension was this node split on
      • tree

        protected final org.apache.lucene.geo.EdgeTree.Edge tree
        root node of edge tree
    • Constructor Detail

      • EdgeTree

        protected EdgeTree​(double minLat,
                           double maxLat,
                           double minLon,
                           double maxLon,
                           double[] lats,
                           double[] lons)
    • Method Detail

      • relateTriangle

        public PointValues.Relation relateTriangle​(double ax,
                                                   double ay,
                                                   double bx,
                                                   double by,
                                                   double cx,
                                                   double cy)
        Returns relation to the provided triangle
      • relate

        public PointValues.Relation relate​(double minLat,
                                           double maxLat,
                                           double minLon,
                                           double maxLon)
        Returns relation to the provided rectangle
      • componentRelate

        protected PointValues.Relation componentRelate​(double minLat,
                                                       double maxLat,
                                                       double minLon,
                                                       double maxLon)
      • componentRelateTriangle

        protected PointValues.Relation componentRelateTriangle​(double ax,
                                                               double ay,
                                                               double bx,
                                                               double by,
                                                               double cx,
                                                               double cy)
      • internalComponentRelate

        protected PointValues.Relation internalComponentRelate​(double minLat,
                                                               double maxLat,
                                                               double minLon,
                                                               double maxLon)
        Returns relation to the provided rectangle for this component
      • createTree

        protected static EdgeTree createTree​(EdgeTree[] components,
                                             int low,
                                             int high,
                                             boolean splitX)
        Creates tree from sorted components (with range low and high inclusive)