org.apache.lucene.geo

## Class EdgeTree

- java.lang.Object
- - org.apache.lucene.geo.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 Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected EdgeTree` | `left`
    `double` | `maxLat` maximum latitude of this geometry's bounding box area
    `double` | `maxLon` maximum longitude of this geometry's bounding box area
    `protected double` | `maxX` maximum longitude of this component or any of its children
    `protected double` | `maxY` maximum latitude of this component or any of its children
    `double` | `minLat` minimum latitude of this geometry's bounding box area
    `double` | `minLon` minimum longitude of this geometry's bounding box area
    `protected EdgeTree` | `right`
    `protected boolean` | `splitX` which dimension was this node split on
    `protected org.apache.lucene.geo.EdgeTree.Edge` | `tree` root node of edge tree

  - ### Constructor Summary

    Constructors
    Modifier | Constructor and Description
    --- | ---
    `protected` | `EdgeTree(double minLat, double maxLat, double minLon, double maxLon, double[] lats, double[] lons)`

  - ### Method Summary

    All Methods Static Methods Instance Methods Abstract Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `protected abstract PointValues.Relation` | `componentRelate(double minLat, double maxLat, double minLon, double maxLon)` Returns relation to the provided rectangle for this component
    `protected abstract PointValues.Relation` | `componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy)` Returns relation to the provided triangle for this component
    `protected static EdgeTree` | `createTree(EdgeTree[] components, int low, int high, boolean splitX)` Creates tree from sorted components (with range low and high inclusive)
    `protected PointValues.Relation` | `internalComponentRelate(double minLat, double maxLat, double minLon, double maxLon)` Returns relation to the provided rectangle for this component
    `protected 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
    `PointValues.Relation` | `relate(double minLat, double maxLat, double minLon, double maxLon)` Returns relation to the provided rectangle
    `PointValues.Relation` | `relateTriangle(double ax, double ay, double bx, double by, double cx, double cy)` Returns relation to the provided triangle

    - ### Methods inherited from class java.lang.Object

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

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

    - #### left

          protected EdgeTree left

    - #### right

          protected EdgeTree right

    - #### 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 abstract PointValues.Relation componentRelate(double minLat,
                                                                  double maxLat,
                                                                  double minLon,
                                                                  double maxLon)

      Returns relation to the provided rectangle for this component

    - #### componentRelateTriangle

          protected abstract PointValues.Relation componentRelateTriangle(double ax,
                                                                          double ay,
                                                                          double bx,
                                                                          double by,
                                                                          double cx,
                                                                          double cy)

      Returns relation to the provided triangle for this component

    - #### 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)

    - #### pointInTriangle

          protected 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

Copyright © 2000-2019 Apache Software Foundation. All Rights Reserved.