AbstractConvexHyperplaneBoundedRegion.java
- /*
- * 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.core.partitioning;
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.Iterator;
- import java.util.List;
- import java.util.function.Function;
- import org.apache.commons.geometry.core.Point;
- import org.apache.commons.geometry.core.RegionLocation;
- import org.apache.commons.geometry.core.Transform;
- /** Base class for convex hyperplane-bounded regions. This class provides generic implementations of many
- * algorithms related to convex regions.
- * @param <P> Point implementation type
- * @param <S> Hyperplane convex subset implementation type
- */
- public abstract class AbstractConvexHyperplaneBoundedRegion<P extends Point<P>, S extends HyperplaneConvexSubset<P>>
- implements HyperplaneBoundedRegion<P> {
- /** List of boundaries for the region. */
- private final List<S> boundaries;
- /** Simple constructor. Callers are responsible for ensuring that the given list of boundaries
- * define a convex region. No validation is performed.
- * @param boundaries the boundaries of the convex region
- */
- protected AbstractConvexHyperplaneBoundedRegion(final List<S> boundaries) {
- this.boundaries = Collections.unmodifiableList(boundaries);
- }
- /** Get the boundaries of the convex region. The exact ordering of the boundaries
- * is not guaranteed.
- * @return the boundaries of the convex region
- */
- public List<S> getBoundaries() {
- return boundaries;
- }
- /** {@inheritDoc} */
- @Override
- public boolean isFull() {
- // no boundaries => no outside
- return boundaries.isEmpty();
- }
- /** {@inheritDoc}
- *
- * <p>This method always returns false.</p>
- */
- @Override
- public boolean isEmpty() {
- return false;
- }
- /** {@inheritDoc} */
- @Override
- public double getBoundarySize() {
- double sum = 0.0;
- for (final S boundary : boundaries) {
- sum += boundary.getSize();
- }
- return sum;
- }
- /** {@inheritDoc} */
- @Override
- public RegionLocation classify(final P pt) {
- boolean isOn = false;
- HyperplaneLocation loc;
- for (final S boundary : boundaries) {
- loc = boundary.getHyperplane().classify(pt);
- if (loc == HyperplaneLocation.PLUS) {
- return RegionLocation.OUTSIDE;
- } else if (loc == HyperplaneLocation.ON) {
- isOn = true;
- }
- }
- return isOn ? RegionLocation.BOUNDARY : RegionLocation.INSIDE;
- }
- /** {@inheritDoc} */
- @Override
- public P project(final P pt) {
- P projected;
- double dist;
- P closestPt = null;
- double closestDist = Double.POSITIVE_INFINITY;
- for (final S boundary : boundaries) {
- projected = boundary.closest(pt);
- dist = pt.distance(projected);
- if (projected != null && (closestPt == null || dist < closestDist)) {
- closestPt = projected;
- closestDist = dist;
- }
- }
- return closestPt;
- }
- /** Trim the given hyperplane subset to the portion contained inside this instance.
- * @param sub hyperplane subset to trim. Null is returned if the subset does not intersect the instance.
- * @return portion of the argument that lies entirely inside the region represented by
- * this instance, or null if it does not intersect.
- */
- public HyperplaneConvexSubset<P> trim(final HyperplaneConvexSubset<P> sub) {
- HyperplaneConvexSubset<P> remaining = sub;
- for (final S boundary : boundaries) {
- remaining = remaining.split(boundary.getHyperplane()).getMinus();
- if (remaining == null) {
- break;
- }
- }
- return remaining;
- }
- /** {@inheritDoc} */
- @Override
- public String toString() {
- final StringBuilder sb = new StringBuilder();
- sb.append(this.getClass().getSimpleName())
- .append("[boundaries= ")
- .append(boundaries)
- .append(']');
- return sb.toString();
- }
- /** Generic, internal transform method. Subclasses should use this to implement their own transform methods.
- * @param transform the transform to apply to the instance
- * @param thisInstance a reference to the current instance; this is passed as
- * an argument in order to allow it to be a generic type
- * @param boundaryType the type used for the boundary hyperplane subsets
- * @param factory function used to create new convex region instances
- * @param <R> Region implementation type
- * @return the result of the transform operation
- */
- protected <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> R transformInternal(
- final Transform<P> transform, final R thisInstance, final Class<S> boundaryType,
- final Function<? super List<S>, R> factory) {
- if (isFull()) {
- return thisInstance;
- }
- final List<S> origBoundaries = getBoundaries();
- final int size = origBoundaries.size();
- final List<S> tBoundaries = new ArrayList<>(size);
- // determine if the hyperplanes should be reversed
- final S boundary = origBoundaries.get(0);
- HyperplaneConvexSubset<P> tBoundary = boundary.transform(transform);
- final boolean reverseDirection = swapsInsideOutside(transform);
- // transform all of the segments
- if (reverseDirection) {
- tBoundary = tBoundary.reverse();
- }
- tBoundaries.add(boundaryType.cast(tBoundary));
- for (int i = 1; i < origBoundaries.size(); ++i) {
- tBoundary = origBoundaries.get(i).transform(transform);
- if (reverseDirection) {
- tBoundary = tBoundary.reverse();
- }
- tBoundaries.add(boundaryType.cast(tBoundary));
- }
- return factory.apply(tBoundaries);
- }
- /** Return true if the given transform swaps the inside and outside of
- * the region.
- *
- * <p>The default behavior of this method is to return true if the transform
- * does not preserve spatial orientation (ie, {@link Transform#preservesOrientation()}
- * is false). Subclasses may need to override this method to implement the correct
- * behavior for their space and dimension.</p>
- * @param transform transform to check
- * @return true if the given transform swaps the interior and exterior of
- * the region
- */
- protected boolean swapsInsideOutside(final Transform<P> transform) {
- return !transform.preservesOrientation();
- }
- /** Generic, internal split method. Subclasses should call this from their {@link #split(Hyperplane)} methods.
- * @param splitter splitting hyperplane
- * @param thisInstance a reference to the current instance; this is passed as
- * an argument in order to allow it to be a generic type
- * @param boundaryType the type used for the boundary hyperplane subsets
- * @param factory function used to create new convex region instances
- * @param <R> Region implementation type
- * @return the result of the split operation
- */
- protected <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> Split<R> splitInternal(
- final Hyperplane<P> splitter, final R thisInstance, final Class<S> boundaryType,
- final Function<List<S>, R> factory) {
- return isFull() ?
- splitInternalFull(splitter, boundaryType, factory) :
- splitInternalNonFull(splitter, thisInstance, boundaryType, factory);
- }
- /** Internal split method for use with full regions, i.e. regions that cover the entire space.
- * @param splitter splitting hyperplane
- * @param boundaryType the type used for the boundary hyperplane subsets
- * @param factory function used to create new convex region instances
- * @param <R> Region implementation type
- * @return the result of the split operation
- */
- private <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> Split<R> splitInternalFull(
- final Hyperplane<P> splitter, final Class<S> boundaryType, final Function<? super List<S>, R> factory) {
- final R minus = factory.apply(Collections.singletonList(boundaryType.cast(splitter.span())));
- final R plus = factory.apply(Collections.singletonList(boundaryType.cast(splitter.reverse().span())));
- return new Split<>(minus, plus);
- }
- /** Internal split method for use with non-full regions, i.e. regions that do not cover the entire space.
- * @param splitter splitting hyperplane
- * @param thisInstance a reference to the current instance; this is passed as
- * an argument in order to allow it to be a generic type
- * @param boundaryType the type used for the boundary hyperplane subsets
- * @param factory function used to create new convex region instances
- * @param <R> Region implementation type
- * @return the result of the split operation
- */
- private <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> Split<R> splitInternalNonFull(
- final Hyperplane<P> splitter, final R thisInstance, final Class<S> boundaryType,
- final Function<? super List<S>, R> factory) {
- final HyperplaneConvexSubset<P> trimmedSplitter = trim(splitter.span());
- if (trimmedSplitter == null) {
- // The splitter lies entirely outside of the region; we need
- // to determine whether we lie on the plus or minus side of the splitter.
- final SplitLocation regionLoc = determineRegionPlusMinusLocation(splitter);
- return regionLoc == SplitLocation.MINUS ?
- new Split<>(thisInstance, null) :
- new Split<>(null, thisInstance);
- }
- // the splitter passes through the region; split the other region boundaries
- // by the splitter
- final ArrayList<S> minusBoundaries = new ArrayList<>();
- final ArrayList<S> plusBoundaries = new ArrayList<>();
- splitBoundaries(splitter, boundaryType, minusBoundaries, plusBoundaries);
- // if the splitter was trimmed by the region boundaries, double-check that the split boundaries
- // actually lie on both sides of the splitter; this is another case where floating point errors
- // can cause a discrepancy between the results of splitting the splitter by the boundaries and
- // splitting the boundaries by the splitter
- if (!trimmedSplitter.isFull()) {
- if (minusBoundaries.isEmpty()) {
- if (plusBoundaries.isEmpty()) {
- return new Split<>(null, null);
- }
- return new Split<>(null, thisInstance);
- } else if (plusBoundaries.isEmpty()) {
- return new Split<>(thisInstance, null);
- }
- }
- // we have a consistent region split; create the new plus and minus regions
- minusBoundaries.add(boundaryType.cast(trimmedSplitter));
- plusBoundaries.add(boundaryType.cast(trimmedSplitter.reverse()));
- minusBoundaries.trimToSize();
- plusBoundaries.trimToSize();
- return new Split<>(factory.apply(minusBoundaries), factory.apply(plusBoundaries));
- }
- /** Determine whether the region lies on the plus or minus side of the given splitter. It is assumed
- * that (1) the region is not full, and (2) the given splitter does not pass through the region.
- *
- * <p>In theory, this is a very simple operation: one need only test a single region boundary
- * to see if it lies on the plus or minus side of the splitter. In practice, however, accumulated
- * floating point errors can cause discrepancies between the splitting operations, causing
- * boundaries to be classified as lying on both sides of the splitter when they should only lie on one.
- * Therefore, this method examines as many boundaries as needed in order to determine the best response.
- * The algorithm proceeds as follows:
- * <ol>
- * <li>If any boundary lies completely on the minus or plus side of the splitter, then
- * {@link SplitLocation#MINUS MINUS} or {@link SplitLocation#PLUS PLUS} is returned, respectively.</li>
- * <li>If any boundary is coincident with the splitter ({@link SplitLocation#NEITHER NEITHER}), then
- * {@link SplitLocation#MINUS MINUS} is returned if the boundary hyperplane has the same orientation
- * as the splitter, otherwise {@link SplitLocation#PLUS PLUS}.</li>
- * <li>If no boundaries match the above conditions, then the sizes of the split boundaries are compared. If
- * the sum of the sizes of the boundaries on the minus side is greater than the sum of the sizes of
- * the boundaries on the plus size, then {@link SplitLocation#MINUS MINUS} is returned. Otherwise,
- * {@link SplitLocation#PLUS PLUS} is returned.
- * </ol>
- * @param splitter splitter to classify the region against; the splitter is assumed to lie
- * completely outside of the region
- * @return {@link SplitLocation#MINUS} if the region lies on the minus side of the splitter and
- * {@link SplitLocation#PLUS} if the region lies on the plus side of the splitter
- */
- private SplitLocation determineRegionPlusMinusLocation(final Hyperplane<P> splitter) {
- double minusSize = 0;
- double plusSize = 0;
- Split<? extends HyperplaneConvexSubset<P>> split;
- SplitLocation loc;
- for (final S boundary : boundaries) {
- split = boundary.split(splitter);
- loc = split.getLocation();
- if (loc == SplitLocation.MINUS || loc == SplitLocation.PLUS) {
- return loc;
- } else if (loc == SplitLocation.NEITHER) {
- return splitter.similarOrientation(boundary.getHyperplane()) ?
- SplitLocation.MINUS :
- SplitLocation.PLUS;
- } else {
- minusSize += split.getMinus().getSize();
- plusSize += split.getPlus().getSize();
- }
- }
- return minusSize > plusSize ? SplitLocation.MINUS : SplitLocation.PLUS;
- }
- /** Split the boundaries of the region by the given hyperplane, adding the split parts into the
- * corresponding lists.
- * @param splitter splitting hyperplane
- * @param boundaryType the type used for the boundary hyperplane subsets
- * @param minusBoundaries list that will contain the portions of the boundaries on the minus side
- * of the splitting hyperplane
- * @param plusBoundaries list that will contain the portions of the boundaries on the plus side of
- * the splitting hyperplane
- */
- private void splitBoundaries(final Hyperplane<P> splitter, final Class<S> boundaryType,
- final List<S> minusBoundaries, final List<S> plusBoundaries) {
- Split<? extends HyperplaneConvexSubset<P>> split;
- HyperplaneConvexSubset<P> minusBoundary;
- HyperplaneConvexSubset<P> plusBoundary;
- for (final S boundary : boundaries) {
- split = boundary.split(splitter);
- minusBoundary = split.getMinus();
- plusBoundary = split.getPlus();
- if (minusBoundary != null) {
- minusBoundaries.add(boundaryType.cast(minusBoundary));
- }
- if (plusBoundary != null) {
- plusBoundaries.add(boundaryType.cast(plusBoundary));
- }
- }
- }
- /** Internal class encapsulating the logic for building convex region boundaries from collections of hyperplanes.
- * @param <P> Point implementation type
- * @param <S> Hyperplane convex subset implementation type
- */
- protected static class ConvexRegionBoundaryBuilder<P extends Point<P>, S extends HyperplaneConvexSubset<P>> {
- /** Hyperplane convex subset implementation type. */
- private final Class<S> subsetType;
- /** Construct a new instance for building convex region boundaries with the given hyperplane
- * convex subset implementation type.
- * @param subsetType Hyperplane convex subset implementation type
- */
- public ConvexRegionBoundaryBuilder(final Class<S> subsetType) {
- this.subsetType = subsetType;
- }
- /** Compute a list of hyperplane convex subsets representing the boundaries of the convex region
- * bounded by the given collection of hyperplanes.
- * @param bounds hyperplanes defining the convex region
- * @return a list of hyperplane convex subsets representing the boundaries of the convex region
- * @throws IllegalArgumentException if the given hyperplanes do not form a convex region
- */
- public List<S> build(final Iterable<? extends Hyperplane<P>> bounds) {
- final List<S> boundaries = new ArrayList<>();
- // cut each hyperplane by every other hyperplane in order to get the region boundaries
- int boundIdx = -1;
- HyperplaneConvexSubset<P> boundary;
- for (final Hyperplane<P> currentBound : bounds) {
- ++boundIdx;
- boundary = splitBound(currentBound, bounds, boundIdx);
- if (boundary != null) {
- boundaries.add(subsetType.cast(boundary));
- }
- }
- if (boundIdx > 0 && boundaries.isEmpty()) {
- // nothing was added
- throw nonConvexException(bounds);
- }
- return boundaries;
- }
- /** Split the given bounding hyperplane by all of the other hyperplanes in the given collection, returning the
- * remaining hyperplane subset.
- * @param currentBound the bound to split; this value is assumed to have come from {@code bounds}
- * @param bounds collection of bounds to use to split {@code currentBound}
- * @param currentBoundIdx the index of {@code currentBound} in {@code bounds}
- * @return the part of {@code currentBound}'s hyperplane subset that lies on the minus side of all of the
- * splitting hyperplanes
- * @throws IllegalArgumentException if the hyperplanes do not form a convex region
- */
- private HyperplaneConvexSubset<P> splitBound(final Hyperplane<P> currentBound,
- final Iterable<? extends Hyperplane<P>> bounds, final int currentBoundIdx) {
- HyperplaneConvexSubset<P> boundary = currentBound.span();
- final Iterator<? extends Hyperplane<P>> boundsIt = bounds.iterator();
- Hyperplane<P> splitter;
- int splitterIdx = -1;
- while (boundsIt.hasNext() && boundary != null) {
- splitter = boundsIt.next();
- ++splitterIdx;
- if (currentBound == splitter) {
- // do not split the bound with itself
- if (currentBoundIdx > splitterIdx) {
- // this hyperplane is duplicated in the list; skip all but the
- // first insertion of its hyperplane subset
- return null;
- }
- } else {
- // split the boundary
- final Split<? extends HyperplaneConvexSubset<P>> split = boundary.split(splitter);
- if (split.getLocation() != SplitLocation.NEITHER) {
- // retain the minus portion of the split
- boundary = split.getMinus();
- } else if (!currentBound.similarOrientation(splitter)) {
- // two or more splitters are coincident and have opposite
- // orientations, meaning that no area is on the minus side
- // of both
- throw nonConvexException(bounds);
- } else if (currentBoundIdx > splitterIdx) {
- // two or more hyperplanes are equivalent; only use the boundary
- // from the first one and return null for this one
- return null;
- }
- }
- }
- return boundary;
- }
- /** Return an exception indicating that the given collection of hyperplanes do not produce a convex region.
- * @param bounds collection of hyperplanes
- * @return an exception indicating that the given collection of hyperplanes do not produce a convex region
- */
- private IllegalArgumentException nonConvexException(final Iterable<? extends Hyperplane<P>> bounds) {
- return new IllegalArgumentException("Bounding hyperplanes do not produce a convex region: " + bounds);
- }
- }
- }