Class EdgeTree


  • final class EdgeTree
    extends java.lang.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 byte FALSE
      helper bytes to signal if a point is on an edge, it is within the edge tree or disjoint
      (package private) EdgeTree left
      left child edge, or null
      (package private) double low
      min Y of this edge
      (package private) double max
      max Y of this edge or any children
      private static byte ON_EDGE  
      (package private) EdgeTree right
      right child edge, or null
      private static byte TRUE  
      (package private) double x1  
      (package private) double x2  
      (package private) double y1  
      (package private) double y2  
    • Constructor Summary

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

      All Methods Static Methods Instance Methods Concrete Methods 
      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 Detail

      • 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
      • right

        EdgeTree right
        right 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:
        Constant Field Values
    • Constructor Detail

      • EdgeTree

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

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