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.euclidean.twod.path;
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.Collectors;
26 import java.util.stream.Stream;
27
28 import org.apache.commons.geometry.core.Sized;
29 import org.apache.commons.geometry.core.Transform;
30 import org.apache.commons.geometry.euclidean.twod.BoundarySource2D;
31 import org.apache.commons.geometry.euclidean.twod.Line;
32 import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
33 import org.apache.commons.geometry.euclidean.twod.Lines;
34 import org.apache.commons.geometry.euclidean.twod.Vector2D;
35 import org.apache.commons.numbers.core.Precision;
36
37 /** Class representing a connected path of {@link LineConvexSubset line convex subsets}.
38 * The elements in the path are connected end to end, with the end vertex of the previous
39 * element equivalent to the start vertex of the next element. Elements are not required to
40 * be finite. However, since path elements are connected, only the first element and/or last
41 * element may be infinite.
42 *
43 * <p>Instances of this class are guaranteed to be immutable.</p>
44 */
45 public class LinePath implements BoundarySource2D, Sized {
46 /** Line path instance containing no elements. */
47 private static final LinePath EMPTY = new LinePath(Collections.emptyList());
48
49 /** The line convex subsets comprising the path. */
50 private final List<LineConvexSubset> elements;
51
52 /** Simple constructor. Callers are responsible for ensuring that the given list of
53 * line subsets defines a valid path. No validation is performed.
54 * @param elements elements defining the path.
55 */
56 LinePath(final List<LineConvexSubset> elements) {
57 this.elements = Collections.unmodifiableList(elements);
58 }
59
60 /** {@inheritDoc} */
61 @Override
62 public Stream<LineConvexSubset> boundaryStream() {
63 return getElements().stream();
64 }
65
66 /** Get the sequence of line subsets comprising the path.
67 * @return the sequence of line subsets comprising the path
68 */
69 public List<LineConvexSubset> getElements() {
70 return elements;
71 }
72
73 /** Get the line subset at the start of the path or null if the path is empty. If the
74 * path consists of a single line subset, then the returned instance with be the same
75 * as that returned by {@link #getEnd()}.
76 * @return the line subset at the start of the path or null if the path is empty
77 * @see #getEnd()
78 */
79 public LineConvexSubset getStart() {
80 if (!isEmpty()) {
81 return elements.get(0);
82 }
83 return null;
84 }
85
86 /** Get the line subset at the end of the path or null if the path is empty. If the
87 * path consists of a single line subset, then the returned instance with be the same
88 * as that returned by {@link #getStart()}.
89 * @return the line subset at the end of the path or null if the path is empty
90 * @see #getStart()
91 */
92 public LineConvexSubset getEnd() {
93 if (!isEmpty()) {
94 return elements.get(elements.size() - 1);
95 }
96 return null;
97 }
98
99 /** Get the sequence of vertices defined by the path. Vertices appear in the
100 * list as many times as they are visited in the path. For example, the vertex
101 * sequence for a closed path contains the start point at the beginning
102 * of the list as well as the end.
103 * @return the sequence of vertices defined by the path
104 */
105 public List<Vector2D> getVertexSequence() {
106 final List<Vector2D> sequence = new ArrayList<>();
107
108 Vector2D pt;
109
110 // add the start point, if present
111 pt = getStartVertex();
112 if (pt != null) {
113 sequence.add(pt);
114 }
115
116 // add end points
117 for (final LineConvexSubset sub : elements) {
118 pt = sub.getEndPoint();
119 if (pt != null) {
120 sequence.add(pt);
121 }
122 }
123
124 return sequence;
125 }
126
127 /** Return true if the path has an element with infinite size.
128 * @return true if the path is infinite
129 */
130 @Override
131 public boolean isInfinite() {
132 return !isEmpty() && (getStartVertex() == null || getEndVertex() == null);
133 }
134
135 /** Return true if the path has a finite size. This will be true if there are
136 * no elements in the path or if all elements have a finite length.
137 * @return true if the path is finite
138 */
139 @Override
140 public boolean isFinite() {
141 return !isInfinite();
142 }
143
144 /** {@inheritDoc}
145 *
146 * <p>The size of the path is defined as the sum of the sizes (lengths) of all path elements.</p>
147 */
148 @Override
149 public double getSize() {
150 double sum = 0.0;
151 for (final LineConvexSubset element : elements) {
152 sum += element.getSize();
153 }
154
155 return sum;
156 }
157
158 /** Return true if the path does not contain any elements.
159 * @return true if the path does not contain any elements
160 */
161 public boolean isEmpty() {
162 return elements.isEmpty();
163 }
164
165 /** Return true if the path is closed, meaning that the end point for the last
166 * element is equivalent to the start point of the first.
167 * @return true if the end point for the last element is equivalent to the
168 * start point for the first
169 */
170 public boolean isClosed() {
171 final LineConvexSubset endElement = getEnd();
172
173 if (endElement != null) {
174 final Vector2D start = getStartVertex();
175 final Vector2D end = endElement.getEndPoint();
176
177 return start != null && end != null && start.eq(end, endElement.getPrecision());
178 }
179
180 return false;
181 }
182
183 /** Transform this instance with the argument, returning the result in a new instance.
184 * @param transform the transform to apply
185 * @return a new instance, transformed by the argument
186 */
187 public LinePath transform(final Transform<Vector2D> transform) {
188 if (!isEmpty()) {
189 final List<LineConvexSubset> transformed = elements.stream()
190 .map(s -> s.transform(transform))
191 .collect(Collectors.toCollection(ArrayList::new));
192
193 return new LinePath(transformed);
194 }
195
196 return this;
197 }
198
199 /** Return a new instance with all line subset directions, and their order,
200 * reversed. The last line subset in this instance will be the first in the
201 * returned instance.
202 * @return a new instance with the path reversed
203 */
204 public LinePath reverse() {
205 if (!isEmpty()) {
206 final List<LineConvexSubset> reversed = elements.stream()
207 .map(LineConvexSubset::reverse)
208 .collect(Collectors.toCollection(ArrayList::new));
209 Collections.reverse(reversed);
210
211 return new LinePath(reversed);
212 }
213
214 return this;
215 }
216
217 /** Simplify this path, if possible, by combining adjacent elements that lie on the
218 * same line (as determined by {@link Line#equals(Object)}).
219 * @return a simplified instance
220 */
221 public LinePath simplify() {
222 final List<LineConvexSubset> simplified = new ArrayList<>();
223
224 final int size = elements.size();
225
226 LineConvexSubset current;
227 Line currentLine;
228 double end;
229
230 int idx = 0;
231 int testIdx;
232 while (idx < size) {
233 current = elements.get(idx);
234 currentLine = current.getLine();
235 end = current.getSubspaceEnd();
236
237 // try to combine with forward neighbors
238 testIdx = idx + 1;
239 while (testIdx < size && currentLine.equals(elements.get(testIdx).getLine())) {
240 end = Math.max(end, elements.get(testIdx).getSubspaceEnd());
241 ++testIdx;
242 }
243
244 if (testIdx > idx + 1) {
245 // we found something to merge
246 simplified.add(Lines.subsetFromInterval(currentLine, current.getSubspaceStart(), end));
247 } else {
248 simplified.add(current);
249 }
250
251 idx = testIdx;
252 }
253
254 // combine the first and last items if needed
255 if (isClosed() && simplified.size() > 2 && simplified.get(0).getLine().equals(
256 simplified.get(simplified.size() - 1).getLine())) {
257
258 final LineConvexSubset startElement = simplified.get(0);
259 final LineConvexSubset endElement = simplified.remove(simplified.size() - 1);
260
261 final LineConvexSubset combined = Lines.subsetFromInterval(
262 endElement.getLine(), endElement.getSubspaceStart(), startElement.getSubspaceEnd());
263
264 simplified.set(0, combined);
265 }
266
267 return new SimplifiedLinePath(simplified);
268 }
269
270 /** Return a string representation of the path.
271 *
272 * <p>In order to keep the string representation short but useful, the exact format of the return
273 * value depends on the properties of the path. See below for examples.
274 *
275 * <ul>
276 * <li>Empty path
277 * <ul>
278 * <li>{@code LinePath[empty= true]}</li>
279 * </ul>
280 * </li>
281 * <li>Single element
282 * <ul>
283 * <li>{@code LinePath[single= Segment[startPoint= (0.0, 0.0), endPoint= (1.0, 0.0)]]}</li>
284 * </ul>
285 * </li>
286 * <li>Path with infinite start element
287 * <ul>
288 * <li>{@code LinePath[startDirection= (1.0, 0.0), vertices= [(1.0, 0.0), (1.0, 1.0)]]}</li>
289 * </ul>
290 * </li>
291 * <li>Path with infinite end element
292 * <ul>
293 * <li>{@code LinePath[vertices= [(0.0, 1.0), (0.0, 0.0)], endDirection= (1.0, 0.0)]}</li>
294 * </ul>
295 * </li>
296 * <li>Path with infinite start and end elements
297 * <ul>
298 * <li>{@code LinePath[startDirection= (0.0, 1.0), vertices= [(0.0, 0.0)], endDirection= (1.0, 0.0)]}</li>
299 * </ul>
300 * </li>
301 * <li>Path with no infinite elements
302 * <ul>
303 * <li>{@code LinePath[vertices= [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0)]]}</li>
304 * </ul>
305 * </li>
306 * </ul>
307 */
308 @Override
309 public String toString() {
310 final StringBuilder sb = new StringBuilder();
311 sb.append(this.getClass().getSimpleName())
312 .append('[');
313
314 if (elements.isEmpty()) {
315 sb.append("empty= true");
316 } else if (elements.size() == 1) {
317 sb.append("single= ")
318 .append(elements.get(0));
319 } else {
320 final LineConvexSubset startElement = getStart();
321 if (startElement.getStartPoint() == null) {
322 sb.append("startDirection= ")
323 .append(startElement.getLine().getDirection())
324 .append(", ");
325 }
326
327 sb.append("vertexSequence= ")
328 .append(getVertexSequence());
329
330 final LineConvexSubset endElement = getEnd();
331 if (endElement.getEndPoint() == null) {
332 sb.append(", endDirection= ")
333 .append(endElement.getLine().getDirection());
334 }
335 }
336
337 sb.append(']');
338
339 return sb.toString();
340 }
341
342 /** Get the start vertex for the path or null if the path is empty
343 * or has an infinite start line subset.
344 * @return the start vertex for the path or null if the path does
345 * not start with a vertex
346 */
347 private Vector2D getStartVertex() {
348 final LineConvexSubset seg = getStart();
349 return (seg != null) ? seg.getStartPoint() : null;
350 }
351
352 /** Get the end vertex for the path or null if the path is empty
353 * or has an infinite end line subset.
354 * @return the end vertex for the path or null if the path does
355 * not end with a vertex
356 */
357 private Vector2D getEndVertex() {
358 final LineConvexSubset seg = getEnd();
359 return (seg != null) ? seg.getEndPoint() : null;
360 }
361
362 /** Build a new path from the given line subsets.
363 * @param subsets the line subsets to comprise the path
364 * @return new path containing the given line subsets in order
365 * @throws IllegalStateException if the line subsets do not form a connected path
366 */
367 public static LinePath from(final LineConvexSubset... subsets) {
368 return from(Arrays.asList(subsets));
369 }
370
371 /** Build a new path from the given line subsets.
372 * @param subsets the line subsets to comprise the path
373 * @return new path containing the given line subsets in order
374 * @throws IllegalStateException if the subsets do not form a connected path
375 */
376 public static LinePath from(final Collection<? extends LineConvexSubset> subsets) {
377 final Builder builder = builder(null);
378
379 for (final LineConvexSubset subset : subsets) {
380 builder.append(subset);
381 }
382
383 return builder.build();
384 }
385
386 /** Build a new path from the given vertices. A line segment is created
387 * from the last vertex to the first one, if the two vertices are not already
388 * considered equal using the given precision context. This method is equivalent to
389 * calling {@link #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
390 * fromVertices(vertices, true, precision)}
391 * @param vertices the vertices to construct the closed path from
392 * @param precision precision context used to construct the line segment
393 * instances for the path
394 * @return new closed path constructed from the given vertices
395 * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
396 * @see #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
397 */
398 public static LinePath fromVertexLoop(final Collection<Vector2D> vertices,
399 final Precision.DoubleEquivalence precision) {
400
401 return fromVertices(vertices, true, precision);
402 }
403
404 /** Build a new path from the given vertices. No additional segment is added
405 * from the last vertex to the first. This method is equivalent to calling
406 * {@link #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
407 * fromVertices(vertices, false, precision)}.
408 * @param vertices the vertices to construct the path from
409 * @param precision precision context used to construct the line segment
410 * instances for the path
411 * @return new path constructed from the given vertices
412 * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
413 * @see #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
414 */
415 public static LinePath fromVertices(final Collection<Vector2D> vertices,
416 final Precision.DoubleEquivalence precision) {
417
418 return fromVertices(vertices, false, precision);
419 }
420
421 /** Build a new path from the given vertices.
422 * @param vertices the vertices to construct the path from
423 * @param close if true, a line segment is created from the last vertex
424 * given to the first one, if the two vertices are not already considered
425 * equal using the given precision context.
426 * @param precision precision context used to construct the line segment
427 * instances for the path
428 * @return new path constructed from the given vertices
429 * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
430 */
431 public static LinePath fromVertices(final Collection<Vector2D> vertices,
432 final boolean close, final Precision.DoubleEquivalence precision) {
433
434 return builder(precision)
435 .appendVertices(vertices)
436 .build(close);
437 }
438
439 /** Return a path containing no elements.
440 * @return a path containing no elements
441 */
442 public static LinePath empty() {
443 return EMPTY;
444 }
445
446 /** Return a {@link Builder} instance configured with the given precision
447 * context. The precision context is used when building line segments from
448 * vertices and may be omitted if raw vertices are not used.
449 * @param precision precision context to use when building line segments from
450 * raw vertices; may be null if raw vertices are not used.
451 * @return a new {@link Builder} instance
452 */
453 public static Builder builder(final Precision.DoubleEquivalence precision) {
454 return new Builder(precision);
455 }
456
457 /** Class used to build line paths.
458 */
459 public static final class Builder {
460 /** Line subsets appended to the path. */
461 private List<LineConvexSubset> appended;
462
463 /** Line subsets prepended to the path. */
464 private List<LineConvexSubset> prepended;
465
466 /** Precision context used when creating line segments directly from vertices. */
467 private Precision.DoubleEquivalence precision;
468
469 /** The current vertex at the start of the path. */
470 private Vector2D startVertex;
471
472 /** The current vertex at the end of the path. */
473 private Vector2D endVertex;
474
475 /** The precision context used when performing comparisons involving the current
476 * end vertex.
477 */
478 private Precision.DoubleEquivalence endVertexPrecision;
479
480 /** Construct a new instance configured with the given precision context. The
481 * precision context is used when building line segments from vertices and
482 * may be omitted if raw vertices are not used.
483 * @param precision precision context to use when creating line segments
484 * from vertices
485 */
486 private Builder(final Precision.DoubleEquivalence precision) {
487 setPrecision(precision);
488 }
489
490 /** Set the precision context. This context is used only when creating line segments
491 * from appended or prepended vertices. It is not used when adding existing
492 * {@link LineConvexSubset} instances since those contain their own precision contexts.
493 * @param builderPrecision precision context to use when creating line segments
494 * from vertices
495 * @return this instance
496 */
497 public Builder setPrecision(final Precision.DoubleEquivalence builderPrecision) {
498 this.precision = builderPrecision;
499
500 return this;
501 }
502
503 /** Get the line subset at the start of the path or null if it does not exist.
504 * @return the line subset at the start of the path
505 */
506 public LineConvexSubset getStart() {
507 LineConvexSubset start = getLast(prepended);
508 if (start == null) {
509 start = getFirst(appended);
510 }
511 return start;
512 }
513
514 /** Get the line subset at the end of the path or null if it does not exist.
515 * @return the line subset at the end of the path
516 */
517 public LineConvexSubset getEnd() {
518 LineConvexSubset end = getLast(appended);
519 if (end == null) {
520 end = getFirst(prepended);
521 }
522 return end;
523 }
524
525 /** Append a line subset to the end of the path.
526 * @param subset line subset to append to the path
527 * @return the current builder instance
528 * @throws IllegalStateException if the path contains a previous element
529 * and the end vertex of the previous element is not equivalent to the
530 * start vertex of the argument
531 */
532 public Builder append(final LineConvexSubset subset) {
533 validateConnected(getEnd(), subset);
534 appendInternal(subset);
535
536 return this;
537 }
538
539 /** Add a vertex to the end of this path. If the path already has an end vertex,
540 * then a line segment is added between the previous end vertex and this vertex,
541 * using the configured precision context.
542 * @param vertex the vertex to add
543 * @return this instance
544 * @see #setPrecision(Precision.DoubleEquivalence)
545 */
546 public Builder append(final Vector2D vertex) {
547 final Precision.DoubleEquivalence vertexPrecision = getAddVertexPrecision();
548
549 if (endVertex == null) {
550 // make sure that we're not adding to an infinite element
551 final LineConvexSubset end = getEnd();
552 if (end != null) {
553 throw new IllegalStateException(
554 MessageFormat.format("Cannot add vertex {0} after infinite line subset: {1}",
555 vertex, end));
556 }
557
558 // this is the first vertex added
559 startVertex = vertex;
560 endVertex = vertex;
561 endVertexPrecision = vertexPrecision;
562 } else if (!endVertex.eq(vertex, endVertexPrecision)) {
563 // only add the vertex if its not equal to the end point
564 // of the last element
565 appendInternal(Lines.segmentFromPoints(endVertex, vertex, endVertexPrecision));
566 }
567
568 return this;
569 }
570
571 /** Convenience method for appending a collection of vertices to the path in a single method call.
572 * @param vertices the vertices to append
573 * @return this instance
574 * @see #append(Vector2D)
575 */
576 public Builder appendVertices(final Collection<? extends Vector2D> vertices) {
577 for (final Vector2D vertex : vertices) {
578 append(vertex);
579 }
580
581 return this;
582 }
583
584 /** Convenience method for appending multiple vertices to the path at once.
585 * @param vertices the vertices to append
586 * @return this instance
587 * @see #append(Vector2D)
588 */
589 public Builder appendVertices(final Vector2D... vertices) {
590 return appendVertices(Arrays.asList(vertices));
591 }
592
593 /** Prepend a line subset to the beginning of the path.
594 * @param subset line subset to prepend to the path
595 * @return the current builder instance
596 * @throws IllegalStateException if the path contains a start element
597 * and the end vertex of the argument is not equivalent to the
598 * start vertex of the start element.
599 */
600 public Builder prepend(final LineConvexSubset subset) {
601 validateConnected(subset, getStart());
602 prependInternal(subset);
603
604 return this;
605 }
606
607 /** Add a vertex to the front of this path. If the path already has a start vertex,
608 * then a line segment is added between this vertex and the previous start vertex,
609 * using the configured precision context.
610 * @param vertex the vertex to add
611 * @return this instance
612 * @see #setPrecision(Precision.DoubleEquivalence)
613 */
614 public Builder prepend(final Vector2D vertex) {
615 final Precision.DoubleEquivalence vertexPrecision = getAddVertexPrecision();
616
617 if (startVertex == null) {
618 // make sure that we're not adding to an infinite element
619 final LineConvexSubset start = getStart();
620 if (start != null) {
621 throw new IllegalStateException(
622 MessageFormat.format("Cannot add vertex {0} before infinite line subset: {1}",
623 vertex, start));
624 }
625
626 // this is the first vertex added
627 startVertex = vertex;
628 endVertex = vertex;
629 endVertexPrecision = vertexPrecision;
630 } else if (!vertex.eq(startVertex, vertexPrecision)) {
631 // only add if the vertex is not equal to the start
632 // point of the first element
633 prependInternal(Lines.segmentFromPoints(vertex, startVertex, vertexPrecision));
634 }
635
636 return this;
637 }
638
639 /** Convenience method for prepending a collection of vertices to the path in a single method call.
640 * The vertices are logically prepended as a single group, meaning that the first vertex
641 * in the given collection appears as the first vertex in the path after this method call.
642 * Internally, this means that the vertices are actually passed to the {@link #prepend(Vector2D)}
643 * method in reverse order.
644 * @param vertices the vertices to prepend
645 * @return this instance
646 * @see #prepend(Vector2D)
647 */
648 public Builder prependVertices(final Collection<Vector2D> vertices) {
649 return prependVertices(vertices.toArray(new Vector2D[0]));
650 }
651
652 /** Convenience method for prepending multiple vertices to the path in a single method call.
653 * The vertices are logically prepended as a single group, meaning that the first vertex
654 * in the given collection appears as the first vertex in the path after this method call.
655 * Internally, this means that the vertices are actually passed to the {@link #prepend(Vector2D)}
656 * method in reverse order.
657 * @param vertices the vertices to prepend
658 * @return this instance
659 * @see #prepend(Vector2D)
660 */
661 public Builder prependVertices(final Vector2D... vertices) {
662 for (int i = vertices.length - 1; i >= 0; --i) {
663 prepend(vertices[i]);
664 }
665
666 return this;
667 }
668
669 /** Close the current path and build a new {@link LinePath} instance. This method is equivalent
670 * to {@code builder.build(true)}.
671 * @return new closed path instance
672 * @throws IllegalStateException if the builder was given only a single unique vertex
673 */
674 public LinePath close() {
675 return build(true);
676 }
677
678 /** Build a {@link LinePath} instance from the configured path. This method is equivalent
679 * to {@code builder.build(false)}.
680 * @return new path instance
681 * @throws IllegalStateException if the builder was given only a single unique vertex
682 */
683 public LinePath build() {
684 return build(false);
685 }
686
687 /** Build a {@link LinePath} instance from the configured path.
688 * @param close if true, the path will be closed by adding an end point equivalent to the
689 * start point
690 * @return new path instance
691 * @throws IllegalStateException if the builder was given only a single unique vertex
692 */
693 public LinePath build(final boolean close) {
694 if (close) {
695 closePath();
696 }
697
698 // combine all of the line subsets
699 List<LineConvexSubset> result = null;
700
701 if (prepended != null) {
702 result = prepended;
703 Collections.reverse(result);
704 }
705
706 if (appended != null) {
707 if (result == null) {
708 result = appended;
709 } else {
710 result.addAll(appended);
711 }
712 }
713
714 if (result == null) {
715 result = Collections.emptyList();
716 }
717
718 if (result.isEmpty() && startVertex != null) {
719 throw new IllegalStateException(
720 MessageFormat.format("Unable to create line path; only a single unique vertex provided: {0} ",
721 startVertex));
722 }
723
724 // clear internal state
725 appended = null;
726 prepended = null;
727
728 // build the final path instance, using the shared empty instance if
729 // no line subsets are present
730
731 return result.isEmpty() ? empty() : new LinePath(result);
732 }
733
734 /** Close the path by adding an end point equivalent to the path start point.
735 * @throws IllegalStateException if the path cannot be closed
736 */
737 private void closePath() {
738 final LineConvexSubset end = getEnd();
739
740 if (end != null) {
741 if (startVertex != null && endVertex != null) {
742 if (!endVertex.eq(startVertex, endVertexPrecision)) {
743 appendInternal(Lines.segmentFromPoints(endVertex, startVertex, endVertexPrecision));
744 }
745 } else {
746 throw new IllegalStateException("Unable to close line path: line path is infinite");
747 }
748 }
749 }
750
751 /** Validate that the given line subsets are connected, meaning that the end vertex of {@code previous}
752 * is equivalent to the start vertex of {@code next}. The line subsets are considered valid if either
753 * line subset is null.
754 * @param previous previous line subset
755 * @param next next line subset
756 * @throws IllegalStateException if previous and next are not null and the end vertex of previous
757 * is not equivalent the start vertex of next
758 */
759 private void validateConnected(final LineConvexSubset previous, final LineConvexSubset next) {
760 if (previous != null && next != null) {
761 final Vector2D nextStartVertex = next.getStartPoint();
762 final Vector2D previousEndVertex = previous.getEndPoint();
763 final Precision.DoubleEquivalence previousPrecision = previous.getPrecision();
764
765 if (nextStartVertex == null || previousEndVertex == null ||
766 !(nextStartVertex.eq(previousEndVertex, previousPrecision))) {
767
768 throw new IllegalStateException(
769 MessageFormat.format("Path line subsets are not connected: previous= {0}, next= {1}",
770 previous, next));
771 }
772 }
773 }
774
775 /** Get the precision context used when adding raw vertices to the path. An exception is thrown
776 * if no precision has been specified.
777 * @return the precision context used when creating working with raw vertices
778 * @throws IllegalStateException if no precision context is configured
779 */
780 private Precision.DoubleEquivalence getAddVertexPrecision() {
781 if (precision == null) {
782 throw new IllegalStateException("Unable to create line segment: no vertex precision specified");
783 }
784
785 return precision;
786 }
787
788 /** Append the given, validated line subsets to the path.
789 * @param subset validated line subset to append
790 */
791 private void appendInternal(final LineConvexSubset subset) {
792 if (appended == null) {
793 appended = new ArrayList<>();
794 }
795
796 if (appended.isEmpty() &&
797 (prepended == null || prepended.isEmpty())) {
798 startVertex = subset.getStartPoint();
799 }
800
801 endVertex = subset.getEndPoint();
802 endVertexPrecision = subset.getPrecision();
803
804 appended.add(subset);
805 }
806
807 /** Prepend the given, validated line subset to the path.
808 * @param subset validated line subset to prepend
809 */
810 private void prependInternal(final LineConvexSubset subset) {
811 if (prepended == null) {
812 prepended = new ArrayList<>();
813 }
814
815 startVertex = subset.getStartPoint();
816
817 if (prepended.isEmpty() &&
818 (appended == null || appended.isEmpty())) {
819 endVertex = subset.getEndPoint();
820 endVertexPrecision = subset.getPrecision();
821 }
822
823 prepended.add(subset);
824 }
825
826 /** Get the first element in the list or null if the list is null
827 * or empty.
828 * @param list the list to return the first item from
829 * @return the first item from the given list or null if it does not exist
830 */
831 private LineConvexSubset getFirst(final List<? extends LineConvexSubset> list) {
832 if (list != null && !list.isEmpty()) {
833 return list.get(0);
834 }
835 return null;
836 }
837
838 /** Get the last element in the list or null if the list is null
839 * or empty.
840 * @param list the list to return the last item from
841 * @return the last item from the given list or null if it does not exist
842 */
843 private LineConvexSubset getLast(final List<? extends LineConvexSubset> list) {
844 if (list != null && !list.isEmpty()) {
845 return list.get(list.size() - 1);
846 }
847 return null;
848 }
849 }
850
851 /** Internal class returned when a line path is simplified to remove unnecessary line subset divisions.
852 * The {@link #simplify()} method on this class simply returns the same instance.
853 */
854 private static final class SimplifiedLinePath extends LinePath {
855 /** Create a new instance containing the given line subsets. No validation is
856 * performed on the inputs. Caller must ensure that the given line subsets represent
857 * a valid, simplified path.
858 * @param elements line subsets comprising the path
859 */
860 private SimplifiedLinePath(final List<LineConvexSubset> elements) {
861 super(elements);
862 }
863
864 /** {@inheritDoc} */
865 @Override
866 public SimplifiedLinePath simplify() {
867 // already simplified
868 return this;
869 }
870 }
871 }