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 }