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.core.partitioning;
    18
    19  import java.util.ArrayList;
    20  import java.util.Collections;
    21  import java.util.Iterator;
    22  import java.util.List;
    23  import java.util.function.Function;
    24
    25  import org.apache.commons.geometry.core.Point;
    26  import org.apache.commons.geometry.core.RegionLocation;
    27  import org.apache.commons.geometry.core.Transform;
    28
    29  /** Base class for convex hyperplane-bounded regions. This class provides generic implementations of many
    30   * algorithms related to convex regions.
    31   * @param <P> Point implementation type
    32   * @param <S> Hyperplane convex subset implementation type
    33   */
    34  public abstract class AbstractConvexHyperplaneBoundedRegion<P extends Point<P>, S extends HyperplaneConvexSubset<P>>
    35      implements HyperplaneBoundedRegion<P> {
    36      /** List of boundaries for the region. */
    37      private final List<S> boundaries;
    38
    39      /** Simple constructor. Callers are responsible for ensuring that the given list of boundaries
    40       * define a convex region. No validation is performed.
    41       * @param boundaries the boundaries of the convex region
    42       */
    43      protected AbstractConvexHyperplaneBoundedRegion(final List<S> boundaries) {
    44          this.boundaries = Collections.unmodifiableList(boundaries);
    45      }
    46
    47      /** Get the boundaries of the convex region. The exact ordering of the boundaries
    48       * is not guaranteed.
    49       * @return the boundaries of the convex region
    50       */
    51      public List<S> getBoundaries() {
    52          return boundaries;
    53      }
    54
    55      /** {@inheritDoc} */
    56      @Override
    57      public boolean isFull() {
    58          // no boundaries => no outside
    59          return boundaries.isEmpty();
    60      }
    61
    62      /** {@inheritDoc}
    63       *
    64       * <p>This method always returns false.</p>
    65       */
    66      @Override
    67      public boolean isEmpty() {
    68          return false;
    69      }
    70
    71      /** {@inheritDoc} */
    72      @Override
    73      public double getBoundarySize() {
    74          double sum = 0.0;
    75          for (final S boundary : boundaries) {
    76              sum += boundary.getSize();
    77          }
    78
    79          return sum;
    80      }
    81
    82      /** {@inheritDoc} */
    83      @Override
    84      public RegionLocation classify(final P pt) {
    85          boolean isOn = false;
    86
    87          HyperplaneLocation loc;
    88          for (final S boundary : boundaries) {
    89              loc = boundary.getHyperplane().classify(pt);
    90
    91              if (loc == HyperplaneLocation.PLUS) {
    92                  return RegionLocation.OUTSIDE;
    93              } else if (loc == HyperplaneLocation.ON) {
    94                  isOn = true;
    95              }
    96          }
    97
    98          return isOn ? RegionLocation.BOUNDARY : RegionLocation.INSIDE;
    99      }
    100
    101     /** {@inheritDoc} */
    102     @Override
    103     public P project(final P pt) {
    104
    105         P projected;
    106         double dist;
    107
    108         P closestPt = null;
    109         double closestDist = Double.POSITIVE_INFINITY;
    110
    111         for (final S boundary : boundaries) {
    112             projected = boundary.closest(pt);
    113             dist = pt.distance(projected);
    114
    115             if (projected != null && (closestPt == null || dist < closestDist)) {
    116                 closestPt = projected;
    117                 closestDist = dist;
    118             }
    119         }
    120
    121         return closestPt;
    122     }
    123
    124     /** Trim the given hyperplane subset to the portion contained inside this instance.
    125      * @param sub hyperplane subset to trim. Null is returned if the subset does not intersect the instance.
    126      * @return portion of the argument that lies entirely inside the region represented by
    127      *      this instance, or null if it does not intersect.
    128      */
    129     public HyperplaneConvexSubset<P> trim(final HyperplaneConvexSubset<P> sub) {
    130         HyperplaneConvexSubset<P> remaining = sub;
    131         for (final S boundary : boundaries) {
    132             remaining = remaining.split(boundary.getHyperplane()).getMinus();
    133             if (remaining == null) {
    134                 break;
    135             }
    136         }
    137
    138         return remaining;
    139     }
    140
    141     /** {@inheritDoc} */
    142     @Override
    143     public String toString() {
    144         final StringBuilder sb = new StringBuilder();
    145         sb.append(this.getClass().getSimpleName())
    146             .append("[boundaries= ")
    147             .append(boundaries)
    148             .append(']');
    149
    150         return sb.toString();
    151     }
    152
    153     /** Generic, internal transform method. Subclasses should use this to implement their own transform methods.
    154      * @param transform the transform to apply to the instance
    155      * @param thisInstance a reference to the current instance; this is passed as
    156      *      an argument in order to allow it to be a generic type
    157      * @param boundaryType the type used for the boundary hyperplane subsets
    158      * @param factory function used to create new convex region instances
    159      * @param <R> Region implementation type
    160      * @return the result of the transform operation
    161      */
    162     protected <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> R transformInternal(
    163             final Transform<P> transform, final R thisInstance, final Class<S> boundaryType,
    164             final Function<? super List<S>, R> factory) {
    165
    166         if (isFull()) {
    167             return thisInstance;
    168         }
    169
    170         final List<S> origBoundaries = getBoundaries();
    171
    172         final int size = origBoundaries.size();
    173         final List<S> tBoundaries = new ArrayList<>(size);
    174
    175         // determine if the hyperplanes should be reversed
    176         final S boundary = origBoundaries.get(0);
    177         HyperplaneConvexSubset<P> tBoundary = boundary.transform(transform);
    178
    179         final boolean reverseDirection = swapsInsideOutside(transform);
    180
    181         // transform all of the segments
    182         if (reverseDirection) {
    183             tBoundary = tBoundary.reverse();
    184         }
    185         tBoundaries.add(boundaryType.cast(tBoundary));
    186
    187         for (int i = 1; i < origBoundaries.size(); ++i) {
    188             tBoundary = origBoundaries.get(i).transform(transform);
    189
    190             if (reverseDirection) {
    191                 tBoundary = tBoundary.reverse();
    192             }
    193
    194             tBoundaries.add(boundaryType.cast(tBoundary));
    195         }
    196
    197         return factory.apply(tBoundaries);
    198     }
    199
    200     /** Return true if the given transform swaps the inside and outside of
    201      * the region.
    202      *
    203      * <p>The default behavior of this method is to return true if the transform
    204      * does not preserve spatial orientation (ie, {@link Transform#preservesOrientation()}
    205      * is false). Subclasses may need to override this method to implement the correct
    206      * behavior for their space and dimension.</p>
    207      * @param transform transform to check
    208      * @return true if the given transform swaps the interior and exterior of
    209      *      the region
    210      */
    211     protected boolean swapsInsideOutside(final Transform<P> transform) {
    212         return !transform.preservesOrientation();
    213     }
    214
    215     /** Generic, internal split method. Subclasses should call this from their {@link #split(Hyperplane)} methods.
    216      * @param splitter splitting hyperplane
    217      * @param thisInstance a reference to the current instance; this is passed as
    218      *      an argument in order to allow it to be a generic type
    219      * @param boundaryType the type used for the boundary hyperplane subsets
    220      * @param factory function used to create new convex region instances
    221      * @param <R> Region implementation type
    222      * @return the result of the split operation
    223      */
    224     protected <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> Split<R> splitInternal(
    225             final Hyperplane<P> splitter, final R thisInstance, final Class<S> boundaryType,
    226             final Function<List<S>, R> factory) {
    227
    228         return isFull() ?
    229                 splitInternalFull(splitter, boundaryType, factory) :
    230                 splitInternalNonFull(splitter, thisInstance, boundaryType, factory);
    231     }
    232
    233     /** Internal split method for use with full regions, i.e. regions that cover the entire space.
    234      * @param splitter splitting hyperplane
    235      * @param boundaryType the type used for the boundary hyperplane subsets
    236      * @param factory function used to create new convex region instances
    237      * @param <R> Region implementation type
    238      * @return the result of the split operation
    239      */
    240     private <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> Split<R> splitInternalFull(
    241             final Hyperplane<P> splitter, final Class<S> boundaryType, final Function<? super List<S>, R> factory) {
    242
    243         final R minus = factory.apply(Collections.singletonList(boundaryType.cast(splitter.span())));
    244         final R plus = factory.apply(Collections.singletonList(boundaryType.cast(splitter.reverse().span())));
    245
    246         return new Split<>(minus, plus);
    247     }
    248
    249     /** Internal split method for use with non-full regions, i.e. regions that do not cover the entire space.
    250      * @param splitter splitting hyperplane
    251      * @param thisInstance a reference to the current instance; this is passed as
    252      *      an argument in order to allow it to be a generic type
    253      * @param boundaryType the type used for the boundary hyperplane subsets
    254      * @param factory function used to create new convex region instances
    255      * @param <R> Region implementation type
    256      * @return the result of the split operation
    257      */
    258     private <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> Split<R> splitInternalNonFull(
    259             final Hyperplane<P> splitter, final R thisInstance, final Class<S> boundaryType,
    260             final Function<? super List<S>, R> factory) {
    261
    262         final HyperplaneConvexSubset<P> trimmedSplitter = trim(splitter.span());
    263
    264         if (trimmedSplitter == null) {
    265             // The splitter lies entirely outside of the region; we need
    266             // to determine whether we lie on the plus or minus side of the splitter.
    267
    268             final SplitLocation regionLoc = determineRegionPlusMinusLocation(splitter);
    269             return regionLoc == SplitLocation.MINUS ?
    270                     new Split<>(thisInstance, null) :
    271                     new Split<>(null, thisInstance);
    272         }
    273
    274         // the splitter passes through the region; split the other region boundaries
    275         // by the splitter
    276         final ArrayList<S> minusBoundaries = new ArrayList<>();
    277         final ArrayList<S> plusBoundaries = new ArrayList<>();
    278
    279         splitBoundaries(splitter, boundaryType, minusBoundaries, plusBoundaries);
    280
    281         // if the splitter was trimmed by the region boundaries, double-check that the split boundaries
    282         // actually lie on both sides of the splitter; this is another case where floating point errors
    283         // can cause a discrepancy between the results of splitting the splitter by the boundaries and
    284         // splitting the boundaries by the splitter
    285         if (!trimmedSplitter.isFull()) {
    286             if (minusBoundaries.isEmpty()) {
    287                 if (plusBoundaries.isEmpty()) {
    288                     return new Split<>(null, null);
    289                 }
    290                 return new Split<>(null, thisInstance);
    291             } else if (plusBoundaries.isEmpty()) {
    292                 return new Split<>(thisInstance, null);
    293             }
    294         }
    295
    296         // we have a consistent region split; create the new plus and minus regions
    297         minusBoundaries.add(boundaryType.cast(trimmedSplitter));
    298         plusBoundaries.add(boundaryType.cast(trimmedSplitter.reverse()));
    299
    300         minusBoundaries.trimToSize();
    301         plusBoundaries.trimToSize();
    302
    303         return new Split<>(factory.apply(minusBoundaries), factory.apply(plusBoundaries));
    304     }
    305
    306     /** Determine whether the region lies on the plus or minus side of the given splitter. It is assumed
    307      * that (1) the region is not full, and (2) the given splitter does not pass through the region.
    308      *
    309      * <p>In theory, this is a very simple operation: one need only test a single region boundary
    310      * to see if it lies on the plus or minus side of the splitter. In practice, however, accumulated
    311      * floating point errors can cause discrepancies between the splitting operations, causing
    312      * boundaries to be classified as lying on both sides of the splitter when they should only lie on one.
    313      * Therefore, this method examines as many boundaries as needed in order to determine the best response.
    314      * The algorithm proceeds as follows:
    315      * <ol>
    316      *  <li>If any boundary lies completely on the minus or plus side of the splitter, then
    317      *      {@link SplitLocation#MINUS MINUS} or {@link SplitLocation#PLUS PLUS} is returned, respectively.</li>
    318      *  <li>If any boundary is coincident with the splitter ({@link SplitLocation#NEITHER NEITHER}), then
    319      *      {@link SplitLocation#MINUS MINUS} is returned if the boundary hyperplane has the same orientation
    320      *      as the splitter, otherwise {@link SplitLocation#PLUS PLUS}.</li>
    321      *  <li>If no boundaries match the above conditions, then the sizes of the split boundaries are compared. If
    322      *      the sum of the sizes of the boundaries on the minus side is greater than the sum of the sizes of
    323      *      the boundaries on the plus size, then {@link SplitLocation#MINUS MINUS} is returned. Otherwise,
    324      *      {@link SplitLocation#PLUS PLUS} is returned.
    325      * </ol>
    326      * @param splitter splitter to classify the region against; the splitter is assumed to lie
    327      *      completely outside of the region
    328      * @return {@link SplitLocation#MINUS} if the region lies on the minus side of the splitter and
    329      *      {@link SplitLocation#PLUS} if the region lies on the plus side of the splitter
    330      */
    331     private SplitLocation determineRegionPlusMinusLocation(final Hyperplane<P> splitter) {
    332         double minusSize = 0;
    333         double plusSize = 0;
    334
    335         Split<? extends HyperplaneConvexSubset<P>> split;
    336         SplitLocation loc;
    337
    338         for (final S boundary : boundaries) {
    339             split = boundary.split(splitter);
    340             loc = split.getLocation();
    341
    342             if (loc == SplitLocation.MINUS || loc == SplitLocation.PLUS) {
    343                 return loc;
    344             } else if (loc == SplitLocation.NEITHER) {
    345                 return splitter.similarOrientation(boundary.getHyperplane()) ?
    346                         SplitLocation.MINUS :
    347                         SplitLocation.PLUS;
    348             } else {
    349                 minusSize += split.getMinus().getSize();
    350                 plusSize += split.getPlus().getSize();
    351             }
    352         }
    353
    354         return minusSize > plusSize ? SplitLocation.MINUS : SplitLocation.PLUS;
    355     }
    356
    357     /** Split the boundaries of the region by the given hyperplane, adding the split parts into the
    358      * corresponding lists.
    359      * @param splitter splitting hyperplane
    360      * @param boundaryType the type used for the boundary hyperplane subsets
    361      * @param minusBoundaries list that will contain the portions of the boundaries on the minus side
    362      *      of the splitting hyperplane
    363      * @param plusBoundaries list that will contain the portions of the boundaries on the plus side of
    364      *      the splitting hyperplane
    365      */
    366     private void splitBoundaries(final Hyperplane<P> splitter, final Class<S> boundaryType,
    367             final List<S> minusBoundaries, final List<S> plusBoundaries) {
    368
    369         Split<? extends HyperplaneConvexSubset<P>> split;
    370         HyperplaneConvexSubset<P> minusBoundary;
    371         HyperplaneConvexSubset<P> plusBoundary;
    372
    373         for (final S boundary : boundaries) {
    374             split = boundary.split(splitter);
    375
    376             minusBoundary = split.getMinus();
    377             plusBoundary = split.getPlus();
    378
    379             if (minusBoundary != null) {
    380                 minusBoundaries.add(boundaryType.cast(minusBoundary));
    381             }
    382
    383             if (plusBoundary != null) {
    384                 plusBoundaries.add(boundaryType.cast(plusBoundary));
    385             }
    386         }
    387     }
    388
    389     /** Internal class encapsulating the logic for building convex region boundaries from collections of hyperplanes.
    390      * @param <P> Point implementation type
    391      * @param <S> Hyperplane convex subset implementation type
    392      */
    393     protected static class ConvexRegionBoundaryBuilder<P extends Point<P>, S extends HyperplaneConvexSubset<P>> {
    394
    395         /** Hyperplane convex subset implementation type. */
    396         private final Class<S> subsetType;
    397
    398         /** Construct a new instance for building convex region boundaries with the given hyperplane
    399          * convex subset implementation type.
    400          * @param subsetType Hyperplane convex subset implementation type
    401          */
    402         public ConvexRegionBoundaryBuilder(final Class<S> subsetType) {
    403             this.subsetType = subsetType;
    404         }
    405
    406         /** Compute a list of hyperplane convex subsets representing the boundaries of the convex region
    407          * bounded by the given collection of hyperplanes.
    408          * @param bounds hyperplanes defining the convex region
    409          * @return a list of hyperplane convex subsets representing the boundaries of the convex region
    410          * @throws IllegalArgumentException if the given hyperplanes do not form a convex region
    411          */
    412         public List<S> build(final Iterable<? extends Hyperplane<P>> bounds) {
    413
    414             final List<S> boundaries = new ArrayList<>();
    415
    416             // cut each hyperplane by every other hyperplane in order to get the region boundaries
    417             int boundIdx = -1;
    418             HyperplaneConvexSubset<P> boundary;
    419
    420             for (final Hyperplane<P> currentBound : bounds) {
    421                 ++boundIdx;
    422
    423                 boundary = splitBound(currentBound, bounds, boundIdx);
    424                 if (boundary != null) {
    425                     boundaries.add(subsetType.cast(boundary));
    426                 }
    427             }
    428
    429             if (boundIdx > 0 && boundaries.isEmpty()) {
    430                 // nothing was added
    431                 throw nonConvexException(bounds);
    432             }
    433
    434             return boundaries;
    435         }
    436
    437         /** Split the given bounding hyperplane by all of the other hyperplanes in the given collection, returning the
    438          * remaining hyperplane subset.
    439          * @param currentBound the bound to split; this value is assumed to have come from {@code bounds}
    440          * @param bounds collection of bounds to use to split {@code currentBound}
    441          * @param currentBoundIdx the index of {@code currentBound} in {@code bounds}
    442          * @return the part of {@code currentBound}'s hyperplane subset that lies on the minus side of all of the
    443          *      splitting hyperplanes
    444          * @throws IllegalArgumentException if the hyperplanes do not form a convex region
    445          */
    446         private HyperplaneConvexSubset<P> splitBound(final Hyperplane<P> currentBound,
    447                 final Iterable<? extends Hyperplane<P>> bounds, final int currentBoundIdx) {
    448
    449             HyperplaneConvexSubset<P> boundary = currentBound.span();
    450
    451             final Iterator<? extends Hyperplane<P>> boundsIt = bounds.iterator();
    452
    453             Hyperplane<P> splitter;
    454             int splitterIdx = -1;
    455
    456             while (boundsIt.hasNext() && boundary != null) {
    457                 splitter = boundsIt.next();
    458                 ++splitterIdx;
    459
    460                 if (currentBound == splitter) {
    461                     // do not split the bound with itself
    462
    463                     if (currentBoundIdx > splitterIdx) {
    464                         // this hyperplane is duplicated in the list; skip all but the
    465                         // first insertion of its hyperplane subset
    466                         return null;
    467                     }
    468                 } else {
    469                     // split the boundary
    470                     final Split<? extends HyperplaneConvexSubset<P>> split = boundary.split(splitter);
    471
    472                     if (split.getLocation() != SplitLocation.NEITHER) {
    473                         // retain the minus portion of the split
    474                         boundary = split.getMinus();
    475                     } else if (!currentBound.similarOrientation(splitter)) {
    476                         // two or more splitters are coincident and have opposite
    477                         // orientations, meaning that no area is on the minus side
    478                         // of both
    479                         throw nonConvexException(bounds);
    480                     } else if (currentBoundIdx > splitterIdx) {
    481                         // two or more hyperplanes are equivalent; only use the boundary
    482                         // from the first one and return null for this one
    483                         return null;
    484                     }
    485                 }
    486             }
    487
    488             return boundary;
    489         }
    490
    491         /** Return an exception indicating that the given collection of hyperplanes do not produce a convex region.
    492          * @param bounds collection of hyperplanes
    493          * @return an exception indicating that the given collection of hyperplanes do not produce a convex region
    494          */
    495         private IllegalArgumentException nonConvexException(final Iterable<? extends Hyperplane<P>> bounds) {
    496             return new IllegalArgumentException("Bounding hyperplanes do not produce a convex region: " + bounds);
    497         }
    498     }
    499 }