Class EdgeTree

java.lang.Object
org.apache.lucene.geo.EdgeTree

final class EdgeTree extends Object
Internal tree node: represents geometry edge from [x1, y1] to [x2, y2]. The sort value is low, which is the minimum y of the edge. max stores the maximum y of this edge or any children.

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

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final byte
    helper bytes to signal if a point is on an edge, it is within the edge tree or disjoint
    (package private) EdgeTree
    left child edge, or null
    (package private) final double
    min Y of this edge
    (package private) double
    max Y of this edge or any children
    private static final byte
     
    (package private) EdgeTree
    right child edge, or null
    private static final byte
     
    (package private) final double
     
    (package private) final double
     
    (package private) final double
     
    (package private) final double
     
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
    EdgeTree(double x1, double y1, double x2, double y2, double low, double max)
     
  • Method Summary

    Modifier and Type
    Method
    Description
    protected boolean
    contains(double x, double y)
    Returns true if the point is on an edge or crosses the edge subtree an odd number of times.
    private byte
    containsPnPoly(double x, double y)
    Returns byte 0x00 if the point crosses this edge subtree an even number of times.
    (package private) static EdgeTree
    createTree(double[] x, double[] y)
    Creates an edge interval tree from a set of geometry vertices.
    private static EdgeTree
    createTree(EdgeTree[] edges, int low, int high)
    Creates tree from sorted edges (with range low and high inclusive)
    (package private) boolean
    crossesBox(double minX, double maxX, double minY, double maxY, boolean includeBoundary)
    Returns true if the box crosses any edge in this edge subtree
    (package private) boolean
    crossesLine(double minX, double maxX, double minY, double maxY, double a2x, double a2y, double b2x, double b2y, boolean includeBoundary)
    Returns true if the line crosses any edge in this edge subtree
    (package private) boolean
    crossesTriangle(double minX, double maxX, double minY, double maxY, double ax, double ay, double bx, double by, double cx, double cy, boolean includeBoundary)
    Returns true if the triangle crosses any edge in this edge subtree
    (package private) boolean
    isPointOnLine(double x, double y)
    returns true if the provided x, y point lies on the line

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • y1

      final double y1
    • y2

      final double y2
    • x1

      final double x1
    • x2

      final double x2
    • low

      final double low
      min Y of this edge
    • max

      double max
      max Y of this edge or any children
    • left

      EdgeTree left
      left child edge, or null
    • FALSE

      private static final byte FALSE
      helper bytes to signal if a point is on an edge, it is within the edge tree or disjoint
      See Also:
    • TRUE

      private static final byte TRUE
      See Also:
    • ON_EDGE

      private static final byte ON_EDGE
      See Also:
  • Constructor Details

    • EdgeTree

      private EdgeTree(double x1, double y1, double x2, double y2, double low, double max)
  • Method Details

    • contains

      protected boolean contains(double x, double y)
      Returns true if the point is on an edge or crosses the edge subtree an odd number of times.
    • containsPnPoly

      private byte containsPnPoly(double x, double y)
      Returns byte 0x00 if the point crosses this edge subtree an even number of times. Returns byte 0x01 if the point crosses this edge subtree an odd number of times. Returns byte 0x02 if the point is on one of the edges.

      See https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html for more information.

    • isPointOnLine

      boolean isPointOnLine(double x, double y)
      returns true if the provided x, y point lies on the line
    • crossesTriangle

      boolean crossesTriangle(double minX, double maxX, double minY, double maxY, double ax, double ay, double bx, double by, double cx, double cy, boolean includeBoundary)
      Returns true if the triangle crosses any edge in this edge subtree
    • crossesBox

      boolean crossesBox(double minX, double maxX, double minY, double maxY, boolean includeBoundary)
      Returns true if the box crosses any edge in this edge subtree
    • crossesLine

      boolean crossesLine(double minX, double maxX, double minY, double maxY, double a2x, double a2y, double b2x, double b2y, boolean includeBoundary)
      Returns true if the line crosses any edge in this edge subtree
    • createTree

      static EdgeTree createTree(double[] x, double[] y)
      Creates an edge interval tree from a set of geometry vertices.
      Returns:
      root node of the tree.
    • createTree

      private static EdgeTree createTree(EdgeTree[] edges, int low, int high)
      Creates tree from sorted edges (with range low and high inclusive)