View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   */
    17  package org.apache.commons.geometry.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.core.precision.DoublePrecisionContext;
    31  import org.apache.commons.geometry.euclidean.twod.BoundarySource2D;
    32  import org.apache.commons.geometry.euclidean.twod.Line;
    33  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
    34  import org.apache.commons.geometry.euclidean.twod.Lines;
    35  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    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<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, DoublePrecisionContext)
    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, DoublePrecisionContext)
    397      */
    398     public static LinePath fromVertexLoop(final Collection<Vector2D> vertices,
    399             final DoublePrecisionContext 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, DoublePrecisionContext)
    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, DoublePrecisionContext)
    414      */
    415     public static LinePath fromVertices(final Collection<Vector2D> vertices,
    416             final DoublePrecisionContext 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 DoublePrecisionContext 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 DoublePrecisionContext 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 = null;
    462
    463         /** Line subsets prepended to the path. */
    464         private List<LineConvexSubset> prepended = null;
    465
    466         /** Precision context used when creating line segments directly from vertices. */
    467         private DoublePrecisionContext 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 DoublePrecisionContext 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 DoublePrecisionContext 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 DoublePrecisionContext 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(DoublePrecisionContext)
    545          */
    546         public Builder append(final Vector2D vertex) {
    547             final DoublePrecisionContext 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<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(DoublePrecisionContext)
    613          */
    614         public Builder prepend(final Vector2D vertex) {
    615             final DoublePrecisionContext 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 DoublePrecisionContext 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 DoublePrecisionContext 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<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<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 }