Class ComponentTree

  • All Implemented Interfaces:
    Component2D

    final class ComponentTree
    extends java.lang.Object
    implements Component2D
    2D multi-component geometry implementation represented as an interval tree of components.

    Construction takes O(n log n) time for sorting and tree construction.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private Component2D component
      root node of edge tree
      private Component2D left  
      private double maxX
      maximum X of this geometry's bounding box area
      private double maxY
      maximum Y of this geometry's bounding box area
      private double minX
      minimum X of this geometry's bounding box area
      private double minY
      minimum Y of this geometry's bounding box area
      private Component2D right  
      private boolean splitX
      which dimension was this node split on
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private ComponentTree​(Component2D component, boolean splitX)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean contains​(double x, double y)
      relates this component2D with a point
      boolean containsLine​(double minX, double maxX, double minY, double maxY, double aX, double aY, double bX, double bY)
      return true if this component2D contains the provided line
      boolean containsTriangle​(double minX, double maxX, double minY, double maxY, double aX, double aY, double bX, double bY, double cX, double cY)
      return true if this component2D contains the provided triangle
      (package private) static Component2D create​(Component2D[] components)
      Creates tree from provided components
      private static ComponentTree createTree​(Component2D[] components, int low, int high, boolean splitX)
      Creates tree from sorted components (with range low and high inclusive)
      double getMaxX()
      max X value for the component
      double getMaxY()
      max Y value for the component
      double getMinX()
      min X value for the component
      double getMinY()
      min Y value for the component
      boolean intersectsLine​(double minX, double maxX, double minY, double maxY, double aX, double aY, double bX, double bY)
      return true if this component2D intersects the provided line
      boolean intersectsTriangle​(double minX, double maxX, double minY, double maxY, double aX, double aY, double bX, double bY, double cX, double cY)
      return true if this component2D intersects the provided triangle
      PointValues.Relation relate​(double minX, double maxX, double minY, double maxY)
      relates this component2D with a bounding box
      Component2D.WithinRelation withinLine​(double minX, double maxX, double minY, double maxY, double aX, double aY, boolean ab, double bX, double bY)
      Compute the within relation of this component2D with a line
      Component2D.WithinRelation withinPoint​(double x, double y)
      Compute the within relation of this component2D with a point
      Component2D.WithinRelation withinTriangle​(double minX, double maxX, double minY, double maxY, double aX, double aY, boolean ab, double bX, double bY, boolean bc, double cX, double cY, boolean ca)
      Compute the within relation of this component2D with a triangle
      • Methods inherited from class java.lang.Object

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

      • minY

        private double minY
        minimum Y of this geometry's bounding box area
      • maxY

        private double maxY
        maximum Y of this geometry's bounding box area
      • minX

        private double minX
        minimum X of this geometry's bounding box area
      • maxX

        private double maxX
        maximum X of this geometry's bounding box area
      • splitX

        private final boolean splitX
        which dimension was this node split on
      • component

        private final Component2D component
        root node of edge tree
    • Constructor Detail

      • ComponentTree

        private ComponentTree​(Component2D component,
                              boolean splitX)
    • Method Detail

      • getMinX

        public double getMinX()
        Description copied from interface: Component2D
        min X value for the component
        Specified by:
        getMinX in interface Component2D
      • getMaxX

        public double getMaxX()
        Description copied from interface: Component2D
        max X value for the component
        Specified by:
        getMaxX in interface Component2D
      • getMinY

        public double getMinY()
        Description copied from interface: Component2D
        min Y value for the component
        Specified by:
        getMinY in interface Component2D
      • getMaxY

        public double getMaxY()
        Description copied from interface: Component2D
        max Y value for the component
        Specified by:
        getMaxY in interface Component2D
      • contains

        public boolean contains​(double x,
                                double y)
        Description copied from interface: Component2D
        relates this component2D with a point
        Specified by:
        contains in interface Component2D
      • intersectsLine

        public boolean intersectsLine​(double minX,
                                      double maxX,
                                      double minY,
                                      double maxY,
                                      double aX,
                                      double aY,
                                      double bX,
                                      double bY)
        Description copied from interface: Component2D
        return true if this component2D intersects the provided line
        Specified by:
        intersectsLine in interface Component2D
      • intersectsTriangle

        public boolean intersectsTriangle​(double minX,
                                          double maxX,
                                          double minY,
                                          double maxY,
                                          double aX,
                                          double aY,
                                          double bX,
                                          double bY,
                                          double cX,
                                          double cY)
        Description copied from interface: Component2D
        return true if this component2D intersects the provided triangle
        Specified by:
        intersectsTriangle in interface Component2D
      • containsLine

        public boolean containsLine​(double minX,
                                    double maxX,
                                    double minY,
                                    double maxY,
                                    double aX,
                                    double aY,
                                    double bX,
                                    double bY)
        Description copied from interface: Component2D
        return true if this component2D contains the provided line
        Specified by:
        containsLine in interface Component2D
      • containsTriangle

        public boolean containsTriangle​(double minX,
                                        double maxX,
                                        double minY,
                                        double maxY,
                                        double aX,
                                        double aY,
                                        double bX,
                                        double bY,
                                        double cX,
                                        double cY)
        Description copied from interface: Component2D
        return true if this component2D contains the provided triangle
        Specified by:
        containsTriangle in interface Component2D
      • withinLine

        public Component2D.WithinRelation withinLine​(double minX,
                                                     double maxX,
                                                     double minY,
                                                     double maxY,
                                                     double aX,
                                                     double aY,
                                                     boolean ab,
                                                     double bX,
                                                     double bY)
        Description copied from interface: Component2D
        Compute the within relation of this component2D with a line
        Specified by:
        withinLine in interface Component2D
      • withinTriangle

        public Component2D.WithinRelation withinTriangle​(double minX,
                                                         double maxX,
                                                         double minY,
                                                         double maxY,
                                                         double aX,
                                                         double aY,
                                                         boolean ab,
                                                         double bX,
                                                         double bY,
                                                         boolean bc,
                                                         double cX,
                                                         double cY,
                                                         boolean ca)
        Description copied from interface: Component2D
        Compute the within relation of this component2D with a triangle
        Specified by:
        withinTriangle in interface Component2D
      • relate

        public PointValues.Relation relate​(double minX,
                                           double maxX,
                                           double minY,
                                           double maxY)
        Description copied from interface: Component2D
        relates this component2D with a bounding box
        Specified by:
        relate in interface Component2D
      • createTree

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