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.spherical.oned;
18
19 import java.text.MessageFormat;
20 import java.util.Arrays;
21 import java.util.Collections;
22 import java.util.List;
23 import java.util.function.BiFunction;
24
25 import org.apache.commons.geometry.core.RegionLocation;
26 import org.apache.commons.geometry.core.Transform;
27 import org.apache.commons.geometry.core.partitioning.Hyperplane;
28 import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
29 import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
30 import org.apache.commons.geometry.core.partitioning.Split;
31 import org.apache.commons.numbers.angle.Angle;
32 import org.apache.commons.numbers.core.Precision;
33
34 /** Class representing an angular interval of size greater than zero to {@code 2pi}. The interval is
35 * defined by two azimuth angles: a min and a max. The interval starts at the min azimuth angle and
36 * contains all points in the direction of increasing azimuth angles up to max.
37 *
38 * <p>Instances of this class are guaranteed to be immutable.</p>
39 */
40 public class AngularInterval implements HyperplaneBoundedRegion<Point1S> {
41 /** The minimum boundary of the interval. */
42 private final CutAngle minBoundary;
43
44 /** The maximum boundary of the interval. */
45 private final CutAngle maxBoundary;
46
47 /** Point halfway between the min and max boundaries. */
48 private final Point1S midpoint;
49
50 /** Construct a new instance representing the angular region between the given
51 * min and max azimuth boundaries. The arguments must be either all finite or all
52 * null (to indicate the full space). If the boundaries are finite, then the min
53 * boundary azimuth value must be numerically less than the max boundary. Callers are
54 * responsible for enforcing these constraints. No validation is performed.
55 * @param minBoundary minimum boundary for the interval
56 * @param maxBoundary maximum boundary for the interval
57 */
58 private AngularInterval(final CutAngle minBoundary, final CutAngle maxBoundary) {
59
60 this.minBoundary = minBoundary;
61 this.maxBoundary = maxBoundary;
62 this.midpoint = (minBoundary != null && maxBoundary != null) ?
63 Point1S.of(0.5 * (minBoundary.getAzimuth() + maxBoundary.getAzimuth())) :
64 null;
65 }
66
67 /** Get the minimum azimuth angle for the interval, or {@code 0}
68 * if the interval is full.
69 * @return the minimum azimuth angle for the interval or {@code 0}
70 * if the interval represents the full space.
71 */
72 public double getMin() {
73 return (minBoundary != null) ?
74 minBoundary.getAzimuth() :
75 0.0;
76 }
77
78 /** Get the minimum boundary for the interval, or null if the
79 * interval represents the full space.
80 * @return the minimum point for the interval or null if
81 * the interval represents the full space
82 */
83 public CutAngle getMinBoundary() {
84 return minBoundary;
85 }
86
87 /** Get the maximum azimuth angle for the interval, or {@code 2pi} if
88 * the interval represents the full space.
89 * @return the maximum azimuth angle for the interval or {@code 2pi} if
90 * the interval represents the full space.
91 */
92 public double getMax() {
93 return (maxBoundary != null) ?
94 maxBoundary.getAzimuth() :
95 Angle.TWO_PI;
96 }
97
98 /** Get the maximum point for the interval. This will be null if the
99 * interval represents the full space.
100 * @return the maximum point for the interval or null if
101 * the interval represents the full space
102 */
103 public CutAngle getMaxBoundary() {
104 return maxBoundary;
105 }
106
107 /** Get the midpoint of the interval or null if the interval represents
108 * the full space.
109 * @return the midpoint of the interval or null if the interval represents
110 * the full space
111 * @see #getCentroid()
112 */
113 public Point1S getMidPoint() {
114 return midpoint;
115 }
116
117 /** {@inheritDoc} */
118 @Override
119 public boolean isFull() {
120 // minBoundary and maxBoundary are either both null or both not null
121 return minBoundary == null;
122 }
123
124 /** {@inheritDoc}
125 *
126 * <p>This method always returns false.</p>
127 */
128 @Override
129 public boolean isEmpty() {
130 return false;
131 }
132
133 /** {@inheritDoc} */
134 @Override
135 public double getSize() {
136 return getMax() - getMin();
137 }
138
139 /** {@inheritDoc}
140 *
141 * <p>This method simply returns 0 because boundaries in one dimension do not
142 * have any size.</p>
143 */
144 @Override
145 public double getBoundarySize() {
146 return 0;
147 }
148
149 /** {@inheritDoc}
150 *
151 * <p>This method is an alias for {@link #getMidPoint()}.</p>
152 * @see #getMidPoint()
153 */
154 @Override
155 public Point1S getCentroid() {
156 return getMidPoint();
157 }
158
159 /** {@inheritDoc} */
160 @Override
161 public RegionLocation classify(final Point1S pt) {
162 if (!isFull()) {
163 final HyperplaneLocation minLoc = minBoundary.classify(pt);
164 final HyperplaneLocation maxLoc = maxBoundary.classify(pt);
165
166 final boolean wraps = wrapsZero();
167
168 if ((!wraps && (minLoc == HyperplaneLocation.PLUS || maxLoc == HyperplaneLocation.PLUS)) ||
169 (wraps && minLoc == HyperplaneLocation.PLUS && maxLoc == HyperplaneLocation.PLUS)) {
170 return RegionLocation.OUTSIDE;
171 } else if (minLoc == HyperplaneLocation.ON || maxLoc == HyperplaneLocation.ON) {
172 return RegionLocation.BOUNDARY;
173 }
174 }
175 return RegionLocation.INSIDE;
176 }
177
178 /** {@inheritDoc} */
179 @Override
180 public Point1S project(final Point1S pt) {
181 if (!isFull()) {
182 final double minDist = minBoundary.getPoint().distance(pt);
183 final double maxDist = maxBoundary.getPoint().distance(pt);
184
185 return (minDist <= maxDist) ?
186 minBoundary.getPoint() :
187 maxBoundary.getPoint();
188 }
189 return null;
190 }
191
192 /** Return true if the interval wraps around the zero/{@code 2pi} point. In this
193 * case, the max boundary azimuth is less than that of the min boundary when both
194 * values are normalized to the range {@code [0, 2pi)}.
195 * @return true if the interval wraps around the zero/{@code 2pi} point
196 */
197 public boolean wrapsZero() {
198 if (!isFull()) {
199 final double minNormAz = minBoundary.getPoint().getNormalizedAzimuth();
200 final double maxNormAz = maxBoundary.getPoint().getNormalizedAzimuth();
201
202 return maxNormAz < minNormAz;
203 }
204 return false;
205 }
206
207 /** Return a new instance transformed by the argument. If the transformed size
208 * of the interval is greater than or equal to 2pi, then an interval representing
209 * the full space is returned.
210 * @param transform transform to apply
211 * @return a new instance transformed by the argument
212 */
213 public AngularInterval transform(final Transform<Point1S> transform) {
214 return AngularInterval.transform(this, transform, AngularInterval::of);
215 }
216
217 /** {@inheritDoc}
218 *
219 * <p>This method returns instances of {@link RegionBSPTree1S} instead of
220 * {@link AngularInterval} since it is possible for a convex angular interval
221 * to be split into disjoint regions by a single hyperplane. These disjoint
222 * regions cannot be represented by this class and require the use of a BSP
223 * tree.</p>
224 *
225 * @see RegionBSPTree1S#split(Hyperplane)
226 */
227 @Override
228 public Split<RegionBSPTree1S> split(final Hyperplane<Point1S> splitter) {
229 return toTree().split(splitter);
230 }
231
232 /** Return a {@link RegionBSPTree1S} instance representing the same region
233 * as this instance.
234 * @return a BSP tree representing the same region as this instance
235 */
236 public RegionBSPTree1S toTree() {
237 return RegionBSPTree1S.fromInterval(this);
238 }
239
240 /** Return a list of convex intervals comprising this region.
241 * @return a list of convex intervals comprising this region
242 * @see Convex
243 */
244 public List<AngularInterval.Convex> toConvex() {
245 if (isConvex(minBoundary, maxBoundary)) {
246 return Collections.singletonList(new Convex(minBoundary, maxBoundary));
247 }
248
249 final CutAngle midPos = CutAngles.createPositiveFacing(midpoint, minBoundary.getPrecision());
250 final CutAngle midNeg = CutAngles.createNegativeFacing(midpoint, maxBoundary.getPrecision());
251
252 return Arrays.asList(
253 new Convex(minBoundary, midPos),
254 new Convex(midNeg, maxBoundary)
255 );
256 }
257
258 /** {@inheritDoc} */
259 @Override
260 public String toString() {
261 final StringBuilder sb = new StringBuilder();
262 sb.append(this.getClass().getSimpleName())
263 .append("[min= ")
264 .append(getMin())
265 .append(", max= ")
266 .append(getMax())
267 .append(']');
268
269 return sb.toString();
270 }
271
272 /** Return an instance representing the full space. The returned instance contains all
273 * possible azimuth angles.
274 * @return an interval representing the full space
275 */
276 public static AngularInterval.Convex full() {
277 return Convex.FULL;
278 }
279
280 /** Return an instance representing the angular interval between the given min and max azimuth
281 * values. The max value is adjusted to be numerically above the min value, even if the resulting
282 * azimuth value is greater than or equal to {@code 2pi}. An instance representing the full space
283 * is returned if either point is infinite or min and max are equivalent as evaluated by the
284 * given precision context.
285 * @param min min azimuth value
286 * @param max max azimuth value
287 * @param precision precision precision context used to compare floating point values
288 * @return a new instance resulting the angular region between the given min and max azimuths
289 * @throws IllegalArgumentException if either azimuth is infinite or NaN
290 */
291 public static AngularInterval of(final double min, final double max,
292 final Precision.DoubleEquivalence precision) {
293 return of(Point1S.of(min), Point1S.of(max), precision);
294 }
295
296 /** Return an instance representing the angular interval between the given min and max azimuth
297 * points. The max point is adjusted to be numerically above the min point, even if the resulting
298 * azimuth value is greater than or equal to {@code 2pi}. An instance representing the full space
299 * is returned if either point is infinite or min and max are equivalent as evaluated by the
300 * given precision context.
301 * @param min min azimuth value
302 * @param max max azimuth value
303 * @param precision precision precision context used to compare floating point values
304 * @return a new instance resulting the angular region between the given min and max points
305 * @throws IllegalArgumentException if either azimuth is infinite or NaN
306 */
307 public static AngularInterval of(final Point1S min, final Point1S max,
308 final Precision.DoubleEquivalence precision) {
309 return createInterval(min, max, precision, AngularInterval::new, Convex.FULL);
310 }
311
312 /** Return an instance representing the angular interval between the given oriented points.
313 * The negative-facing point is used as the minimum boundary and the positive-facing point is
314 * adjusted to be above the minimum. The arguments can be given in any order. The full space
315 * is returned if the points are equivalent or are oriented in the same direction.
316 * @param a first oriented point
317 * @param b second oriented point
318 * @return an instance representing the angular interval between the given oriented points
319 * @throws IllegalArgumentException if either argument is infinite or NaN
320 */
321 public static AngularInterval of(final CutAngle a, final CutAngle b) {
322 return createInterval(a, b, AngularInterval::new, Convex.FULL);
323 }
324
325 /** Internal method to create an interval between the given min and max points. The max point
326 * is adjusted to be numerically above the min point, even if the resulting
327 * azimuth value is greater than or equal to {@code 2pi}. The full instance argument
328 * is returned if either point is infinite or min and max are equivalent as evaluated by the
329 * given precision context.
330 * @param min min azimuth value
331 * @param max max azimuth value
332 * @param precision precision precision context used to compare floating point values
333 * @param factory factory object used to create new instances; this object is passed the validated
334 * min (negative-facing) cut and the max (positive-facing) cut, in that order
335 * @param <T> Angular interval implementation type
336 * @param fullSpace instance returned if the interval should represent the full space
337 * @return a new instance resulting the angular region between the given min and max points
338 * @throws IllegalArgumentException if either azimuth is infinite or NaN
339 */
340 private static <T extends AngularInterval> T createInterval(final Point1S min, final Point1S max,
341 final Precision.DoubleEquivalence precision,
342 final BiFunction<? super CutAngle, ? super CutAngle, T> factory, final T fullSpace) {
343
344 validateIntervalValues(min, max);
345
346 // return the full space if either point is infinite or the points are equivalent
347 if (min.eq(max, precision)) {
348 return fullSpace;
349 }
350
351 final Point1S adjustedMax = max.above(min);
352
353 return factory.apply(
354 CutAngles.createNegativeFacing(min, precision),
355 CutAngles.createPositiveFacing(adjustedMax, precision)
356 );
357 }
358
359 /** Internal method to create a new interval instance from the given cut angles.
360 * The negative-facing point is used as the minimum boundary and the positive-facing point is
361 * adjusted to be above the minimum. The arguments can be given in any order. The full space
362 * argument is returned if the points are equivalent or are oriented in the same direction.
363 * @param a first cut point
364 * @param b second cut point
365 * @param factory factory object used to create new instances; this object is passed the validated
366 * min (negative-facing) cut and the max (positive-facing) cut, in that order
367 * @param fullSpace instance returned if the interval should represent the full space
368 * @param <T> Angular interval implementation type
369 * @return a new interval instance created from the given cut angles
370 * @throws IllegalArgumentException if either argument is infinite or NaN
371 */
372 private static <T extends AngularInterval> T createInterval(final CutAngle a, final CutAngle b,
373 final BiFunction<? super CutAngle, ? super CutAngle, T> factory, final T fullSpace) {
374
375 final Point1S aPoint = a.getPoint();
376 final Point1S bPoint = b.getPoint();
377
378 validateIntervalValues(aPoint, bPoint);
379
380 if (a.isPositiveFacing() == b.isPositiveFacing() ||
381 aPoint.eq(bPoint, a.getPrecision()) ||
382 bPoint.eq(aPoint, b.getPrecision())) {
383 // points are equivalent or facing in the same direction
384 return fullSpace;
385 }
386
387 final CutAngle min = a.isPositiveFacing() ? b : a;
388 final CutAngle max = a.isPositiveFacing() ? a : b;
389 final CutAngle adjustedMax = CutAngles.createPositiveFacing(
390 max.getPoint().above(min.getPoint()),
391 max.getPrecision());
392
393 return factory.apply(min, adjustedMax);
394 }
395
396 /** Validate that the given points can be used to specify an angular interval.
397 * @param a first point
398 * @param b second point
399 * @throws IllegalArgumentException if either point is infinite NaN
400 */
401 private static void validateIntervalValues(final Point1S a, final Point1S b) {
402 if (!a.isFinite() || !b.isFinite()) {
403 throw new IllegalArgumentException(MessageFormat.format("Invalid angular interval: [{0}, {1}]",
404 a.getAzimuth(), b.getAzimuth()));
405 }
406 }
407
408 /** Return true if the given cut angles define a convex region. By convention, the
409 * precision context from the min cut is used for the floating point comparison.
410 * @param min min (negative-facing) cut angle
411 * @param max max (positive-facing) cut angle
412 * @return true if the given cut angles define a convex region
413 */
414 private static boolean isConvex(final CutAngle min, final CutAngle max) {
415 if (min != null && max != null) {
416 final double dist = max.getAzimuth() - min.getAzimuth();
417 final Precision.DoubleEquivalence precision = min.getPrecision();
418 return precision.lte(dist, Math.PI);
419 }
420
421 return true;
422 }
423
424 /** Internal transform method that transforms the given instance, using the factory
425 * method to create a new instance if needed.
426 * @param interval interval to transform
427 * @param transform transform to apply
428 * @param factory object used to create new instances
429 * @param <T> Angular interval implementation type
430 * @return a transformed instance
431 */
432 private static <T extends AngularInterval> T transform(final T interval,
433 final Transform<Point1S> transform,
434 final BiFunction<? super CutAngle, ? super CutAngle, T> factory) {
435
436 if (!interval.isFull()) {
437 final CutAngle tMin = interval.getMinBoundary().transform(transform);
438 final CutAngle tMax = interval.getMaxBoundary().transform(transform);
439
440 return factory.apply(tMin, tMax);
441 }
442
443 return interval;
444 }
445
446 /** Class representing an angular interval with the additional property that the
447 * region is convex. By convex, it is meant that the shortest path between any
448 * two points in the region is also contained entirely in the region. If there is
449 * a tie for shortest path, then it is sufficient that at least one lie entirely
450 * within the region. For spherical 1D space, this means that the angular interval
451 * is either completely full or has a length less than or equal to {@code pi}.
452 */
453 public static final class Convex extends AngularInterval {
454 /** Interval instance representing the full space. */
455 private static final Convex FULL = new Convex(null, null);
456
457 /** Construct a new convex instance from its boundaries and midpoint. No validation
458 * of the argument is performed. Callers are responsible for ensuring that the size
459 * of interval is less than or equal to {@code pi}.
460 * @param minBoundary minimum boundary for the interval
461 * @param maxBoundary maximum boundary for the interval
462 * @throws IllegalArgumentException if the interval is not convex
463 */
464 private Convex(final CutAngle minBoundary, final CutAngle maxBoundary) {
465 super(minBoundary, maxBoundary);
466
467 if (!isConvex(minBoundary, maxBoundary)) {
468 throw new IllegalArgumentException(MessageFormat.format("Interval is not convex: [{0}, {1}]",
469 minBoundary.getAzimuth(), maxBoundary.getAzimuth()));
470 }
471 }
472
473 /** {@inheritDoc} */
474 @Override
475 public List<AngularInterval.Convex> toConvex() {
476 return Collections.singletonList(this);
477 }
478
479 /** {@inheritDoc} */
480 @Override
481 public Convex transform(final Transform<Point1S> transform) {
482 return AngularInterval.transform(this, transform, Convex::of);
483 }
484
485 /** Split the instance along a circle diameter.The diameter is defined by the given split point and
486 * its reversed antipodal point.
487 * @param splitter split point defining one side of the split diameter
488 * @return result of the split operation
489 */
490 public Split<Convex> splitDiameter(final CutAngle splitter) {
491
492 final CutAngle opposite = CutAngles.fromPointAndDirection(
493 splitter.getPoint().antipodal(),
494 !splitter.isPositiveFacing(),
495 splitter.getPrecision());
496
497 if (isFull()) {
498 final Convex minus = Convex.of(splitter, opposite);
499 final Convex plus = Convex.of(splitter.reverse(), opposite.reverse());
500
501 return new Split<>(minus, plus);
502 }
503
504 final CutAngle minBoundary = getMinBoundary();
505 final CutAngle maxBoundary = getMaxBoundary();
506
507 final Point1S posPole = Point1S.of(splitter.getPoint().getAzimuth() + Angle.PI_OVER_TWO);
508
509 final int minLoc = minBoundary.getPrecision().compare(Angle.PI_OVER_TWO,
510 posPole.distance(minBoundary.getPoint()));
511 final int maxLoc = maxBoundary.getPrecision().compare(Angle.PI_OVER_TWO,
512 posPole.distance(maxBoundary.getPoint()));
513
514 final boolean positiveFacingSplit = splitter.isPositiveFacing();
515
516 // assume a positive orientation of the splitter for region location
517 // purposes and adjust later
518 Convex pos = null;
519 Convex neg = null;
520
521 if (minLoc > 0) {
522 // min is on the pos side
523
524 if (maxLoc >= 0) {
525 // max is directly on the splitter or on the pos side
526 pos = this;
527 } else {
528 // min is on the pos side and max is on the neg side
529 final CutAngle posCut = positiveFacingSplit ?
530 opposite.reverse() :
531 opposite;
532 pos = Convex.of(minBoundary, posCut);
533
534 final CutAngle negCut = positiveFacingSplit ?
535 opposite :
536 opposite.reverse();
537 neg = Convex.of(negCut, maxBoundary);
538 }
539 } else if (minLoc < 0) {
540 // min is on the neg side
541
542 if (maxLoc <= 0) {
543 // max is directly on the splitter or on the neg side
544 neg = this;
545 } else {
546 // min is on the neg side and max is on the pos side
547 final CutAngle posCut = positiveFacingSplit ?
548 splitter.reverse() :
549 splitter;
550 pos = Convex.of(maxBoundary, posCut);
551
552 final CutAngle negCut = positiveFacingSplit ?
553 splitter :
554 splitter.reverse();
555 neg = Convex.of(negCut, minBoundary);
556 }
557 } else {
558 // min is directly on the splitter; determine whether it was on the main split
559 // point or its antipodal point
560 if (splitter.getPoint().distance(minBoundary.getPoint()) < Angle.PI_OVER_TWO) {
561 // on main splitter; interval will be located on pos side of split
562 pos = this;
563 } else {
564 // on antipodal point; interval will be located on neg side of split
565 neg = this;
566 }
567 }
568
569 // adjust for the actual orientation of the splitter
570 final Convex minus = positiveFacingSplit ? neg : pos;
571 final Convex plus = positiveFacingSplit ? pos : neg;
572
573 return new Split<>(minus, plus);
574 }
575
576 /** Return an instance representing the convex angular interval between the given min and max azimuth
577 * values. The max value is adjusted to be numerically above the min value, even if the resulting
578 * azimuth value is greater than or equal to {@code 2pi}. An instance representing the full space
579 * is returned if either point is infinite or min and max are equivalent as evaluated by the
580 * given precision context.
581 * @param min min azimuth value
582 * @param max max azimuth value
583 * @param precision precision precision context used to compare floating point values
584 * @return a new instance resulting the angular region between the given min and max azimuths
585 * @throws IllegalArgumentException if either azimuth is infinite or NaN, or the given angular
586 * interval is not convex (meaning it has a size of greater than {@code pi})
587 */
588 public static Convex of(final double min, final double max, final Precision.DoubleEquivalence precision) {
589 return of(Point1S.of(min), Point1S.of(max), precision);
590 }
591
592 /** Return an instance representing the convex angular interval between the given min and max azimuth
593 * points. The max point is adjusted to be numerically above the min point, even if the resulting
594 * azimuth value is greater than or equal to {@code 2pi}. An instance representing the full space
595 * is returned if either point is infinite or min and max are equivalent as evaluated by the
596 * given precision context.
597 * @param min min azimuth value
598 * @param max max azimuth value
599 * @param precision precision precision context used to compare floating point values
600 * @return a new instance resulting the angular region between the given min and max points
601 * @throws IllegalArgumentException if either azimuth is infinite or NaN, or the given angular
602 * interval is not convex (meaning it has a size of greater than {@code pi})
603 */
604 public static Convex of(final Point1S min, final Point1S max, final Precision.DoubleEquivalence precision) {
605 return createInterval(min, max, precision, Convex::new, Convex.FULL);
606 }
607
608 /** Return an instance representing the convex angular interval between the given oriented points.
609 * The negative-facing point is used as the minimum boundary and the positive-facing point is
610 * adjusted to be above the minimum. The arguments can be given in any order. The full space
611 * is returned if the points are equivalent or are oriented in the same direction.
612 * @param a first oriented point
613 * @param b second oriented point
614 * @return an instance representing the angular interval between the given oriented points
615 * @throws IllegalArgumentException if either azimuth is infinite or NaN, or the given angular
616 * interval is not convex (meaning it has a size of greater than {@code pi})
617 */
618 public static Convex of(final CutAngle a, final CutAngle b) {
619 return createInterval(a, b, Convex::new, Convex.FULL);
620 }
621 }
622 }