View Javadoc

    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;
    18
    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;
    24
    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;
    32
    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);
    40
    41      /** Create a new, empty region.
    42       */
    43      public RegionBSPTree1D() {
    44          this(false);
    45      }
    46
    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      }
    55
    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);
    63
    64          return result;
    65      }
    66
    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      }
    74
    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      }
    83
    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      }
    93
    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     }
    103
    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);
    111
    112         return projector.getProjected();
    113     }
    114
    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     }
    127
    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;
    135
    136         RegionNode1D node = getRoot();
    137         OrientedPoint pt;
    138
    139         while (!node.isLeaf()) {
    140             pt = (OrientedPoint) node.getCutHyperplane();
    141
    142             min = pt.getLocation();
    143             node = pt.isPositiveFacing() ? node.getMinus() : node.getPlus();
    144         }
    145
    146         return node.isInside() ? Double.NEGATIVE_INFINITY : min;
    147     }
    148
    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;
    156
    157         RegionNode1D node = getRoot();
    158         OrientedPoint pt;
    159
    160         while (!node.isLeaf()) {
    161             pt = (OrientedPoint) node.getCutHyperplane();
    162
    163             max = pt.getLocation();
    164             node = pt.isPositiveFacing() ? node.getPlus() : node.getMinus();
    165         }
    166
    167         return node.isInside() ? Double.POSITIVE_INFINITY : max;
    168     }
    169
    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() {
    176
    177         final List<BoundaryPair> boundaryPairs = new ArrayList<>();
    178
    179         visitInsideIntervals((min, max) -> boundaryPairs.add(new BoundaryPair(min, max)));
    180         boundaryPairs.sort(BOUNDARY_PAIR_COMPARATOR);
    181
    182         final List<Interval> intervals = new ArrayList<>();
    183
    184         BoundaryPair start = null;
    185         BoundaryPair end = null;
    186
    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));
    197
    198                 // queue up the next pair
    199                 start = current;
    200                 end = current;
    201             }
    202         }
    203
    204         if (start != null) {
    205             intervals.add(createInterval(start, end));
    206         }
    207
    208         return intervals;
    209     }
    210
    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();
    222
    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)
    226
    227         if (min != null && min.isPositiveFacing()) {
    228             min = min.reverse();
    229         }
    230         if (max != null && !max.isPositiveFacing()) {
    231             max = max.reverse();
    232         }
    233
    234         return Interval.of(min, max);
    235     }
    236
    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     }
    249
    250     /** {@inheritDoc} */
    251     @Override
    252     protected RegionNode1D createNode() {
    253         return new RegionNode1D(this);
    254     }
    255
    256     /** {@inheritDoc} */
    257     @Override
    258     protected RegionSizeProperties<Vector1D> computeRegionSizeProperties() {
    259         final RegionSizePropertiesVisitor visitor = new RegionSizePropertiesVisitor();
    260
    261         visitInsideIntervals(visitor);
    262
    263         return visitor.getRegionSizeProperties();
    264     }
    265
    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     }
    276
    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     }
    283
    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     }
    290
    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);
    300
    301         for (final Interval additional : more) {
    302             tree.add(additional);
    303         }
    304
    305         return tree;
    306     }
    307
    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);
    314
    315         for (final Interval interval : intervals) {
    316             tree.add(interval);
    317         }
    318
    319         return tree;
    320     }
    321
    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();
    329
    330         final RegionBSPTree1D tree = full();
    331
    332         RegionNode1D node = tree.getRoot();
    333
    334         if (minBoundary != null) {
    335             tree.setNodeCut(node, minBoundary.span(), tree.getSubtreeInitializer(RegionCutRule.MINUS_INSIDE));
    336
    337             node = node.getMinus();
    338         }
    339
    340         if (maxBoundary != null) {
    341             tree.setNodeCut(node, maxBoundary.span(), tree.getSubtreeInitializer(RegionCutRule.MINUS_INSIDE));
    342         }
    343
    344         return tree;
    345     }
    346
    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         }
    356
    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);
    365
    366             return visitor.getInterval();
    367         }
    368
    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;
    377
    378             OrientedPoint pt;
    379             RegionNode1D child = this;
    380             RegionNode1D parent;
    381
    382             while ((min == null || max == null) && (parent = child.getParent()) != null) {
    383                 pt = (OrientedPoint) parent.getCutHyperplane();
    384
    385                 if ((pt.isPositiveFacing() && child.isMinus()) ||
    386                         (!pt.isPositiveFacing() && child.isPlus())) {
    387
    388                     if (max == null) {
    389                         max = pt;
    390                     }
    391                 } else if (min == null) {
    392                     min = pt;
    393                 }
    394
    395                 child = parent;
    396             }
    397
    398             visitor.accept(min, max);
    399         }
    400
    401         /** {@inheritDoc} */
    402         @Override
    403         protected RegionNode1D getSelf() {
    404             return this;
    405         }
    406     }
    407
    408     /** Internal class containing pairs of interval boundaries.
    409      */
    410     private static final class BoundaryPair {
    411
    412         /** The min boundary. */
    413         private final OrientedPoint min;
    414
    415         /** The max boundary. */
    416         private final OrientedPoint max;
    417
    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         }
    426
    427         /** Get the minimum boundary hyperplane.
    428          * @return the minimum boundary hyperplane.
    429          */
    430         public OrientedPoint getMin() {
    431             return min;
    432         }
    433
    434         /** Get the maximum boundary hyperplane.
    435          * @return the maximum boundary hyperplane.
    436          */
    437         public OrientedPoint getMax() {
    438             return max;
    439         }
    440
    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     }
    450
    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         }
    460
    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);
    465
    466             if (target.isInfinite() && target.getX() > 0) {
    467                 // return the largest value (closest to +Infinity)
    468                 return cmp < 0 ? b : a;
    469             }
    470
    471             // return the smallest value
    472             return cmp < 0 ? a : b;
    473         }
    474     }
    475
    476     /** Internal class for calculating the region of a single tree node.
    477      */
    478     private static final class NodeRegionVisitor implements BiConsumer<OrientedPoint, OrientedPoint> {
    479
    480         /** The min boundary for the region. */
    481         private OrientedPoint min;
    482
    483         /** The max boundary for the region. */
    484         private OrientedPoint max;
    485
    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         }
    493
    494         /** Return the computed interval.
    495          * @return the computed interval.
    496          */
    497         public Interval getInterval() {
    498             return Interval.of(min, max);
    499         }
    500     }
    501
    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;
    507
    508         /** Total computed size of all inside regions. */
    509         private double size;
    510
    511         /** Raw sum of the centroids of each inside interval. */
    512         private double rawCentroidSum;
    513
    514         /** The sum of the centroids of each inside interval, scaled by the size of the interval. */
    515         private double scaledCentroidSum;
    516
    517         /** {@inheritDoc} */
    518         @Override
    519         public void accept(final OrientedPoint min, final OrientedPoint max) {
    520             ++count;
    521
    522             final double minLoc = (min != null) ? min.getLocation() : Double.NEGATIVE_INFINITY;
    523             final double maxLoc = (max != null) ? max.getLocation() : Double.POSITIVE_INFINITY;
    524
    525             final double intervalSize = maxLoc - minLoc;
    526             final double intervalCentroid = 0.5 * (maxLoc + minLoc);
    527
    528             size += intervalSize;
    529             rawCentroidSum += intervalCentroid;
    530             scaledCentroidSum += intervalSize * intervalCentroid;
    531         }
    532
    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;
    539
    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             }
    550
    551             return new RegionSizeProperties<>(size, centroid);
    552         }
    553     }
    554 }