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