| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.geometry.euclidean.oned; |
| |
| import java.util.ArrayList; |
| import java.util.Comparator; |
| import java.util.List; |
| import java.util.Objects; |
| import java.util.function.BiConsumer; |
| |
| import org.apache.commons.geometry.core.RegionLocation; |
| import org.apache.commons.geometry.core.Transform; |
| import org.apache.commons.geometry.core.partitioning.Hyperplane; |
| import org.apache.commons.geometry.core.partitioning.Split; |
| import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree; |
| import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree; |
| |
| /** Binary space partitioning (BSP) tree representing a region in one dimensional |
| * Euclidean space. |
| */ |
| public final class RegionBSPTree1D extends AbstractRegionBSPTree<Vector1D, RegionBSPTree1D.RegionNode1D> { |
| /** Comparator used to sort BoundaryPairs by ascending location. */ |
| private static final Comparator<BoundaryPair> BOUNDARY_PAIR_COMPARATOR = |
| (a, b) -> Double.compare(a.getMinValue(), b.getMinValue()); |
| |
| /** Create a new, empty region. |
| */ |
| public RegionBSPTree1D() { |
| this(false); |
| } |
| |
| /** Create a new region. If {@code full} is true, then the region will |
| * represent the entire number line. Otherwise, it will be empty. |
| * @param full whether or not the region should contain the entire |
| * number line or be empty |
| */ |
| public RegionBSPTree1D(boolean full) { |
| super(full); |
| } |
| |
| /** Return a deep copy of this instance. |
| * @return a deep copy of this instance. |
| * @see #copy(org.apache.commons.geometry.core.partitioning.bsp.BSPTree) |
| */ |
| public RegionBSPTree1D copy() { |
| RegionBSPTree1D result = RegionBSPTree1D.empty(); |
| result.copy(this); |
| |
| return result; |
| } |
| |
| /** Add an interval to this region. The resulting region will be the |
| * union of the interval and the region represented by this instance. |
| * @param interval the interval to add |
| */ |
| public void add(final Interval interval) { |
| union(intervalToTree(interval)); |
| } |
| |
| /** Classify a point location with respect to the region. |
| * @param x the point to classify |
| * @return the location of the point with respect to the region |
| * @see #classify(Point) |
| */ |
| public RegionLocation classify(final double x) { |
| return classify(Vector1D.of(x)); |
| } |
| |
| /** Return true if the given point location is on the inside or boundary |
| * of the region. |
| * @param x the location to test |
| * @return true if the location is on the inside or boundary of the region |
| * @see #contains(Point) |
| */ |
| public boolean contains(final double x) { |
| return contains(Vector1D.of(x)); |
| } |
| |
| /** {@inheritDoc} |
| * |
| * <p>This method simply returns 0 because boundaries in one dimension do not |
| * have any size.</p> |
| */ |
| @Override |
| public double getBoundarySize() { |
| return 0; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public Vector1D project(final Vector1D pt) { |
| // use our custom projector so that we can disambiguate points that are |
| // actually equidistant from the target point |
| final BoundaryProjector1D projector = new BoundaryProjector1D(pt); |
| accept(projector); |
| |
| return projector.getProjected(); |
| } |
| |
| /** {@inheritDoc} |
| * |
| * <p>When splitting trees representing single points with a splitter lying directly |
| * on the point, the result point is placed on one side of the splitter based on its |
| * orientation: if the splitter is positive-facing, the point is placed on the plus |
| * side of the split; if the splitter is negative-facing, the point is placed on the |
| * minus side of the split.</p> |
| */ |
| @Override |
| public Split<RegionBSPTree1D> split(final Hyperplane<Vector1D> splitter) { |
| return split(splitter, RegionBSPTree1D.empty(), RegionBSPTree1D.empty()); |
| } |
| |
| /** Get the minimum value on the inside of the region; returns {@link Double#NEGATIVE_INFINITY} |
| * if the region does not have a minimum value and {@link Double#POSITIVE_INFINITY} if |
| * the region is empty. |
| * @return the minimum value on the inside of the region |
| */ |
| public double getMin() { |
| double min = Double.POSITIVE_INFINITY; |
| |
| RegionNode1D node = getRoot(); |
| OrientedPoint pt; |
| |
| while (!node.isLeaf()) { |
| pt = (OrientedPoint) node.getCutHyperplane(); |
| |
| min = pt.getLocation(); |
| node = pt.isPositiveFacing() ? node.getMinus() : node.getPlus(); |
| } |
| |
| return node.isInside() ? Double.NEGATIVE_INFINITY : min; |
| } |
| |
| /** Get the maximum value on the inside of the region; returns {@link Double#POSITIVE_INFINITY} |
| * if the region does not have a maximum value and {@link Double#NEGATIVE_INFINITY} if |
| * the region is empty. |
| * @return the maximum value on the inside of the region |
| */ |
| public double getMax() { |
| double max = Double.NEGATIVE_INFINITY; |
| |
| RegionNode1D node = getRoot(); |
| OrientedPoint pt; |
| |
| while (!node.isLeaf()) { |
| pt = (OrientedPoint) node.getCutHyperplane(); |
| |
| max = pt.getLocation(); |
| node = pt.isPositiveFacing() ? node.getPlus() : node.getMinus(); |
| } |
| |
| return node.isInside() ? Double.POSITIVE_INFINITY : max; |
| } |
| |
| /** Convert the region represented by this tree into a list of separate |
| * {@link Interval}s, arranged in order of ascending min value. |
| * @return list of {@link Interval}s representing this region in order of |
| * ascending min value |
| */ |
| public List<Interval> toIntervals() { |
| |
| final List<BoundaryPair> boundaryPairs = new ArrayList<>(); |
| |
| visitInsideIntervals((min, max) -> boundaryPairs.add(new BoundaryPair(min, max))); |
| boundaryPairs.sort(BOUNDARY_PAIR_COMPARATOR); |
| |
| final List<Interval> intervals = new ArrayList<>(); |
| |
| BoundaryPair start = null; |
| BoundaryPair end = null; |
| |
| for (BoundaryPair current : boundaryPairs) { |
| if (start == null) { |
| start = current; |
| end = current; |
| } else if (Objects.equals(end.getMax(), current.getMin())) { |
| // these intervals should be merged |
| end = current; |
| } else { |
| // these intervals should not be merged |
| intervals.add(createInterval(start, end)); |
| |
| // queue up the next pair |
| start = current; |
| end = current; |
| } |
| } |
| |
| if (start != null && end != null) { |
| intervals.add(createInterval(start, end)); |
| } |
| |
| return intervals; |
| } |
| |
| /** Create an interval instance from the min boundary from the start boundary pair and |
| * the max boundary from the end boundary pair. The hyperplane directions are adjusted |
| * as needed. |
| * @param start starting boundary pair |
| * @param end ending boundary pair |
| * @return an interval created from the min boundary of the given start pair and the |
| * max boundary from the given end pair |
| */ |
| private Interval createInterval(final BoundaryPair start, final BoundaryPair end) { |
| OrientedPoint min = start.getMin(); |
| OrientedPoint max = end.getMax(); |
| |
| // flip the hyperplanes if needed since there's no |
| // guarantee that the inside will be on the minus side |
| // of the hyperplane (for example, if the region is complemented) |
| |
| if (min != null && min.isPositiveFacing()) { |
| min = min.reverse(); |
| } |
| if (max != null && !max.isPositiveFacing()) { |
| max = max.reverse(); |
| } |
| |
| return Interval.of(min, max); |
| } |
| |
| /** Compute the min/max intervals for all interior convex regions in the tree and |
| * pass the values to the given visitor function. |
| * @param visitor the object that will receive the calculated min and max boundary for each |
| * insides node's convex region |
| */ |
| private void visitInsideIntervals(final BiConsumer<OrientedPoint, OrientedPoint> visitor) { |
| for (RegionNode1D node : nodes()) { |
| if (node.isInside()) { |
| node.visitNodeInterval(visitor); |
| } |
| } |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| protected RegionNode1D createNode() { |
| return new RegionNode1D(this); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| protected RegionSizeProperties<Vector1D> computeRegionSizeProperties() { |
| RegionSizePropertiesVisitor visitor = new RegionSizePropertiesVisitor(); |
| |
| visitInsideIntervals(visitor); |
| |
| return visitor.getRegionSizeProperties(); |
| } |
| |
| /** Returns true if the given transform would result in a swapping of the interior |
| * and exterior of the region if applied. |
| * |
| * <p>This method always returns false since no swapping of this kind occurs in |
| * 1D.</p> |
| */ |
| @Override |
| protected boolean swapsInsideOutside(final Transform<Vector1D> transform) { |
| return false; |
| } |
| |
| /** Return a new {@link RegionBSPTree1D} instance containing the entire space. |
| * @return a new {@link RegionBSPTree1D} instance containing the entire space |
| */ |
| public static RegionBSPTree1D full() { |
| return new RegionBSPTree1D(true); |
| } |
| |
| /** Return a new, empty {@link RegionBSPTree1D} instance. |
| * @return a new, empty {@link RegionBSPTree1D} instance |
| */ |
| public static RegionBSPTree1D empty() { |
| return new RegionBSPTree1D(false); |
| } |
| |
| /** Construct a new instance from one or more intervals. The returned tree |
| * represents the same region as the union of all of the input intervals. |
| * @param interval the input interval |
| * @param more additional intervals to add to the region |
| * @return a new instance representing the same region as the union |
| * of all of the given intervals |
| */ |
| public static RegionBSPTree1D from(final Interval interval, final Interval... more) { |
| final RegionBSPTree1D tree = intervalToTree(interval); |
| |
| for (final Interval additional : more) { |
| tree.add(additional); |
| } |
| |
| return tree; |
| } |
| |
| /** Construct a new instance from the given collection of intervals. |
| * @param intervals the intervals to populate the region with |
| * @return a new instance constructed from the given collection of intervals |
| */ |
| public static RegionBSPTree1D from(final Iterable<Interval> intervals) { |
| RegionBSPTree1D tree = new RegionBSPTree1D(false); |
| |
| for (final Interval interval : intervals) { |
| tree.add(interval); |
| } |
| |
| return tree; |
| } |
| |
| /** Return a tree representing the same region as the given interval. |
| * @param interval interval to create a tree from |
| * @return a tree representing the same region as the given interval |
| */ |
| private static RegionBSPTree1D intervalToTree(final Interval interval) { |
| final OrientedPoint minBoundary = interval.getMinBoundary(); |
| final OrientedPoint maxBoundary = interval.getMaxBoundary(); |
| |
| final RegionBSPTree1D tree = full(); |
| |
| RegionNode1D node = tree.getRoot(); |
| |
| if (minBoundary != null) { |
| tree.cutNode(node, minBoundary.span()); |
| |
| node = node.getMinus(); |
| } |
| |
| if (maxBoundary != null) { |
| tree.cutNode(node, maxBoundary.span()); |
| } |
| |
| return tree; |
| } |
| |
| /** BSP tree node for one dimensional Euclidean space. |
| */ |
| public static final class RegionNode1D extends AbstractRegionBSPTree.AbstractRegionNode<Vector1D, RegionNode1D> { |
| /** Simple constructor. |
| * @param tree the owning tree instance |
| */ |
| private RegionNode1D(AbstractBSPTree<Vector1D, RegionNode1D> tree) { |
| super(tree); |
| } |
| |
| /** Get the region represented by this node. The returned region contains |
| * the entire area contained in this node, regardless of the attributes of |
| * any child nodes. |
| * @return the region represented by this node |
| */ |
| public Interval getNodeRegion() { |
| final NodeRegionVisitor visitor = new NodeRegionVisitor(); |
| visitNodeInterval(visitor); |
| |
| return visitor.getInterval(); |
| } |
| |
| /** Determine the min/max boundaries for the convex region represented by this node and pass |
| * the values to the visitor function. |
| * @param visitor the object that will receive the min and max boundaries for the node's |
| * convex region |
| */ |
| private void visitNodeInterval(final BiConsumer<OrientedPoint, OrientedPoint> visitor) { |
| OrientedPoint min = null; |
| OrientedPoint max = null; |
| |
| OrientedPoint pt; |
| RegionNode1D child = this; |
| RegionNode1D parent; |
| |
| while ((min == null || max == null) && (parent = child.getParent()) != null) { |
| pt = (OrientedPoint) parent.getCutHyperplane(); |
| |
| if ((pt.isPositiveFacing() && child.isMinus()) || |
| (!pt.isPositiveFacing() && child.isPlus())) { |
| |
| if (max == null) { |
| max = pt; |
| } |
| } else if (min == null) { |
| min = pt; |
| } |
| |
| child = parent; |
| } |
| |
| visitor.accept(min, max); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| protected RegionNode1D getSelf() { |
| return this; |
| } |
| } |
| |
| /** Internal class containing pairs of interval boundaries. |
| */ |
| private static final class BoundaryPair { |
| |
| /** The min boundary. */ |
| private final OrientedPoint min; |
| |
| /** The max boundary. */ |
| private final OrientedPoint max; |
| |
| /** Simple constructor. |
| * @param min min boundary hyperplane |
| * @param max max boundary hyperplane |
| */ |
| BoundaryPair(final OrientedPoint min, final OrientedPoint max) { |
| this.min = min; |
| this.max = max; |
| } |
| |
| /** Get the minimum boundary hyperplane. |
| * @return the minimum boundary hyperplane. |
| */ |
| public OrientedPoint getMin() { |
| return min; |
| } |
| |
| /** Get the maximum boundary hyperplane. |
| * @return the maximum boundary hyperplane. |
| */ |
| public OrientedPoint getMax() { |
| return max; |
| } |
| |
| /** Get the minumum value of the interval or {@link Double#NEGATIVE_INFINITY} |
| * if no minimum value exists. |
| * @return the minumum value of the interval or {@link Double#NEGATIVE_INFINITY} |
| * if no minimum value exists. |
| */ |
| public double getMinValue() { |
| return (min != null) ? min.getLocation() : Double.NEGATIVE_INFINITY; |
| } |
| } |
| |
| /** Class used to project points onto the region boundary. |
| */ |
| private static final class BoundaryProjector1D extends BoundaryProjector<Vector1D, RegionNode1D> { |
| /** Simple constructor. |
| * @param point the point to project onto the region's boundary |
| */ |
| BoundaryProjector1D(Vector1D point) { |
| super(point); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| protected Vector1D disambiguateClosestPoint(final Vector1D target, final Vector1D a, final Vector1D b) { |
| final int cmp = Vector1D.COORDINATE_ASCENDING_ORDER.compare(a, b); |
| |
| if (target.isInfinite() && target.getX() > 0) { |
| // return the largest value (closest to +Infinity) |
| return cmp < 0 ? b : a; |
| } |
| |
| // return the smallest value |
| return cmp < 0 ? a : b; |
| } |
| } |
| |
| /** Internal class for calculating the region of a single tree node. |
| */ |
| private static final class NodeRegionVisitor implements BiConsumer<OrientedPoint, OrientedPoint> { |
| |
| /** The min boundary for the region. */ |
| private OrientedPoint min; |
| |
| /** The max boundary for the region. */ |
| private OrientedPoint max; |
| |
| /** {@inheritDoc} */ |
| @Override |
| public void accept(final OrientedPoint minBoundary, final OrientedPoint maxBoundary) { |
| // reverse the oriented point directions if needed |
| this.min = (minBoundary != null && minBoundary.isPositiveFacing()) ? minBoundary.reverse() : minBoundary; |
| this.max = (maxBoundary != null && !maxBoundary.isPositiveFacing()) ? maxBoundary.reverse() : maxBoundary; |
| } |
| |
| /** Return the computed interval. |
| * @return the computed interval. |
| */ |
| public Interval getInterval() { |
| return Interval.of(min, max); |
| } |
| } |
| |
| /** Internal class for calculating size-related properties for a {@link RegionBSPTree1D}. |
| */ |
| private static final class RegionSizePropertiesVisitor implements BiConsumer<OrientedPoint, OrientedPoint> { |
| /** Number of inside intervals visited. */ |
| private int count = 0; |
| |
| /** Total computed size of all inside regions. */ |
| private double size = 0; |
| |
| /** Raw sum of the barycenters of each inside interval. */ |
| private double rawBarycenterSum = 0; |
| |
| /** The sum of the barycenter of each inside interval, scaled by the size of the interval. */ |
| private double scaledBarycenterSum = 0; |
| |
| /** {@inheritDoc} */ |
| @Override |
| public void accept(OrientedPoint min, OrientedPoint max) { |
| ++count; |
| |
| final double minLoc = (min != null) ? min.getLocation() : Double.NEGATIVE_INFINITY; |
| final double maxLoc = (max != null) ? max.getLocation() : Double.POSITIVE_INFINITY; |
| |
| final double intervalSize = maxLoc - minLoc; |
| final double intervalBarycenter = 0.5 * (maxLoc + minLoc); |
| |
| size += intervalSize; |
| rawBarycenterSum += intervalBarycenter; |
| scaledBarycenterSum += intervalSize * intervalBarycenter; |
| } |
| |
| /** Get the computed properties for the region. This must only be called after |
| * every inside interval has been visited. |
| * @return properties for the region |
| */ |
| public RegionSizeProperties<Vector1D> getRegionSizeProperties() { |
| Vector1D barycenter = null; |
| |
| if (count > 0 && Double.isFinite(size)) { |
| if (size > 0.0) { |
| // use the scaled sum if we have a non-zero size |
| barycenter = Vector1D.of(scaledBarycenterSum / size); |
| } else { |
| // use the raw sum if we don't have a size; this will be |
| // the case if the region only contains points with zero size |
| barycenter = Vector1D.of(rawBarycenterSum / count); |
| } |
| } |
| |
| return new RegionSizeProperties<>(size, barycenter); |
| } |
| } |
| } |