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.twod;
18
19 import java.text.MessageFormat;
20 import java.util.ArrayList;
21 import java.util.Arrays;
22 import java.util.Collection;
23 import java.util.Collections;
24 import java.util.List;
25 import java.util.stream.Stream;
26
27 import org.apache.commons.numbers.core.Precision;
28
29 /** Class representing a connected sequence of {@link GreatArc} instances.
30 */
31 public final class GreatArcPath implements BoundarySource2S {
32 /** Instance containing no arcs. */
33 private static final GreatArcPath EMPTY = new GreatArcPath(Collections.emptyList());
34
35 /** Arcs comprising the instance. */
36 private final List<GreatArc> arcs;
37
38 /** Simple constructor. No validation is performed on the input arc.
39 * @param arcs arcs for the path, in connection order
40 */
41 private GreatArcPath(final List<GreatArc> arcs) {
42 this.arcs = Collections.unmodifiableList(arcs);
43 }
44
45 /** {@inheritDoc} */
46 @Override
47 public Stream<GreatArc> boundaryStream() {
48 return getArcs().stream();
49 }
50
51 /** Get the arcs in path.
52 * @return the arcs in the path
53 */
54 public List<GreatArc> getArcs() {
55 return arcs;
56 }
57
58 /** Get the start arc for the path or null if the path is empty.
59 * @return the start arc for the path or null if the path is empty
60 */
61 public GreatArc getStartArc() {
62 if (!isEmpty()) {
63 return arcs.get(0);
64 }
65 return null;
66 }
67
68 /** Get the end arc for the path or null if the path is empty.
69 * @return the end arc for the path or null if the path is empty
70 */
71 public GreatArc getEndArc() {
72 if (!isEmpty()) {
73 return arcs.get(arcs.size() - 1);
74 }
75 return null;
76 }
77
78 /** Get the start vertex for the path or null if the path is empty
79 * or consists of a single, full arc.
80 * @return the start vertex for the path
81 */
82 public Point2S getStartVertex() {
83 final GreatArc arc = getStartArc();
84 return (arc != null) ? arc.getStartPoint() : null;
85 }
86
87 /** Get the end vertex for the path or null if the path is empty
88 * or consists of a single, full arc.
89 * @return the end vertex for the path
90 */
91 public Point2S getEndVertex() {
92 final GreatArc arc = getEndArc();
93 return (arc != null) ? arc.getEndPoint() : null;
94 }
95
96 /** Get the vertices contained in the path in the order they appear.
97 * Closed paths contain the start vertex at the beginning of the list
98 * as well as the end.
99 * @return the vertices contained in the path in order they appear
100 */
101 public List<Point2S> getVertices() {
102 final List<Point2S> vertices = new ArrayList<>();
103
104 Point2S pt;
105
106 // add the start point, if present
107 pt = getStartVertex();
108 if (pt != null) {
109 vertices.add(pt);
110 }
111
112 // add end points
113 for (final GreatArc arc : arcs) {
114 pt = arc.getEndPoint();
115 if (pt != null) {
116 vertices.add(pt);
117 }
118 }
119
120 return vertices;
121 }
122
123 /** Return true if the path does not contain any arcs.
124 * @return true if the path does not contain any arcs
125 */
126 public boolean isEmpty() {
127 return arcs.isEmpty();
128 }
129
130 /** Return true if the path is closed, meaning that the end
131 * point for the last arc is equal to the start point
132 * for the path.
133 * @return true if the end point for the last arc is
134 * equal to the start point for the path
135 */
136 public boolean isClosed() {
137 final GreatArc endArc = getEndArc();
138
139 if (endArc != null) {
140 final Point2S start = getStartVertex();
141 final Point2S end = endArc.getEndPoint();
142
143 return start != null && end != null && start.eq(end, endArc.getPrecision());
144 }
145
146 return false;
147 }
148
149 /** Return a string representation of this arc path instance.
150 *
151 * <p>In order to keep the string representation short but useful, the exact format of the return
152 * value depends on the properties of the path. See below for examples.
153 *
154 * <ul>
155 * <li>Empty path
156 * <ul>
157 * <li>{@code GreatArcPath[empty= true]}</li>
158 * </ul>
159 * </li>
160 * <li>Single, full arc
161 * <ul>
162 * <li>{@code GreatArcPath[full= true, circle= GreatCircle[pole= (0.0, 0.0, 1.0),
163 * x= (0.0, 1.0, -0.0), y= (-1.0, 0.0, 0.0)]]}</li>
164 * </ul>
165 * </li>
166 * <li>One or more non-full arcs
167 * <ul>
168 * <li>{@code GreatArcPath[vertices= [(0.0, 1.5707963267948966),
169 * (1.5707963267948966, 1.5707963267948966)]]}</li>
170 * </ul>
171 * </li>
172 * </ul>
173 */
174 @Override
175 public String toString() {
176 final StringBuilder sb = new StringBuilder();
177 sb.append(this.getClass().getSimpleName())
178 .append('[');
179
180 if (isEmpty()) {
181 sb.append("empty= true");
182 } else if (arcs.size() == 1 && arcs.get(0).isFull()) {
183 sb.append("full= true, circle= ")
184 .append(arcs.get(0).getCircle());
185 } else {
186 sb.append("vertices= ")
187 .append(getVertices());
188 }
189
190 sb.append(']');
191
192 return sb.toString();
193 }
194
195 /** Construct a new path from the given arcs.
196 * @param arcs arc instance to use to construct the path
197 * @return a new instance constructed from the given arc instances
198 */
199 public static GreatArcPath fromArcs(final GreatArc... arcs) {
200 return fromArcs(Arrays.asList(arcs));
201 }
202
203 /** Construct a new path from the given arcs.
204 * @param arcs arc instance to use to construct the path
205 * @return a new instance constructed from the given arc instances
206 */
207 public static GreatArcPath fromArcs(final Collection<GreatArc> arcs) {
208 final Builder builder = builder(null);
209 for (final GreatArc arc : arcs) {
210 builder.append(arc);
211 }
212
213 return builder.build();
214 }
215
216 /** Return a new path formed by connecting the given vertices. An additional arc is added
217 * from the last point to the first point to construct a loop, if the two points are not
218 * already considered equal by the given precision context. This method is equivalent
219 * to calling {@link #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
220 * fromPoints(points, true, precision)}.
221 * @param vertices the points to construct the path from
222 * @param precision precision precision context used to construct the arc instances for the
223 * path
224 * @return a new path formed by connecting the given vertices
225 * @see #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
226 */
227 public static GreatArcPath fromVertexLoop(final Collection<Point2S> vertices,
228 final Precision.DoubleEquivalence precision) {
229 return fromVertices(vertices, true, precision);
230 }
231
232 /** Return a new path formed by connecting the given vertices. No additional arc
233 * is inserted to connect the last point to the first. This method is equivalent
234 * to calling {@link #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
235 * fromPoint(points, false, precision)}.
236 * @param vertices the points to construct the path from
237 * @param precision precision context used to construct the arc instances for the
238 * path
239 * @return a new path formed by connecting the given vertices
240 * @see #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
241 */
242 public static GreatArcPath fromVertices(final Collection<Point2S> vertices,
243 final Precision.DoubleEquivalence precision) {
244 return fromVertices(vertices, false, precision);
245 }
246
247 /** Return a new path formed by connecting the given vertices.
248 * @param vertices the points to construct the path from
249 * @param close if true, then an additional arc will be added from the last point
250 * to the first, if the points are not already considered equal by the given
251 * precision context
252 * @param precision precision context used to construct the arc instances for the
253 * path
254 * @return a new path formed by connecting the given points
255 */
256 public static GreatArcPath fromVertices(final Collection<Point2S> vertices, final boolean close,
257 final Precision.DoubleEquivalence precision) {
258
259 return builder(precision)
260 .appendVertices(vertices)
261 .build(close);
262 }
263
264 /** Return a {@link Builder} instance configured with the given precision
265 * context. The precision context is used when building arcs from points
266 * and may be omitted if raw points are not used.
267 * @param precision precision context to use when building arcs from
268 * raw points; may be null if raw points are not used.
269 * @return a new {@link Builder} instance
270 */
271 public static Builder builder(final Precision.DoubleEquivalence precision) {
272 return new Builder(precision);
273 }
274
275 /** Get an instance containing no arcs.
276 * @return an instance containing no arcs
277 */
278 public static GreatArcPath empty() {
279 return EMPTY;
280 }
281
282 /** Class used to build arc paths.
283 */
284 public static final class Builder {
285 /** Arcs appended to the path. */
286 private List<GreatArc> appendedArcs;
287
288 /** Arcs prepended to the path. */
289 private List<GreatArc> prependedArcs;
290
291 /** Precision context used when creating arcs directly from points. */
292 private Precision.DoubleEquivalence precision;
293
294 /** The current point at the start of the path. */
295 private Point2S startVertex;
296
297 /** The current point at the end of the path. */
298 private Point2S endVertex;
299
300 /** The precision context used when performing comparisons involving the current
301 * end point.
302 */
303 private Precision.DoubleEquivalence endVertexPrecision;
304
305 /** Construct a new instance configured with the given precision context. The
306 * precision context is used when building arcs from points and
307 * may be omitted if raw points are not used.
308 * @param precision precision context to use when creating arcs
309 * from points
310 */
311 private Builder(final Precision.DoubleEquivalence precision) {
312 setPrecision(precision);
313 }
314
315 /** Set the precision context. This context is used only when creating arcs
316 * from appended or prepended points. It is not used when adding existing
317 * {@link GreatArc} instances since those contain their own precision contexts.
318 * @param builderPrecision precision context to use when creating arcs from points
319 * @return this instance
320 */
321 public Builder setPrecision(final Precision.DoubleEquivalence builderPrecision) {
322 this.precision = builderPrecision;
323
324 return this;
325 }
326
327 /** Get the arc at the start of the path or null if it does not exist.
328 * @return the arc at the start of the path
329 */
330 public GreatArc getStartArc() {
331 GreatArc start = getLast(prependedArcs);
332 if (start == null) {
333 start = getFirst(appendedArcs);
334 }
335 return start;
336 }
337
338 /** Get the arc at the end of the path or null if it does not exist.
339 * @return the arc at the end of the path
340 */
341 public GreatArc getEndArc() {
342 GreatArc end = getLast(appendedArcs);
343 if (end == null) {
344 end = getFirst(prependedArcs);
345 }
346 return end;
347 }
348
349 /** Append an arc to the end of the path.
350 * @param arc arc to append to the path
351 * @return the current builder instance
352 * @throws IllegalStateException if the path contains a previous arc
353 * and the end point of the previous arc is not equivalent to the
354 * start point of the given arc
355 */
356 public Builder append(final GreatArc arc) {
357 validateArcsConnected(getEndArc(), arc);
358 appendInternal(arc);
359
360 return this;
361 }
362
363 /** Add a vertex to the end of this path. If the path already has an end vertex,
364 * then an arc is added between the previous end vertex and this vertex,
365 * using the configured precision context.
366 * @param vertex the vertex to add
367 * @return this instance
368 * @see #setPrecision(Precision.DoubleEquivalence)
369 */
370 public Builder append(final Point2S vertex) {
371 final Precision.DoubleEquivalence vertexPrecision = getAddPointPrecision();
372
373 if (endVertex == null) {
374 // make sure that we're not adding to a full arc
375 final GreatArc end = getEndArc();
376 if (end != null) {
377 throw new IllegalStateException(
378 MessageFormat.format("Cannot add point {0} after full arc: {1}", vertex, end));
379 }
380
381 // this is the first vertex added
382 startVertex = vertex;
383 endVertex = vertex;
384 endVertexPrecision = vertexPrecision;
385 } else if (!endVertex.eq(vertex, vertexPrecision)) {
386 // only add the vertex if its not equal to the end point
387 // of the last arc
388 appendInternal(GreatCircles.arcFromPoints(endVertex, vertex, endVertexPrecision));
389 }
390
391 return this;
392 }
393
394 /** Convenience method for appending a collection of vertices to the path in a single
395 * method call.
396 * @param vertices the vertices to append
397 * @return this instance
398 * @see #append(Point2S)
399 */
400 public Builder appendVertices(final Collection<Point2S> vertices) {
401 for (final Point2S vertex : vertices) {
402 append(vertex);
403 }
404
405 return this;
406 }
407
408 /** Convenience method for appending multiple vertices to the path at once.
409 * @param vertices the points to append
410 * @return this instance
411 * @see #append(Point2S)
412 */
413 public Builder appendVertices(final Point2S... vertices) {
414 return appendVertices(Arrays.asList(vertices));
415 }
416
417 /** Prepend an arc to the beginning of the path.
418 * @param arc arc to prepend to the path
419 * @return the current builder instance
420 * @throws IllegalStateException if the path contains a start arc
421 * and the end point of the given arc is not equivalent to the
422 * start point of the start arc
423 */
424 public Builder prepend(final GreatArc arc) {
425 validateArcsConnected(arc, getStartArc());
426 prependInternal(arc);
427
428 return this;
429 }
430
431 /** Add a vertex to the front of this path. If the path already has a start vertex,
432 * then an arc is added between this vertex and the previous start vertex,
433 * using the configured precision context.
434 * @param vertex the vertex to add
435 * @return this instance
436 * @see #setPrecision(Precision.DoubleEquivalence)
437 */
438 public Builder prepend(final Point2S vertex) {
439 final Precision.DoubleEquivalence vertexPrecision = getAddPointPrecision();
440
441 if (startVertex == null) {
442 // make sure that we're not adding to a full arc
443 final GreatArc start = getStartArc();
444 if (start != null) {
445 throw new IllegalStateException(
446 MessageFormat.format("Cannot add point {0} before full arc: {1}", vertex, start));
447 }
448
449 // this is the first vertex added
450 startVertex = vertex;
451 endVertex = vertex;
452 endVertexPrecision = vertexPrecision;
453 } else if (!vertex.eq(startVertex, vertexPrecision)) {
454 // only add if the vertex is not equal to the start
455 // point of the first arc
456 prependInternal(GreatCircles.arcFromPoints(vertex, startVertex, vertexPrecision));
457 }
458
459 return this;
460 }
461
462 /** Convenience method for prepending a collection of vertices to the path in a single method call.
463 * The vertices are logically prepended as a single group, meaning that the first vertex
464 * in the given collection appears as the first vertex in the path after this method call.
465 * Internally, this means that the vertices are actually passed to the {@link #prepend(Point2S)}
466 * method in reverse order.
467 * @param vertices the points to prepend
468 * @return this instance
469 * @see #prepend(Point2S)
470 */
471 public Builder prependPoints(final Collection<Point2S> vertices) {
472 return prependPoints(vertices.toArray(new Point2S[0]));
473 }
474
475 /** Convenience method for prepending multiple vertices to the path in a single method call.
476 * The vertices are logically prepended as a single group, meaning that the first vertex
477 * in the given collection appears as the first vertex in the path after this method call.
478 * Internally, this means that the vertices are actually passed to the {@link #prepend(Point2S)}
479 * method in reverse order.
480 * @param vertices the vertices to prepend
481 * @return this instance
482 * @see #prepend(Point2S)
483 */
484 public Builder prependPoints(final Point2S... vertices) {
485 for (int i = vertices.length - 1; i >= 0; --i) {
486 prepend(vertices[i]);
487 }
488
489 return this;
490 }
491
492 /** Close the current path and build a new {@link GreatArcPath} instance. This method is equivalent
493 * to {@code builder.build(true)}.
494 * @return new closed path instance
495 */
496 public GreatArcPath close() {
497 return build(true);
498 }
499
500 /** Build a {@link GreatArcPath} instance from the configured path. This method is equivalent
501 * to {@code builder.build(false)}.
502 * @return new path instance
503 */
504 public GreatArcPath build() {
505 return build(false);
506 }
507
508 /** Build a {@link GreatArcPath} instance from the configured path.
509 * @param close if true, the path will be closed by adding an end point equivalent to the
510 * start point
511 * @return new path instance
512 */
513 public GreatArcPath build(final boolean close) {
514 if (close) {
515 closePath();
516 }
517
518 // combine all of the arcs
519 List<GreatArc> result = null;
520
521 if (prependedArcs != null) {
522 result = prependedArcs;
523 Collections.reverse(result);
524 }
525
526 if (appendedArcs != null) {
527 if (result == null) {
528 result = appendedArcs;
529 } else {
530 result.addAll(appendedArcs);
531 }
532 }
533
534 if (result == null) {
535 result = Collections.emptyList();
536 }
537
538 if (result.isEmpty() && startVertex != null) {
539 throw new IllegalStateException(
540 MessageFormat.format("Unable to create path; only a single point provided: {0}",
541 startVertex));
542 }
543
544 // clear internal state
545 appendedArcs = null;
546 prependedArcs = null;
547
548 // build the final path instance, using the shared empty instance if
549 // no arcs are present
550 return result.isEmpty() ? empty() : new GreatArcPath(result);
551 }
552
553 /** Close the path by adding an end point equivalent to the path start point.
554 * @throws IllegalStateException if the path cannot be closed
555 */
556 private void closePath() {
557 final GreatArc end = getEndArc();
558
559 if (end != null) {
560 if (startVertex != null && endVertex != null) {
561 if (!endVertex.eq(startVertex, endVertexPrecision)) {
562 appendInternal(GreatCircles.arcFromPoints(endVertex, startVertex, endVertexPrecision));
563 }
564 } else {
565 throw new IllegalStateException("Unable to close path: path is full");
566 }
567 }
568 }
569
570 /** Validate that the given arcs are connected, meaning that the end point of {@code previous}
571 * is equivalent to the start point of {@code next}. The arcs are considered valid if either
572 * arc is null.
573 * @param previous previous arc
574 * @param next next arc
575 * @throws IllegalStateException if previous and next are not null and the end point of previous
576 * is not equivalent the start point of next
577 */
578 private void validateArcsConnected(final GreatArc previous, final GreatArc next) {
579 if (previous != null && next != null) {
580 final Point2S nextStartVertex = next.getStartPoint();
581 final Point2S previousEndVertex = previous.getEndPoint();
582 final Precision.DoubleEquivalence previousPrecision = previous.getPrecision();
583
584 if (nextStartVertex == null || previousEndVertex == null ||
585 !(nextStartVertex.eq(previousEndVertex, previousPrecision))) {
586
587 throw new IllegalStateException(
588 MessageFormat.format("Path arcs are not connected: previous= {0}, next= {1}",
589 previous, next));
590 }
591 }
592 }
593
594 /** Get the precision context used when adding raw points to the path. An exception is thrown
595 * if no precision has been specified.
596 * @return the precision context used when working with raw points
597 * @throws IllegalStateException if no precision context is configured
598 */
599 private Precision.DoubleEquivalence getAddPointPrecision() {
600 if (precision == null) {
601 throw new IllegalStateException("Unable to create arc: no point precision specified");
602 }
603
604 return precision;
605 }
606
607 /** Append the given, validated arc to the path.
608 * @param arc validated arc to append
609 */
610 private void appendInternal(final GreatArc arc) {
611 if (appendedArcs == null) {
612 appendedArcs = new ArrayList<>();
613 }
614
615 if (appendedArcs.isEmpty() &&
616 (prependedArcs == null || prependedArcs.isEmpty())) {
617 startVertex = arc.getStartPoint();
618 }
619
620 endVertex = arc.getEndPoint();
621 endVertexPrecision = arc.getPrecision();
622
623 appendedArcs.add(arc);
624 }
625
626 /** Prepend the given, validated arc to the path.
627 * @param arc validated arc to prepend
628 */
629 private void prependInternal(final GreatArc arc) {
630 if (prependedArcs == null) {
631 prependedArcs = new ArrayList<>();
632 }
633
634 startVertex = arc.getStartPoint();
635
636 if (prependedArcs.isEmpty() &&
637 (appendedArcs == null || appendedArcs.isEmpty())) {
638 endVertex = arc.getEndPoint();
639 endVertexPrecision = arc.getPrecision();
640 }
641
642 prependedArcs.add(arc);
643 }
644
645 /** Get the first element in the list or null if the list is null
646 * or empty.
647 * @param list the list to return the first item from
648 * @return the first item from the given list or null if it does not exist
649 */
650 private GreatArc getFirst(final List<GreatArc> list) {
651 if (list != null && !list.isEmpty()) {
652 return list.get(0);
653 }
654 return null;
655 }
656
657 /** Get the last element in the list or null if the list is null
658 * or empty.
659 * @param list the list to return the last item from
660 * @return the last item from the given list or null if it does not exist
661 */
662 private GreatArc getLast(final List<GreatArc> list) {
663 if (list != null && !list.isEmpty()) {
664 return list.get(list.size() - 1);
665 }
666 return null;
667 }
668 }
669 }