Source code

001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.geometry.spherical.twod;
018
019import java.util.ArrayList;
020import java.util.List;
021import java.util.Objects;
022
023import org.apache.commons.geometry.euclidean.internal.AbstractPathConnector;
024import org.apache.commons.geometry.euclidean.threed.Vector3D;
025
026/** Abstract class for joining collections of great arcs into connected
027 * paths. This class is not thread-safe.
028 */
029public abstract class AbstractGreatArcConnector
030    extends AbstractPathConnector<AbstractGreatArcConnector.ConnectableGreatArc> {
031    /** Add an arc to the connector, leaving it unconnected until a later call to
032     * to {@link #connect(Iterable)} or {@link #connectAll()}.
033     * @param arc arc to add
034     * @see #connect(Iterable)
035     * @see #connectAll()
036     */
037    public void add(final GreatArc arc) {
038        addPathElement(new ConnectableGreatArc(arc));
039    }
040
041    /** Add a collection of arcs to the connector, leaving them unconnected
042     * until a later call to {@link #connect(Iterable)} or
043     * {@link #connectAll()}.
044     * @param arcs arcs to add
045     * @see #connect(Iterable)
046     * @see #connectAll()
047     * @see #add(GreatArc)
048     */
049    public void add(final Iterable<GreatArc> arcs) {
050        for (final GreatArc segment : arcs) {
051            add(segment);
052        }
053    }
054
055    /** Add a collection of arcs to the connector and attempt to connect each new
056     * arc with existing ones. Connections made at this time will not be
057     * overwritten by subsequent calls to this or other connection methods,
058     * (eg, {@link #connectAll()}).
059     *
060     * <p>The connector is not reset by this call. Additional arc can still be added
061     * to the current set of paths.</p>
062     * @param arcs arcs to connect
063     * @see #connectAll()
064     */
065    public void connect(final Iterable<GreatArc> arcs) {
066        final List<ConnectableGreatArc> newEntries = new ArrayList<>();
067
068        for (final GreatArc segment : arcs) {
069            newEntries.add(new ConnectableGreatArc(segment));
070        }
071
072        connectPathElements(newEntries);
073    }
074
075    /** Add the given arcs to this instance and connect all current
076     * arc into paths. This call is equivalent to
077     * <pre>
078     *      connector.add(arcs);
079     *      List&lt;GreatArcPath&gt; result = connector.connectAll();
080     * </pre>
081     *
082     * <p>The connector is reset after this call. Further calls to
083     * add or connect arcs will result in new paths being generated.</p>
084     * @param arcs arcs to add
085     * @return the connected arc paths
086     * @see #add(Iterable)
087     * @see #connectAll()
088     */
089    public List<GreatArcPath> connectAll(final Iterable<GreatArc> arcs) {
090        add(arcs);
091        return connectAll();
092    }
093
094    /** Connect all current arcs into connected paths, returning the result as a
095     * list of arc paths.
096     *
097     * <p>The connector is reset after this call. Further calls to
098     * add or connect arcs will result in new paths being generated.</p>
099     * @return the connected line segments paths
100     */
101    public List<GreatArcPath> connectAll() {
102        final List<ConnectableGreatArc> roots = computePathRoots();
103        final List<GreatArcPath> paths = new ArrayList<>(roots.size());
104
105        for (final ConnectableGreatArc root : roots) {
106            paths.add(toPath(root));
107        }
108
109        return paths;
110    }
111
112    /** Convert the linked list of path elements starting at the argument
113     * into a {@link GreatArcPath}.
114     * @param root root of a connected path linked list
115     * @return a great arc path representing the linked list path
116     */
117    private GreatArcPath toPath(final ConnectableGreatArc root) {
118        final GreatArcPath.Builder builder = GreatArcPath.builder(null);
119
120        builder.append(root.getArc());
121
122        ConnectableGreatArc current = root.getNext();
123
124        while (current != null && current != root) {
125            builder.append(current.getArc());
126            current = current.getNext();
127        }
128
129        return builder.build();
130    }
131
132    /** Internal class for connecting {@link GreatArc}s into {@link GreatArcPath}s.
133     */
134    protected static class ConnectableGreatArc extends AbstractPathConnector.ConnectableElement<ConnectableGreatArc> {
135        /** Segment start point. This will be used to connect to other path elements. */
136        private final Point2S start;
137
138        /** Great arc for this instance. */
139        private final GreatArc arc;
140
141        /** Create a new instance with the given start point. This constructor is
142         * intended only for performing searches for other path elements.
143         * @param start start point
144         */
145        public ConnectableGreatArc(final Point2S start) {
146            this(start, null);
147        }
148
149        /** Create a new instance from the given arc.
150         * @param arc arc for the instance
151         */
152        public ConnectableGreatArc(final GreatArc arc) {
153            this(arc.getStartPoint(), arc);
154        }
155
156        /** Create a new instance with the given start point and arc.
157         * @param start start point
158         * @param arc arc for the instance
159         */
160        private ConnectableGreatArc(final Point2S start, final GreatArc arc) {
161            this.start = start;
162            this.arc = arc;
163        }
164
165        /** Get the arc for the instance.
166         * @return the arc for the instance
167         */
168        public GreatArc getArc() {
169            return arc;
170        }
171
172        /** {@inheritDoc} */
173        @Override
174        public boolean hasStart() {
175            return start != null;
176        }
177
178        /** {@inheritDoc} */
179        @Override
180        public boolean hasEnd() {
181            return arc.getEndPoint() != null;
182        }
183
184        /** {@inheritDoc} */
185        @Override
186        public boolean endPointsEq(final ConnectableGreatArc other) {
187            if (hasEnd() && other.hasEnd()) {
188                return arc.getEndPoint()
189                        .eq(other.arc.getEndPoint(), arc.getCircle().getPrecision());
190            }
191
192            return false;
193        }
194
195        /** Return true if this instance has a size equivalent to zero.
196         * @return true if this instance has a size equivalent to zero.
197         */
198        public boolean hasZeroSize() {
199            return arc != null && arc.getCircle().getPrecision().eqZero(arc.getSize());
200        }
201
202        /** {@inheritDoc} */
203        @Override
204        public boolean canConnectTo(final ConnectableGreatArc next) {
205            final Point2S end = arc.getEndPoint();
206            final Point2S nextStart = next.start;
207
208            return end != null && nextStart != null &&
209                    end.eq(nextStart, arc.getCircle().getPrecision());
210        }
211
212        /** {@inheritDoc} */
213        @Override
214        public double getRelativeAngle(final ConnectableGreatArc other) {
215            return arc.getCircle().angle(other.getArc().getCircle());
216        }
217
218        /** {@inheritDoc} */
219        @Override
220        public ConnectableGreatArc getConnectionSearchKey() {
221            return new ConnectableGreatArc(arc.getEndPoint());
222        }
223
224        /** {@inheritDoc} */
225        @Override
226        public boolean shouldContinueConnectionSearch(final ConnectableGreatArc candidate,
227                final boolean ascending) {
228
229            if (candidate.hasStart()) {
230                final double candidatePolar = candidate.getArc().getStartPoint().getPolar();
231                final double thisPolar = arc.getEndPoint().getPolar();
232                final int cmp = arc.getCircle().getPrecision().compare(candidatePolar, thisPolar);
233
234                return ascending ? cmp <= 0 : cmp >= 0;
235            }
236
237            return true;
238        }
239
240        /** {@inheritDoc} */
241        @Override
242        public int compareTo(final ConnectableGreatArc other) {
243            int cmp = Point2S.POLAR_AZIMUTH_ASCENDING_ORDER.compare(start, other.start);
244
245            if (cmp == 0) {
246                // sort entries without arcs before ones with arcs
247                final boolean thisHasArc = arc != null;
248                final boolean otherHasArc = other.arc != null;
249
250                cmp = Boolean.compare(thisHasArc, otherHasArc);
251
252                if (cmp == 0 && thisHasArc) {
253                    // place point-like segments before ones with non-zero length
254                    cmp = Boolean.compare(this.hasZeroSize(), other.hasZeroSize());
255
256                    if (cmp == 0) {
257                        // sort by circle pole
258                        cmp = Vector3D.COORDINATE_ASCENDING_ORDER.compare(
259                                arc.getCircle().getPole(),
260                                other.arc.getCircle().getPole());
261                    }
262                }
263            }
264
265            return cmp;
266        }
267
268        /** {@inheritDoc} */
269        @Override
270        public int hashCode() {
271            return Objects.hash(start, arc);
272        }
273
274        /** {@inheritDoc} */
275        @Override
276        public boolean equals(final Object obj) {
277            if (this == obj) {
278                return true;
279            }
280            if (obj == null || !this.getClass().equals(obj.getClass())) {
281                return false;
282            }
283
284            final ConnectableGreatArc other = (ConnectableGreatArc) obj;
285            return Objects.equals(this.start, other.start) &&
286                    Objects.equals(this.arc, other.arc);
287        }
288
289        /** {@inheritDoc} */
290        @Override
291        protected ConnectableGreatArc getSelf() {
292            return this;
293        }
294    }
295}