RegionBSPTree1D.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.geometry.euclidean.oned;

  19. import java.util.ArrayList;
  20. import java.util.Comparator;
  21. import java.util.List;
  22. import java.util.Objects;
  23. import java.util.function.BiConsumer;

  25. import org.apache.commons.geometry.core.RegionLocation;
  26. import org.apache.commons.geometry.core.Transform;
  27. import org.apache.commons.geometry.core.partitioning.Hyperplane;
  28. import org.apache.commons.geometry.core.partitioning.Split;
  29. import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
  30. import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;
  31. import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;

  33. /** Binary space partitioning (BSP) tree representing a region in one dimensional
  34.  * Euclidean space.
  35.  */
  36. public final class RegionBSPTree1D extends AbstractRegionBSPTree<Vector1D, RegionBSPTree1D.RegionNode1D> {
  37.     /** Comparator used to sort BoundaryPairs by ascending location.  */
  38.     private static final Comparator<BoundaryPair> BOUNDARY_PAIR_COMPARATOR =
  39.             Comparator.comparingDouble(BoundaryPair::getMinValue);

  41.     /** Create a new, empty region.
  42.      */
  43.     public RegionBSPTree1D() {
  44.         this(false);
  45.     }

  47.     /** Create a new region. If {@code full} is true, then the region will
  48.      * represent the entire number line. Otherwise, it will be empty.
  49.      * @param full whether or not the region should contain the entire
  50.      *      number line or be empty
  51.      */
  52.     public RegionBSPTree1D(final boolean full) {
  53.         super(full);
  54.     }

  56.     /** Return a deep copy of this instance.
  57.      * @return a deep copy of this instance.
  58.      * @see #copy(org.apache.commons.geometry.core.partitioning.bsp.BSPTree)
  59.      */
  60.     public RegionBSPTree1D copy() {
  61.         final RegionBSPTree1D result = RegionBSPTree1D.empty();
  62.         result.copy(this);

  64.         return result;
  65.     }

  67.     /** Add an interval to this region. The resulting region will be the
  68.      * union of the interval and the region represented by this instance.
  69.      * @param interval the interval to add
  70.      */
  71.     public void add(final Interval interval) {
  72.         union(intervalToTree(interval));
  73.     }

  75.     /** Classify a point location with respect to the region.
  76.      * @param x the point to classify
  77.      * @return the location of the point with respect to the region
  78.      * @see #classify(org.apache.commons.geometry.core.Point)
  79.      */
  80.     public RegionLocation classify(final double x) {
  81.         return classify(Vector1D.of(x));
  82.     }

  84.     /** Return true if the given point location is on the inside or boundary
  85.      * of the region.
  86.      * @param x the location to test
  87.      * @return true if the location is on the inside or boundary of the region
  88.      * @see #contains(org.apache.commons.geometry.core.Point)
  89.      */
  90.     public boolean contains(final double x) {
  91.         return contains(Vector1D.of(x));
  92.     }

  94.     /** {@inheritDoc}
  95.     *
  96.     *  <p>This method simply returns 0 because boundaries in one dimension do not
  97.     *  have any size.</p>
  98.     */
  99.     @Override
  100.     public double getBoundarySize() {
  101.         return 0;
  102.     }

  104.     /** {@inheritDoc} */
  105.     @Override
  106.     public Vector1D project(final Vector1D pt) {
  107.         // use our custom projector so that we can disambiguate points that are
  108.         // actually equidistant from the target point
  109.         final BoundaryProjector1D projector = new BoundaryProjector1D(pt);
  110.         accept(projector);

  112.         return projector.getProjected();
  113.     }

  115.     /** {@inheritDoc}
  116.      *
  117.      * <p>When splitting trees representing single points with a splitter lying directly
  118.      * on the point, the result point is placed on one side of the splitter based on its
  119.      * orientation: if the splitter is positive-facing, the point is placed on the plus
  120.      * side of the split; if the splitter is negative-facing, the point is placed on the
  121.      * minus side of the split.</p>
  122.      */
  123.     @Override
  124.     public Split<RegionBSPTree1D> split(final Hyperplane<Vector1D> splitter) {
  125.         return split(splitter, RegionBSPTree1D.empty(), RegionBSPTree1D.empty());
  126.     }

  128.     /** Get the minimum value on the inside of the region; returns {@link Double#NEGATIVE_INFINITY}
  129.      * if the region does not have a minimum value and {@link Double#POSITIVE_INFINITY} if
  130.      * the region is empty.
  131.      * @return the minimum value on the inside of the region
  132.      */
  133.     public double getMin() {
  134.         double min = Double.POSITIVE_INFINITY;

  136.         RegionNode1D node = getRoot();
  137.         OrientedPoint pt;

  139.         while (!node.isLeaf()) {
  140.             pt = (OrientedPoint) node.getCutHyperplane();

  142.             min = pt.getLocation();
  143.             node = pt.isPositiveFacing() ? node.getMinus() : node.getPlus();
  144.         }

  146.         return node.isInside() ? Double.NEGATIVE_INFINITY : min;
  147.     }

  149.     /** Get the maximum value on the inside of the region; returns {@link Double#POSITIVE_INFINITY}
  150.      * if the region does not have a maximum value and {@link Double#NEGATIVE_INFINITY} if
  151.      * the region is empty.
  152.      * @return the maximum value on the inside of the region
  153.      */
  154.     public double getMax() {
  155.         double max = Double.NEGATIVE_INFINITY;

  157.         RegionNode1D node = getRoot();
  158.         OrientedPoint pt;

  160.         while (!node.isLeaf()) {
  161.             pt = (OrientedPoint) node.getCutHyperplane();

  163.             max = pt.getLocation();
  164.             node = pt.isPositiveFacing() ? node.getPlus() : node.getMinus();
  165.         }

  167.         return node.isInside() ? Double.POSITIVE_INFINITY : max;
  168.     }

  170.     /** Convert the region represented by this tree into a list of separate
  171.      * {@link Interval}s, arranged in order of ascending min value.
  172.      * @return list of {@link Interval}s representing this region in order of
  173.      *      ascending min value
  174.      */
  175.     public List<Interval> toIntervals() {

  177.         final List<BoundaryPair> boundaryPairs = new ArrayList<>();

  179.         visitInsideIntervals((min, max) -> boundaryPairs.add(new BoundaryPair(min, max)));
  180.         boundaryPairs.sort(BOUNDARY_PAIR_COMPARATOR);

  182.         final List<Interval> intervals = new ArrayList<>();

  184.         BoundaryPair start = null;
  185.         BoundaryPair end = null;

  187.         for (final BoundaryPair current : boundaryPairs) {
  188.             if (start == null) {
  189.                 start = current;
  190.                 end = current;
  191.             } else if (Objects.equals(end.getMax(), current.getMin())) {
  192.                 // these intervals should be merged
  193.                 end = current;
  194.             } else {
  195.                 // these intervals should not be merged
  196.                 intervals.add(createInterval(start, end));

  198.                 // queue up the next pair
  199.                 start = current;
  200.                 end = current;
  201.             }
  202.         }

  204.         if (start != null) {
  205.             intervals.add(createInterval(start, end));
  206.         }

  208.         return intervals;
  209.     }

  211.     /** Create an interval instance from the min boundary from the start boundary pair and
  212.      * the max boundary from the end boundary pair. The hyperplane directions are adjusted
  213.      * as needed.
  214.      * @param start starting boundary pair
  215.      * @param end ending boundary pair
  216.      * @return an interval created from the min boundary of the given start pair and the
  217.      *      max boundary from the given end pair
  218.      */
  219.     private Interval createInterval(final BoundaryPair start, final BoundaryPair end) {
  220.         OrientedPoint min = start.getMin();
  221.         OrientedPoint max = end.getMax();

  223.         // flip the hyperplanes if needed since there's no
  224.         // guarantee that the inside will be on the minus side
  225.         // of the hyperplane (for example, if the region is complemented)

  227.         if (min != null && min.isPositiveFacing()) {
  228.             min = min.reverse();
  229.         }
  230.         if (max != null && !max.isPositiveFacing()) {
  231.             max = max.reverse();
  232.         }

  234.         return Interval.of(min, max);
  235.     }

  237.     /** Compute the min/max intervals for all interior convex regions in the tree and
  238.      * pass the values to the given visitor function.
  239.      * @param visitor the object that will receive the calculated min and max boundary for each
  240.      *      insides node's convex region
  241.      */
  242.     private void visitInsideIntervals(final BiConsumer<OrientedPoint, OrientedPoint> visitor) {
  243.         for (final RegionNode1D node : nodes()) {
  244.             if (node.isInside()) {
  245.                 node.visitNodeInterval(visitor);
  246.             }
  247.         }
  248.     }

  250.     /** {@inheritDoc} */
  251.     @Override
  252.     protected RegionNode1D createNode() {
  253.         return new RegionNode1D(this);
  254.     }

  256.     /** {@inheritDoc} */
  257.     @Override
  258.     protected RegionSizeProperties<Vector1D> computeRegionSizeProperties() {
  259.         final RegionSizePropertiesVisitor visitor = new RegionSizePropertiesVisitor();

  261.         visitInsideIntervals(visitor);

  263.         return visitor.getRegionSizeProperties();
  264.     }

  266.     /** Returns true if the given transform would result in a swapping of the interior
  267.      * and exterior of the region if applied.
  268.      *
  269.      * <p>This method always returns false since no swapping of this kind occurs in
  270.      * 1D.</p>
  271.      */
  272.     @Override
  273.     protected boolean swapsInsideOutside(final Transform<Vector1D> transform) {
  274.         return false;
  275.     }

  277.     /** Return a new {@link RegionBSPTree1D} instance containing the entire space.
  278.      * @return a new {@link RegionBSPTree1D} instance containing the entire space
  279.      */
  280.     public static RegionBSPTree1D full() {
  281.         return new RegionBSPTree1D(true);
  282.     }

  284.     /** Return a new, empty {@link RegionBSPTree1D} instance.
  285.      * @return a new, empty {@link RegionBSPTree1D} instance
  286.      */
  287.     public static RegionBSPTree1D empty() {
  288.         return new RegionBSPTree1D(false);
  289.     }

  291.     /** Construct a new instance from one or more intervals. The returned tree
  292.      * represents the same region as the union of all of the input intervals.
  293.      * @param interval the input interval
  294.      * @param more additional intervals to add to the region
  295.      * @return a new instance representing the same region as the union
  296.      *      of all of the given intervals
  297.      */
  298.     public static RegionBSPTree1D from(final Interval interval, final Interval... more) {
  299.         final RegionBSPTree1D tree = intervalToTree(interval);

  301.         for (final Interval additional : more) {
  302.             tree.add(additional);
  303.         }

  305.         return tree;
  306.     }

  308.     /** Construct a new instance from the given collection of intervals.
  309.      * @param intervals the intervals to populate the region with
  310.      * @return a new instance constructed from the given collection of intervals
  311.      */
  312.     public static RegionBSPTree1D from(final Iterable<Interval> intervals) {
  313.         final RegionBSPTree1D tree = new RegionBSPTree1D(false);

  315.         for (final Interval interval : intervals) {
  316.             tree.add(interval);
  317.         }

  319.         return tree;
  320.     }

  322.     /** Return a tree representing the same region as the given interval.
  323.      * @param interval interval to create a tree from
  324.      * @return a tree representing the same region as the given interval
  325.      */
  326.     private static RegionBSPTree1D intervalToTree(final Interval interval) {
  327.         final OrientedPoint minBoundary = interval.getMinBoundary();
  328.         final OrientedPoint maxBoundary = interval.getMaxBoundary();

  330.         final RegionBSPTree1D tree = full();

  332.         RegionNode1D node = tree.getRoot();

  334.         if (minBoundary != null) {
  335.             tree.setNodeCut(node, minBoundary.span(), tree.getSubtreeInitializer(RegionCutRule.MINUS_INSIDE));

  337.             node = node.getMinus();
  338.         }

  340.         if (maxBoundary != null) {
  341.             tree.setNodeCut(node, maxBoundary.span(), tree.getSubtreeInitializer(RegionCutRule.MINUS_INSIDE));
  342.         }

  344.         return tree;
  345.     }

  347.     /** BSP tree node for one dimensional Euclidean space.
  348.      */
  349.     public static final class RegionNode1D extends AbstractRegionBSPTree.AbstractRegionNode<Vector1D, RegionNode1D> {
  350.         /** Simple constructor.
  351.          * @param tree the owning tree instance
  352.          */
  353.         private RegionNode1D(final AbstractBSPTree<Vector1D, RegionNode1D> tree) {
  354.             super(tree);
  355.         }

  357.         /** Get the region represented by this node. The returned region contains
  358.          * the entire area contained in this node, regardless of the attributes of
  359.          * any child nodes.
  360.          * @return the region represented by this node
  361.          */
  362.         public Interval getNodeRegion() {
  363.             final NodeRegionVisitor visitor = new NodeRegionVisitor();
  364.             visitNodeInterval(visitor);

  366.             return visitor.getInterval();
  367.         }

  369.         /** Determine the min/max boundaries for the convex region represented by this node and pass
  370.          * the values to the visitor function.
  371.          * @param visitor the object that will receive the min and max boundaries for the node's
  372.          *      convex region
  373.          */
  374.         private void visitNodeInterval(final BiConsumer<? super OrientedPoint, ? super OrientedPoint> visitor) {
  375.             OrientedPoint min = null;
  376.             OrientedPoint max = null;

  378.             OrientedPoint pt;
  379.             RegionNode1D child = this;
  380.             RegionNode1D parent;

  382.             while ((min == null || max == null) && (parent = child.getParent()) != null) {
  383.                 pt = (OrientedPoint) parent.getCutHyperplane();

  385.                 if ((pt.isPositiveFacing() && child.isMinus()) ||
  386.                         (!pt.isPositiveFacing() && child.isPlus())) {

  388.                     if (max == null) {
  389.                         max = pt;
  390.                     }
  391.                 } else if (min == null) {
  392.                     min = pt;
  393.                 }

  395.                 child = parent;
  396.             }

  398.             visitor.accept(min, max);
  399.         }

  401.         /** {@inheritDoc} */
  402.         @Override
  403.         protected RegionNode1D getSelf() {
  404.             return this;
  405.         }
  406.     }

  408.     /** Internal class containing pairs of interval boundaries.
  409.      */
  410.     private static final class BoundaryPair {

  412.         /** The min boundary. */
  413.         private final OrientedPoint min;

  415.         /** The max boundary. */
  416.         private final OrientedPoint max;

  418.         /** Simple constructor.
  419.          * @param min min boundary hyperplane
  420.          * @param max max boundary hyperplane
  421.          */
  422.         BoundaryPair(final OrientedPoint min, final OrientedPoint max) {
  423.             this.min = min;
  424.             this.max = max;
  425.         }

  427.         /** Get the minimum boundary hyperplane.
  428.          * @return the minimum boundary hyperplane.
  429.          */
  430.         public OrientedPoint getMin() {
  431.             return min;
  432.         }

  434.         /** Get the maximum boundary hyperplane.
  435.          * @return the maximum boundary hyperplane.
  436.          */
  437.         public OrientedPoint getMax() {
  438.             return max;
  439.         }

  441.         /** Get the minimum value of the interval or {@link Double#NEGATIVE_INFINITY}
  442.          * if no minimum value exists.
  443.          * @return the minimum value of the interval or {@link Double#NEGATIVE_INFINITY}
  444.          *      if no minimum value exists.
  445.          */
  446.         public double getMinValue() {
  447.             return (min != null) ? min.getLocation() : Double.NEGATIVE_INFINITY;
  448.         }
  449.     }

  451.     /** Class used to project points onto the region boundary.
  452.      */
  453.     private static final class BoundaryProjector1D extends BoundaryProjector<Vector1D, RegionNode1D> {
  454.         /** Simple constructor.
  455.          * @param point the point to project onto the region's boundary
  456.          */
  457.         BoundaryProjector1D(final Vector1D point) {
  458.             super(point);
  459.         }

  461.         /** {@inheritDoc} */
  462.         @Override
  463.         protected Vector1D disambiguateClosestPoint(final Vector1D target, final Vector1D a, final Vector1D b) {
  464.             final int cmp = Vector1D.COORDINATE_ASCENDING_ORDER.compare(a, b);

  466.             if (target.isInfinite() && target.getX() > 0) {
  467.                 // return the largest value (closest to +Infinity)
  468.                 return cmp < 0 ? b : a;
  469.             }

  471.             // return the smallest value
  472.             return cmp < 0 ? a : b;
  473.         }
  474.     }

  476.     /** Internal class for calculating the region of a single tree node.
  477.      */
  478.     private static final class NodeRegionVisitor implements BiConsumer<OrientedPoint, OrientedPoint> {

  480.         /** The min boundary for the region. */
  481.         private OrientedPoint min;

  483.         /** The max boundary for the region. */
  484.         private OrientedPoint max;

  486.         /** {@inheritDoc} */
  487.         @Override
  488.         public void accept(final OrientedPoint minBoundary, final OrientedPoint maxBoundary) {
  489.             // reverse the oriented point directions if needed
  490.             this.min = (minBoundary != null && minBoundary.isPositiveFacing()) ? minBoundary.reverse() : minBoundary;
  491.             this.max = (maxBoundary != null && !maxBoundary.isPositiveFacing()) ? maxBoundary.reverse() : maxBoundary;
  492.         }

  494.         /** Return the computed interval.
  495.          * @return the computed interval.
  496.          */
  497.         public Interval getInterval() {
  498.             return Interval.of(min, max);
  499.         }
  500.     }

  502.     /** Internal class for calculating size-related properties for a {@link RegionBSPTree1D}.
  503.      */
  504.     private static final class RegionSizePropertiesVisitor implements BiConsumer<OrientedPoint, OrientedPoint> {
  505.         /** Number of inside intervals visited. */
  506.         private int count;

  508.         /** Total computed size of all inside regions. */
  509.         private double size;

  511.         /** Raw sum of the centroids of each inside interval. */
  512.         private double rawCentroidSum;

  514.         /** The sum of the centroids of each inside interval, scaled by the size of the interval. */
  515.         private double scaledCentroidSum;

  517.         /** {@inheritDoc} */
  518.         @Override
  519.         public void accept(final OrientedPoint min, final OrientedPoint max) {
  520.             ++count;

  522.             final double minLoc = (min != null) ? min.getLocation() : Double.NEGATIVE_INFINITY;
  523.             final double maxLoc = (max != null) ? max.getLocation() : Double.POSITIVE_INFINITY;

  525.             final double intervalSize = maxLoc - minLoc;
  526.             final double intervalCentroid = 0.5 * (maxLoc + minLoc);

  528.             size += intervalSize;
  529.             rawCentroidSum += intervalCentroid;
  530.             scaledCentroidSum += intervalSize * intervalCentroid;
  531.         }

  533.         /** Get the computed properties for the region. This must only be called after
  534.          * every inside interval has been visited.
  535.          * @return properties for the region
  536.          */
  537.         public RegionSizeProperties<Vector1D> getRegionSizeProperties() {
  538.             Vector1D centroid = null;

  540.             if (count > 0 && Double.isFinite(size)) {
  541.                 if (size > 0) {
  542.                     // use the scaled sum if we have a non-zero size
  543.                     centroid = Vector1D.of(scaledCentroidSum / size);
  544.                 } else {
  545.                     // use the raw sum if we don't have a size; this will be
  546.                     // the case if the region only contains points with zero size
  547.                     centroid = Vector1D.of(rawCentroidSum / count);
  548.                 }
  549.             }

  551.             return new RegionSizeProperties<>(size, centroid);
  552.         }
  553.     }
  554. }
Created with JaCoCo 0.8.5.201910111838