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 }