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);
}
}
}