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.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 }