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