commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/GreatArcPath.java - commons-geometry - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package org.apache.commons.geometry.spherical.twod;

 import java.text.MessageFormat;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Iterator;
 import java.util.List;

 import org.apache.commons.geometry.core.precision.DoublePrecisionContext;

 /** Class representing a connected sequence of {@link GreatArc} instances.
  */
 public final class GreatArcPath implements Iterable<GreatArc> {
     /** Instance containing no arcs. */
     private static final GreatArcPath EMPTY = new GreatArcPath(Collections.emptyList());

     /** Arcs comprising the instance. */
     private final List<GreatArc> arcs;

     /** Simple constructor. No validation is performed on the input arc.
      * @param arcs arcs for the path, in connection order
      */
     private GreatArcPath(final List<GreatArc> arcs) {
         this.arcs = Collections.unmodifiableList(arcs);
     }

     /** Get the arcs in path.
      * @return the arcs in the path
      */
     public List<GreatArc> getArcs() {
         return arcs;
     }

     /** Get the start arc for the path or null if the path is empty.
      * @return the start arc for the path or null if the path is empty
      */
     public GreatArc getStartArc() {
         if (!isEmpty()) {
             return arcs.get(0);
         }
         return null;
     }

     /** Get the end arc for the path or null if the path is empty.
      * @return the end arc for the path or null if the path is empty
      */
     public GreatArc getEndArc() {
         if (!isEmpty()) {
             return arcs.get(arcs.size() - 1);
         }
         return null;
     }

     /** Get the start vertex for the path or null if the path is empty
      * or consists of a single, full arc.
      * @return the start vertex for the path
      */
     public Point2S getStartVertex() {
         final GreatArc arc = getStartArc();
         return (arc != null) ? arc.getStartPoint() : null;
     }

     /** Get the end vertex for the path or null if the path is empty
      * or consists of a single, full arc.
      * @return the end vertex for the path
      */
     public Point2S getEndVertex() {
         final GreatArc arc = getEndArc();
         return (arc != null) ? arc.getEndPoint() : null;
     }

     /** Get the vertices contained in the path in the order they appear.
      * Closed paths contain the start vertex at the beginning of the list
      * as well as the end.
      * @return the vertices contained in the path in order they appear
      */
     public List<Point2S> getVertices() {
         final List<Point2S> vertices = new ArrayList<>();

         Point2S pt;

         // add the start point, if present
         pt = getStartVertex();
         if (pt != null) {
             vertices.add(pt);
         }

         // add end points
         for (GreatArc arc : arcs) {
             pt = arc.getEndPoint();
             if (pt != null) {
                 vertices.add(pt);
             }
         }

         return vertices;
     }

     /** Return true if the path does not contain any arcs.
      * @return true if the path does not contain any arcs
      */
     public boolean isEmpty() {
         return arcs.isEmpty();
     }

     /** Return true if the path is closed, meaning that the end
      * point for the last arc is equal to the start point
      * for the path.
      * @return true if the end point for the last arc is
      *      equal to the start point for the path
      */
     public boolean isClosed() {
         final GreatArc endArc = getEndArc();

         if (endArc != null) {
             final Point2S start = getStartVertex();
             final Point2S end = endArc.getEndPoint();

             return start != null && end != null && start.eq(end, endArc.getPrecision());
         }

         return false;
     }

     /** {@inheritDoc} */
     @Override
     public Iterator<GreatArc> iterator() {
         return arcs.iterator();
     }

     /** Construct a {@link RegionBSPTree2S} from the arcs in this instance.
      * @return a bsp tree constructed from the arcs in this instance
      */
     public RegionBSPTree2S toTree() {
         RegionBSPTree2S tree = RegionBSPTree2S.empty();
         tree.insert(this);

         return tree;
     }

     /** Return a string representation of this arc path instance.
     *
     * <p>In order to keep the string representation short but useful, the exact format of the return
     * value depends on the properties of the path. See below for examples.
     *
     * <ul>
     *      <li>Empty path
     *          <ul>
     *              <li>{@code GreatArcPath[empty= true]}</li>
     *          </ul>
     *      </li>
     *      <li>Single, full arc
     *          <ul>
     *              <li>{@code GreatArcPath[full= true, circle= GreatCircle[pole= (0.0, 0.0, 1.0),
     *              x= (0.0, 1.0, -0.0), y= (-1.0, 0.0, 0.0)]]}</li>
     *          </ul>
     *      </li>
     *      <li>One or more non-full arcs
     *          <ul>
     *              <li>{@code GreatArcPath[vertices= [(0.0, 1.5707963267948966),
     *              (1.5707963267948966, 1.5707963267948966)]]}</li>
     *          </ul>
     *      </li>
     * </ul>
     */
     @Override
     public String toString() {
         final StringBuilder sb = new StringBuilder();
         sb.append(this.getClass().getSimpleName())
             .append('[');

         if (isEmpty()) {
             sb.append("empty= true");
         } else if (arcs.size() == 1 && arcs.get(0).isFull()) {
             sb.append("full= true, circle= ")
                 .append(arcs.get(0).getCircle());
         } else {
             sb.append("vertices= ")
                 .append(getVertices());
         }

         sb.append("]");

         return sb.toString();
     }

     /** Construct a new path from the given arcs.
      * @param arcs arc instance to use to construct the path
      * @return a new instance constructed from the given arc instances
      */
     public static GreatArcPath fromArcs(final GreatArc... arcs) {
         return fromArcs(Arrays.asList(arcs));
     }

     /** Construct a new path from the given arcs.
      * @param arcs arc instance to use to construct the path
      * @return a new instance constructed from the given arc instances
      */
     public static GreatArcPath fromArcs(final Collection<GreatArc> arcs) {
         final Builder builder = builder(null);
         for (GreatArc arc : arcs) {
             builder.append(arc);
         }

         return builder.build();
     }

     /** Return a new path formed by connecting the given vertices. An additional arc is added
      * from the last point to the first point to construct a loop, if the two points are not
      * already considered equal by the given precision context. This method is equivalent
      * to calling {@link #fromVertices(Collection, boolean, DoublePrecisionContext)
      * fromPoints(points, true, precision)}.
      * @param vertices the points to construct the path from
      * @param precision precision precision context used to construct the arc instances for the
      *      path
      * @return a new path formed by connecting the given vertices
      * @see #fromVertices(Collection, boolean, DoublePrecisionContext)
      */
     public static GreatArcPath fromVertexLoop(final Collection<Point2S> vertices,
             final DoublePrecisionContext precision) {
         return fromVertices(vertices, true, precision);
     }

     /** Return a new path formed by connecting the given vertices. No additional arc
      * is inserted to connect the last point to the first. This method is equivalent
      * to calling {@link #fromVertices(Collection, boolean, DoublePrecisionContext)
      * fromPoint(points, false, precision)}.
      * @param vertices the points to construct the path from
      * @param precision precision context used to construct the arc instances for the
      *      path
      * @return a new path formed by connecting the given vertices
      * @see #fromVertices(Collection, boolean, DoublePrecisionContext)
      */
     public static GreatArcPath fromVertices(final Collection<Point2S> vertices,
             final DoublePrecisionContext precision) {
         return fromVertices(vertices, false, precision);
     }

     /** Return a new path formed by connecting the given vertices.
      * @param vertices the points to construct the path from
      * @param close if true, then an additional arc will be added from the last point
      *      to the first, if the points are not already considered equal by the given
      *      precision context
      * @param precision precision context used to construct the arc instances for the
      *      path
      * @return a new path formed by connecting the given points
      */
     public static GreatArcPath fromVertices(final Collection<Point2S> vertices, final boolean close,
             final DoublePrecisionContext precision) {

         return builder(precision)
                 .appendVertices(vertices)
                 .build(close);
     }

     /** Return a {@link Builder} instance configured with the given precision
      * context. The precision context is used when building arcs from points
      * and may be omitted if raw points are not used.
      * @param precision precision context to use when building arcs from
      *      raw points; may be null if raw points are not used.
      * @return a new {@link Builder} instance
      */
     public static Builder builder(final DoublePrecisionContext precision) {
         return new Builder(precision);
     }

     /** Get an instance containing no arcs.
      * @return an instance containing no arcs
      */
     public static GreatArcPath empty() {
         return EMPTY;
     }

     /** Class used to build arc paths.
      */
     public static final class Builder {
         /** Arcs appended to the path. */
         private List<GreatArc> appendedArcs = null;

         /** Arcs prepended to the path. */
         private List<GreatArc> prependedArcs = null;

         /** Precision context used when creating arcs directly from points. */
         private DoublePrecisionContext precision;

         /** The current point at the start of the path. */
         private Point2S startVertex;

         /** The current point at the end of the path. */
         private Point2S endVertex;

         /** The precision context used when performing comparisons involving the current
          * end point.
          */
         private DoublePrecisionContext endVertexPrecision;

         /** Construct a new instance configured with the given precision context. The
          * precision context is used when building arcs from points and
          * may be omitted if raw points are not used.
          * @param precision precision context to use when creating arcs
          *      from points
          */
         private Builder(final DoublePrecisionContext precision) {
             setPrecision(precision);
         }

         /** Set the precision context. This context is used only when creating arcs
          * from appended or prepended points. It is not used when adding existing
          * {@link GreatArc} instances since those contain their own precision contexts.
          * @param builderPrecision precision context to use when creating arcs from points
          * @return this instance
          */
         public Builder setPrecision(final DoublePrecisionContext builderPrecision) {
             this.precision = builderPrecision;

             return this;
         }

         /** Get the arc at the start of the path or null if it does not exist.
          * @return the arc at the start of the path
          */
         public GreatArc getStartArc() {
             GreatArc start = getLast(prependedArcs);
             if (start == null) {
                 start = getFirst(appendedArcs);
             }
             return start;
         }

         /** Get the arc at the end of the path or null if it does not exist.
          * @return the arc at the end of the path
          */
         public GreatArc getEndArc() {
             GreatArc end = getLast(appendedArcs);
             if (end == null) {
                 end = getFirst(prependedArcs);
             }
             return end;
         }

         /** Append an arc to the end of the path.
          * @param arc arc to append to the path
          * @return the current builder instance
          * @throws IllegalStateException if the path contains a previous arc
          *      and the end point of the previous arc is not equivalent to the
          *      start point of the given arc
          */
         public Builder append(final GreatArc arc) {
             validateArcsConnected(getEndArc(), arc);
             appendInternal(arc);

             return this;
         }

         /** Add a vertex to the end of this path. If the path already has an end vertex,
          * then an arc is added between the previous end vertex and this vertex,
          * using the configured precision context.
          * @param vertex the vertex to add
          * @return this instance
          * @see #setPrecision(DoublePrecisionContext)
          */
         public Builder append(final Point2S vertex) {
             final DoublePrecisionContext vertexPrecision = getAddPointPrecision();

             if (endVertex == null) {
                 // make sure that we're not adding to a full arc
                 final GreatArc end = getEndArc();
                 if (end != null) {
                     throw new IllegalStateException(
                             MessageFormat.format("Cannot add point {0} after full arc: {1}", vertex, end));
                 }

                 // this is the first vertex added
                 startVertex = vertex;
                 endVertex = vertex;
                 endVertexPrecision = vertexPrecision;
             } else if (!endVertex.eq(vertex, vertexPrecision)) {
                 // only add the vertex if its not equal to the end point
                 // of the last arc
                 appendInternal(GreatArc.fromPoints(endVertex, vertex, endVertexPrecision));
             }

             return this;
         }

         /** Convenience method for appending a collection of vertices to the path in a single
          * method call.
          * @param vertices the vertices to append
          * @return this instance
          * @see #append(Point2S)
          */
         public Builder appendVertices(final Collection<Point2S> vertices) {
             for (Point2S vertex : vertices) {
                 append(vertex);
             }

             return this;
         }

         /** Convenience method for appending multiple vertices to the path at once.
          * @param vertices the points to append
          * @return this instance
          * @see #append(Point2S)
          */
         public Builder appendVertices(final Point2S... vertices) {
             return appendVertices(Arrays.asList(vertices));
         }

         /** Prepend an arc to the beginning of the path.
          * @param arc arc to prepend to the path
          * @return the current builder instance
          * @throws IllegalStateException if the path contains a start arc
          *      and the end point of the given arc is not equivalent to the
          *      start point of the start arc
          */
         public Builder prepend(final GreatArc arc) {
             validateArcsConnected(arc, getStartArc());
             prependInternal(arc);

             return this;
         }

         /** Add a vertex to the front of this path. If the path already has a start vertex,
          * then an arc is added between this vertex and the previous start vertex,
          * using the configured precision context.
          * @param vertex the vertex to add
          * @return this instance
          * @see #setPrecision(DoublePrecisionContext)
          */
         public Builder prepend(final Point2S vertex) {
             final DoublePrecisionContext vertexPrecision = getAddPointPrecision();

             if (startVertex == null) {
                 // make sure that we're not adding to a full arc
                 final GreatArc start = getStartArc();
                 if (start != null) {
                     throw new IllegalStateException(
                             MessageFormat.format("Cannot add point {0} before full arc: {1}", vertex, start));
                 }

                 // this is the first vertex added
                 startVertex = vertex;
                 endVertex = vertex;
                 endVertexPrecision = vertexPrecision;
             } else if (!vertex.eq(startVertex, vertexPrecision)) {
                 // only add if the vertex is not equal to the start
                 // point of the first arc
                 prependInternal(GreatArc.fromPoints(vertex, startVertex, vertexPrecision));
             }

             return this;
         }

         /** Convenience method for prepending a collection of vertices to the path in a single method call.
          * The vertices are logically prepended as a single group, meaning that the first vertex
          * in the given collection appears as the first vertex in the path after this method call.
          * Internally, this means that the vertices are actually passed to the {@link #prepend(Point2S)}
          * method in reverse order.
          * @param vertices the points to prepend
          * @return this instance
          * @see #prepend(Point2S)
          */
         public Builder prependPoints(final Collection<Point2S> vertices) {
             return prependPoints(vertices.toArray(new Point2S[0]));
         }

         /** Convenience method for prepending multiple vertices to the path in a single method call.
          * The vertices are logically prepended as a single group, meaning that the first vertex
          * in the given collection appears as the first vertex in the path after this method call.
          * Internally, this means that the vertices are actually passed to the {@link #prepend(Point2S)}
          * method in reverse order.
          * @param vertices the vertices to prepend
          * @return this instance
          * @see #prepend(Point2S)
          */
         public Builder prependPoints(final Point2S... vertices) {
             for (int i = vertices.length - 1; i >= 0; --i) {
                 prepend(vertices[i]);
             }

             return this;
         }

         /** Close the current path and build a new {@link GreatArcPath} instance. This method is equivalent
          * to {@code builder.build(true)}.
          * @return new closed path instance
          */
         public GreatArcPath close() {
             return build(true);
         }

         /** Build a {@link GreatArcPath} instance from the configured path. This method is equivalent
          * to {@code builder.build(false)}.
          * @return new path instance
          */
         public GreatArcPath build() {
             return build(false);
         }

         /** Build a {@link GreatArcPath} instance from the configured path.
          * @param close if true, the path will be closed by adding an end point equivalent to the
          *      start point
          * @return new path instance
          */
         public GreatArcPath build(final boolean close) {
             if (close) {
                 closePath();
             }

             // combine all of the arcs
             List<GreatArc> result = null;

             if (prependedArcs != null) {
                 result = prependedArcs;
                 Collections.reverse(result);
             }

             if (appendedArcs != null) {
                 if (result == null) {
                     result = appendedArcs;
                 } else {
                     result.addAll(appendedArcs);
                 }
             }

             if (result == null) {
                 result = Collections.emptyList();
             }

             if (result.isEmpty() && startVertex != null) {
                 throw new IllegalStateException(
                         MessageFormat.format("Unable to create path; only a single point provided: {0}",
                                 startVertex));
             }

             // clear internal state
             appendedArcs = null;
             prependedArcs = null;

             // build the final path instance, using the shared empty instance if
             // no arcs are present
             return result.isEmpty() ? empty() : new GreatArcPath(result);
         }

         /** Close the path by adding an end point equivalent to the path start point.
          * @throws IllegalStateException if the path cannot be closed
          */
         private void closePath() {
             final GreatArc end = getEndArc();

             if (end != null) {
                 if (startVertex != null && endVertex != null) {
                     if (!endVertex.eq(startVertex, endVertexPrecision)) {
                         appendInternal(GreatArc.fromPoints(endVertex, startVertex, endVertexPrecision));
                     }
                 } else {
                     throw new IllegalStateException("Unable to close path: path is full");
                 }
             }
         }

         /** Validate that the given arcs are connected, meaning that the end point of {@code previous}
          * is equivalent to the start point of {@code next}. The arcs are considered valid if either
          * arc is null.
          * @param previous previous arc
          * @param next next arc
          * @throws IllegalStateException if previous and next are not null and the end point of previous
          *      is not equivalent the start point of next
          */
         private void validateArcsConnected(final GreatArc previous, final GreatArc next) {
             if (previous != null && next != null) {
                 final Point2S nextStartVertex = next.getStartPoint();
                 final Point2S previousEndVertex = previous.getEndPoint();
                 final DoublePrecisionContext previousPrecision = previous.getPrecision();

                 if (nextStartVertex == null || previousEndVertex == null ||
                         !(nextStartVertex.eq(previousEndVertex, previousPrecision))) {

                     throw new IllegalStateException(
                             MessageFormat.format("Path arcs are not connected: previous= {0}, next= {1}",
                                     previous, next));
                 }
             }
         }

         /** Get the precision context used when adding raw points to the path. An exception is thrown
          * if no precision has been specified.
          * @return the precision context used when working with raw points
          * @throws IllegalStateException if no precision context is configured
          */
         private DoublePrecisionContext getAddPointPrecision() {
             if (precision == null) {
                 throw new IllegalStateException("Unable to create arc: no point precision specified");
             }

             return precision;
         }

         /** Append the given, validated arc to the path.
          * @param arc validated arc to append
          */
         private void appendInternal(final GreatArc arc) {
             if (appendedArcs == null) {
                 appendedArcs = new ArrayList<>();
             }

             if (appendedArcs.isEmpty() &&
                     (prependedArcs == null || prependedArcs.isEmpty())) {
                 startVertex = arc.getStartPoint();
             }

             endVertex = arc.getEndPoint();
             endVertexPrecision = arc.getPrecision();

             appendedArcs.add(arc);
         }

         /** Prepend the given, validated arc to the path.
          * @param arc validated arc to prepend
          */
         private void prependInternal(final GreatArc arc) {
             if (prependedArcs == null) {
                 prependedArcs = new ArrayList<>();
             }

             startVertex = arc.getStartPoint();

             if (prependedArcs.isEmpty() &&
                     (appendedArcs == null || appendedArcs.isEmpty())) {
                 endVertex = arc.getEndPoint();
                 endVertexPrecision = arc.getPrecision();
             }

             prependedArcs.add(arc);
         }

         /** Get the first element in the list or null if the list is null
          * or empty.
          * @param list the list to return the first item from
          * @return the first item from the given list or null if it does not exist
          */
         private GreatArc getFirst(final List<GreatArc> list) {
             if (list != null && !list.isEmpty()) {
                 return list.get(0);
             }
             return null;
         }

         /** Get the last element in the list or null if the list is null
          * or empty.
          * @param list the list to return the last item from
          * @return the last item from the given list or null if it does not exist
          */
         private GreatArc getLast(final List<GreatArc> list) {
             if (list != null && !list.isEmpty()) {
                 return list.get(list.size() - 1);
             }
             return null;
         }
     }
 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one or more
	* contributor license agreements. See the NOTICE file distributed with
	* this work for additional information regarding copyright ownership.
	* The ASF licenses this file to You under the Apache License, Version 2.0
	* (the "License"); you may not use this file except in compliance with
	* the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package org.apache.commons.geometry.spherical.twod;

	import java.text.MessageFormat;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.Iterator;
	import java.util.List;

	import org.apache.commons.geometry.core.precision.DoublePrecisionContext;

	/** Class representing a connected sequence of {@link GreatArc} instances.
	*/
	public final class GreatArcPath implements Iterable<GreatArc> {
	/** Instance containing no arcs. */
	private static final GreatArcPath EMPTY = new GreatArcPath(Collections.emptyList());

	/** Arcs comprising the instance. */
	private final List<GreatArc> arcs;

	/** Simple constructor. No validation is performed on the input arc.
	* @param arcs arcs for the path, in connection order
	*/
	private GreatArcPath(final List<GreatArc> arcs) {
	this.arcs = Collections.unmodifiableList(arcs);
	}

	/** Get the arcs in path.
	* @return the arcs in the path
	*/
	public List<GreatArc> getArcs() {
	return arcs;
	}

	/** Get the start arc for the path or null if the path is empty.
	* @return the start arc for the path or null if the path is empty
	*/
	public GreatArc getStartArc() {
	if (!isEmpty()) {
	return arcs.get(0);
	}
	return null;
	}

	/** Get the end arc for the path or null if the path is empty.
	* @return the end arc for the path or null if the path is empty
	*/
	public GreatArc getEndArc() {
	if (!isEmpty()) {
	return arcs.get(arcs.size() - 1);
	}
	return null;
	}

	/** Get the start vertex for the path or null if the path is empty
	* or consists of a single, full arc.
	* @return the start vertex for the path
	*/
	public Point2S getStartVertex() {
	final GreatArc arc = getStartArc();
	return (arc != null) ? arc.getStartPoint() : null;
	}

	/** Get the end vertex for the path or null if the path is empty
	* or consists of a single, full arc.
	* @return the end vertex for the path
	*/
	public Point2S getEndVertex() {
	final GreatArc arc = getEndArc();
	return (arc != null) ? arc.getEndPoint() : null;
	}

	/** Get the vertices contained in the path in the order they appear.
	* Closed paths contain the start vertex at the beginning of the list
	* as well as the end.
	* @return the vertices contained in the path in order they appear
	*/
	public List<Point2S> getVertices() {
	final List<Point2S> vertices = new ArrayList<>();

	Point2S pt;

	// add the start point, if present
	pt = getStartVertex();
	if (pt != null) {
	vertices.add(pt);
	}

	// add end points
	for (GreatArc arc : arcs) {
	pt = arc.getEndPoint();
	if (pt != null) {
	vertices.add(pt);
	}
	}

	return vertices;
	}

	/** Return true if the path does not contain any arcs.
	* @return true if the path does not contain any arcs
	*/
	public boolean isEmpty() {
	return arcs.isEmpty();
	}

	/** Return true if the path is closed, meaning that the end
	* point for the last arc is equal to the start point
	* for the path.
	* @return true if the end point for the last arc is
	* equal to the start point for the path
	*/
	public boolean isClosed() {
	final GreatArc endArc = getEndArc();

	if (endArc != null) {
	final Point2S start = getStartVertex();
	final Point2S end = endArc.getEndPoint();

	return start != null && end != null && start.eq(end, endArc.getPrecision());
	}

	return false;
	}

	/** {@inheritDoc} */
	@Override
	public Iterator<GreatArc> iterator() {
	return arcs.iterator();
	}

	/** Construct a {@link RegionBSPTree2S} from the arcs in this instance.
	* @return a bsp tree constructed from the arcs in this instance
	*/
	public RegionBSPTree2S toTree() {
	RegionBSPTree2S tree = RegionBSPTree2S.empty();
	tree.insert(this);

	return tree;
	}

	/** Return a string representation of this arc path instance.
	*
	* <p>In order to keep the string representation short but useful, the exact format of the return
	* value depends on the properties of the path. See below for examples.
	*
	* <ul>
	* <li>Empty path
	* <ul>
	* <li>{@code GreatArcPath[empty= true]}</li>
	* </ul>
	* </li>
	* <li>Single, full arc
	* <ul>
	* <li>{@code GreatArcPath[full= true, circle= GreatCircle[pole= (0.0, 0.0, 1.0),
	* x= (0.0, 1.0, -0.0), y= (-1.0, 0.0, 0.0)]]}</li>
	* </ul>
	* </li>
	* <li>One or more non-full arcs
	* <ul>
	* <li>{@code GreatArcPath[vertices= [(0.0, 1.5707963267948966),
	* (1.5707963267948966, 1.5707963267948966)]]}</li>
	* </ul>
	* </li>
	* </ul>
	*/
	@Override
	public String toString() {
	final StringBuilder sb = new StringBuilder();
	sb.append(this.getClass().getSimpleName())
	.append('[');

	if (isEmpty()) {
	sb.append("empty= true");
	} else if (arcs.size() == 1 && arcs.get(0).isFull()) {
	sb.append("full= true, circle= ")
	.append(arcs.get(0).getCircle());
	} else {
	sb.append("vertices= ")
	.append(getVertices());
	}

	sb.append("]");

	return sb.toString();
	}

	/** Construct a new path from the given arcs.
	* @param arcs arc instance to use to construct the path
	* @return a new instance constructed from the given arc instances
	*/
	public static GreatArcPath fromArcs(final GreatArc... arcs) {
	return fromArcs(Arrays.asList(arcs));
	}

	/** Construct a new path from the given arcs.
	* @param arcs arc instance to use to construct the path
	* @return a new instance constructed from the given arc instances
	*/
	public static GreatArcPath fromArcs(final Collection<GreatArc> arcs) {
	final Builder builder = builder(null);
	for (GreatArc arc : arcs) {
	builder.append(arc);
	}

	return builder.build();
	}

	/** Return a new path formed by connecting the given vertices. An additional arc is added
	* from the last point to the first point to construct a loop, if the two points are not
	* already considered equal by the given precision context. This method is equivalent
	* to calling {@link #fromVertices(Collection, boolean, DoublePrecisionContext)
	* fromPoints(points, true, precision)}.
	* @param vertices the points to construct the path from
	* @param precision precision precision context used to construct the arc instances for the
	* path
	* @return a new path formed by connecting the given vertices
	* @see #fromVertices(Collection, boolean, DoublePrecisionContext)
	*/
	public static GreatArcPath fromVertexLoop(final Collection<Point2S> vertices,
	final DoublePrecisionContext precision) {
	return fromVertices(vertices, true, precision);
	}

	/** Return a new path formed by connecting the given vertices. No additional arc
	* is inserted to connect the last point to the first. This method is equivalent
	* to calling {@link #fromVertices(Collection, boolean, DoublePrecisionContext)
	* fromPoint(points, false, precision)}.
	* @param vertices the points to construct the path from
	* @param precision precision context used to construct the arc instances for the
	* path
	* @return a new path formed by connecting the given vertices
	* @see #fromVertices(Collection, boolean, DoublePrecisionContext)
	*/
	public static GreatArcPath fromVertices(final Collection<Point2S> vertices,
	final DoublePrecisionContext precision) {
	return fromVertices(vertices, false, precision);
	}

	/** Return a new path formed by connecting the given vertices.
	* @param vertices the points to construct the path from
	* @param close if true, then an additional arc will be added from the last point
	* to the first, if the points are not already considered equal by the given
	* precision context
	* @param precision precision context used to construct the arc instances for the
	* path
	* @return a new path formed by connecting the given points
	*/
	public static GreatArcPath fromVertices(final Collection<Point2S> vertices, final boolean close,
	final DoublePrecisionContext precision) {

	return builder(precision)
	.appendVertices(vertices)
	.build(close);
	}

	/** Return a {@link Builder} instance configured with the given precision
	* context. The precision context is used when building arcs from points
	* and may be omitted if raw points are not used.
	* @param precision precision context to use when building arcs from
	* raw points; may be null if raw points are not used.
	* @return a new {@link Builder} instance
	*/
	public static Builder builder(final DoublePrecisionContext precision) {
	return new Builder(precision);
	}

	/** Get an instance containing no arcs.
	* @return an instance containing no arcs
	*/
	public static GreatArcPath empty() {
	return EMPTY;
	}

	/** Class used to build arc paths.
	*/
	public static final class Builder {
	/** Arcs appended to the path. */
	private List<GreatArc> appendedArcs = null;

	/** Arcs prepended to the path. */
	private List<GreatArc> prependedArcs = null;

	/** Precision context used when creating arcs directly from points. */
	private DoublePrecisionContext precision;

	/** The current point at the start of the path. */
	private Point2S startVertex;

	/** The current point at the end of the path. */
	private Point2S endVertex;

	/** The precision context used when performing comparisons involving the current
	* end point.
	*/
	private DoublePrecisionContext endVertexPrecision;

	/** Construct a new instance configured with the given precision context. The
	* precision context is used when building arcs from points and
	* may be omitted if raw points are not used.
	* @param precision precision context to use when creating arcs
	* from points
	*/
	private Builder(final DoublePrecisionContext precision) {
	setPrecision(precision);
	}

	/** Set the precision context. This context is used only when creating arcs
	* from appended or prepended points. It is not used when adding existing
	* {@link GreatArc} instances since those contain their own precision contexts.
	* @param builderPrecision precision context to use when creating arcs from points
	* @return this instance
	*/
	public Builder setPrecision(final DoublePrecisionContext builderPrecision) {
	this.precision = builderPrecision;

	return this;
	}

	/** Get the arc at the start of the path or null if it does not exist.
	* @return the arc at the start of the path
	*/
	public GreatArc getStartArc() {
	GreatArc start = getLast(prependedArcs);
	if (start == null) {
	start = getFirst(appendedArcs);
	}
	return start;
	}

	/** Get the arc at the end of the path or null if it does not exist.
	* @return the arc at the end of the path
	*/
	public GreatArc getEndArc() {
	GreatArc end = getLast(appendedArcs);
	if (end == null) {
	end = getFirst(prependedArcs);
	}
	return end;
	}

	/** Append an arc to the end of the path.
	* @param arc arc to append to the path
	* @return the current builder instance
	* @throws IllegalStateException if the path contains a previous arc
	* and the end point of the previous arc is not equivalent to the
	* start point of the given arc
	*/
	public Builder append(final GreatArc arc) {
	validateArcsConnected(getEndArc(), arc);
	appendInternal(arc);

	return this;
	}

	/** Add a vertex to the end of this path. If the path already has an end vertex,
	* then an arc is added between the previous end vertex and this vertex,
	* using the configured precision context.
	* @param vertex the vertex to add
	* @return this instance
	* @see #setPrecision(DoublePrecisionContext)
	*/
	public Builder append(final Point2S vertex) {
	final DoublePrecisionContext vertexPrecision = getAddPointPrecision();

	if (endVertex == null) {
	// make sure that we're not adding to a full arc
	final GreatArc end = getEndArc();
	if (end != null) {
	throw new IllegalStateException(
	MessageFormat.format("Cannot add point {0} after full arc: {1}", vertex, end));
	}

	// this is the first vertex added
	startVertex = vertex;
	endVertex = vertex;
	endVertexPrecision = vertexPrecision;
	} else if (!endVertex.eq(vertex, vertexPrecision)) {
	// only add the vertex if its not equal to the end point
	// of the last arc
	appendInternal(GreatArc.fromPoints(endVertex, vertex, endVertexPrecision));
	}

	return this;
	}

	/** Convenience method for appending a collection of vertices to the path in a single
	* method call.
	* @param vertices the vertices to append
	* @return this instance
	* @see #append(Point2S)
	*/
	public Builder appendVertices(final Collection<Point2S> vertices) {
	for (Point2S vertex : vertices) {
	append(vertex);
	}

	return this;
	}

	/** Convenience method for appending multiple vertices to the path at once.
	* @param vertices the points to append
	* @return this instance
	* @see #append(Point2S)
	*/
	public Builder appendVertices(final Point2S... vertices) {
	return appendVertices(Arrays.asList(vertices));
	}

	/** Prepend an arc to the beginning of the path.
	* @param arc arc to prepend to the path
	* @return the current builder instance
	* @throws IllegalStateException if the path contains a start arc
	* and the end point of the given arc is not equivalent to the
	* start point of the start arc
	*/
	public Builder prepend(final GreatArc arc) {
	validateArcsConnected(arc, getStartArc());
	prependInternal(arc);

	return this;
	}

	/** Add a vertex to the front of this path. If the path already has a start vertex,
	* then an arc is added between this vertex and the previous start vertex,
	* using the configured precision context.
	* @param vertex the vertex to add
	* @return this instance
	* @see #setPrecision(DoublePrecisionContext)
	*/
	public Builder prepend(final Point2S vertex) {
	final DoublePrecisionContext vertexPrecision = getAddPointPrecision();

	if (startVertex == null) {
	// make sure that we're not adding to a full arc
	final GreatArc start = getStartArc();
	if (start != null) {
	throw new IllegalStateException(
	MessageFormat.format("Cannot add point {0} before full arc: {1}", vertex, start));
	}

	// this is the first vertex added
	startVertex = vertex;
	endVertex = vertex;
	endVertexPrecision = vertexPrecision;
	} else if (!vertex.eq(startVertex, vertexPrecision)) {
	// only add if the vertex is not equal to the start
	// point of the first arc
	prependInternal(GreatArc.fromPoints(vertex, startVertex, vertexPrecision));
	}

	return this;
	}

	/** Convenience method for prepending a collection of vertices to the path in a single method call.
	* The vertices are logically prepended as a single group, meaning that the first vertex
	* in the given collection appears as the first vertex in the path after this method call.
	* Internally, this means that the vertices are actually passed to the {@link #prepend(Point2S)}
	* method in reverse order.
	* @param vertices the points to prepend
	* @return this instance
	* @see #prepend(Point2S)
	*/
	public Builder prependPoints(final Collection<Point2S> vertices) {
	return prependPoints(vertices.toArray(new Point2S[0]));
	}

	/** Convenience method for prepending multiple vertices to the path in a single method call.
	* The vertices are logically prepended as a single group, meaning that the first vertex
	* in the given collection appears as the first vertex in the path after this method call.
	* Internally, this means that the vertices are actually passed to the {@link #prepend(Point2S)}
	* method in reverse order.
	* @param vertices the vertices to prepend
	* @return this instance
	* @see #prepend(Point2S)
	*/
	public Builder prependPoints(final Point2S... vertices) {
	for (int i = vertices.length - 1; i >= 0; --i) {
	prepend(vertices[i]);
	}

	return this;
	}

	/** Close the current path and build a new {@link GreatArcPath} instance. This method is equivalent
	* to {@code builder.build(true)}.
	* @return new closed path instance
	*/
	public GreatArcPath close() {
	return build(true);
	}

	/** Build a {@link GreatArcPath} instance from the configured path. This method is equivalent
	* to {@code builder.build(false)}.
	* @return new path instance
	*/
	public GreatArcPath build() {
	return build(false);
	}

	/** Build a {@link GreatArcPath} instance from the configured path.
	* @param close if true, the path will be closed by adding an end point equivalent to the
	* start point
	* @return new path instance
	*/
	public GreatArcPath build(final boolean close) {
	if (close) {
	closePath();
	}

	// combine all of the arcs
	List<GreatArc> result = null;

	if (prependedArcs != null) {
	result = prependedArcs;
	Collections.reverse(result);
	}

	if (appendedArcs != null) {
	if (result == null) {
	result = appendedArcs;
	} else {
	result.addAll(appendedArcs);
	}
	}

	if (result == null) {
	result = Collections.emptyList();
	}

	if (result.isEmpty() && startVertex != null) {
	throw new IllegalStateException(
	MessageFormat.format("Unable to create path; only a single point provided: {0}",
	startVertex));
	}

	// clear internal state
	appendedArcs = null;
	prependedArcs = null;

	// build the final path instance, using the shared empty instance if
	// no arcs are present
	return result.isEmpty() ? empty() : new GreatArcPath(result);
	}

	/** Close the path by adding an end point equivalent to the path start point.
	* @throws IllegalStateException if the path cannot be closed
	*/
	private void closePath() {
	final GreatArc end = getEndArc();

	if (end != null) {
	if (startVertex != null && endVertex != null) {
	if (!endVertex.eq(startVertex, endVertexPrecision)) {
	appendInternal(GreatArc.fromPoints(endVertex, startVertex, endVertexPrecision));
	}
	} else {
	throw new IllegalStateException("Unable to close path: path is full");
	}
	}
	}

	/** Validate that the given arcs are connected, meaning that the end point of {@code previous}
	* is equivalent to the start point of {@code next}. The arcs are considered valid if either
	* arc is null.
	* @param previous previous arc
	* @param next next arc
	* @throws IllegalStateException if previous and next are not null and the end point of previous
	* is not equivalent the start point of next
	*/
	private void validateArcsConnected(final GreatArc previous, final GreatArc next) {
	if (previous != null && next != null) {
	final Point2S nextStartVertex = next.getStartPoint();
	final Point2S previousEndVertex = previous.getEndPoint();
	final DoublePrecisionContext previousPrecision = previous.getPrecision();

	if (nextStartVertex == null \|\| previousEndVertex == null \|\|
	!(nextStartVertex.eq(previousEndVertex, previousPrecision))) {

	throw new IllegalStateException(
	MessageFormat.format("Path arcs are not connected: previous= {0}, next= {1}",
	previous, next));
	}
	}
	}

	/** Get the precision context used when adding raw points to the path. An exception is thrown
	* if no precision has been specified.
	* @return the precision context used when working with raw points
	* @throws IllegalStateException if no precision context is configured
	*/
	private DoublePrecisionContext getAddPointPrecision() {
	if (precision == null) {
	throw new IllegalStateException("Unable to create arc: no point precision specified");
	}

	return precision;
	}

	/** Append the given, validated arc to the path.
	* @param arc validated arc to append
	*/
	private void appendInternal(final GreatArc arc) {
	if (appendedArcs == null) {
	appendedArcs = new ArrayList<>();
	}

	if (appendedArcs.isEmpty() &&
	(prependedArcs == null \|\| prependedArcs.isEmpty())) {
	startVertex = arc.getStartPoint();
	}

	endVertex = arc.getEndPoint();
	endVertexPrecision = arc.getPrecision();

	appendedArcs.add(arc);
	}

	/** Prepend the given, validated arc to the path.
	* @param arc validated arc to prepend
	*/
	private void prependInternal(final GreatArc arc) {
	if (prependedArcs == null) {
	prependedArcs = new ArrayList<>();
	}

	startVertex = arc.getStartPoint();

	if (prependedArcs.isEmpty() &&
	(appendedArcs == null \|\| appendedArcs.isEmpty())) {
	endVertex = arc.getEndPoint();
	endVertexPrecision = arc.getPrecision();
	}

	prependedArcs.add(arc);
	}

	/** Get the first element in the list or null if the list is null
	* or empty.
	* @param list the list to return the first item from
	* @return the first item from the given list or null if it does not exist
	*/
	private GreatArc getFirst(final List<GreatArc> list) {
	if (list != null && !list.isEmpty()) {
	return list.get(0);
	}
	return null;
	}

	/** Get the last element in the list or null if the list is null
	* or empty.
	* @param list the list to return the last item from
	* @return the last item from the given list or null if it does not exist
	*/
	private GreatArc getLast(final List<GreatArc> list) {
	if (list != null && !list.isEmpty()) {
	return list.get(list.size() - 1);
	}
	return null;
	}
	}
	}