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.euclidean.twod.path;
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.twod.LineConvexSubset;
025import org.apache.commons.geometry.euclidean.twod.Vector2D;
026import org.apache.commons.numbers.angle.Angle;
027
028/** Abstract class for joining collections of line subsets into connected
029 * paths. This class is not thread-safe.
030 */
031public abstract class AbstractLinePathConnector
032    extends AbstractPathConnector<AbstractLinePathConnector.ConnectableLineSubset> {
033    /** Add a line subset to the connector, leaving it unconnected until a later call to
034     * to {@link #connect(Iterable)} or {@link #connectAll()}.
035     * @param subset line subset to add
036     * @see #connect(Iterable)
037     * @see #connectAll()
038     */
039    public void add(final LineConvexSubset subset) {
040        addPathElement(new ConnectableLineSubset(subset));
041    }
042
043    /** Add a collection of line subsets to the connector, leaving them unconnected
044     * until a later call to {@link #connect(Iterable)} or
045     * {@link #connectAll()}.
046     * @param subsets line subsets to add
047     * @see #connect(Iterable)
048     * @see #connectAll()
049     * @see #add(LineConvexSubset)
050     */
051    public void add(final Iterable<? extends LineConvexSubset> subsets) {
052        for (final LineConvexSubset subset : subsets) {
053            add(subset);
054        }
055    }
056
057    /** Add a collection of line subsets to the connector and attempt to connect each new
058     * line subset with existing subsets. Connections made at this time will not be
059     * overwritten by subsequent calls to this or other connection methods.
060     * (eg, {@link #connectAll()}).
061     *
062     * <p>The connector is not reset by this call. Additional line subsets can still be added
063     * to the current set of paths.</p>
064     * @param subsets line subsets to connect
065     * @see #connectAll()
066     */
067    public void connect(final Iterable<? extends LineConvexSubset> subsets) {
068        final List<ConnectableLineSubset> newEntries = new ArrayList<>();
069
070        for (final LineConvexSubset subset : subsets) {
071            newEntries.add(new ConnectableLineSubset(subset));
072        }
073
074        connectPathElements(newEntries);
075    }
076
077    /** Add the given line subsets to this instance and connect all current
078     * subsets into connected paths. This call is equivalent to
079     * <pre>
080     *      connector.add(subsets);
081     *      List&lt;LinePath&gt; result = connector.connectAll();
082     * </pre>
083     *
084     * <p>The connector is reset after this call. Further calls to
085     * add or connect line subsets will result in new paths being generated.</p>
086     * @param subsets line subsets to add
087     * @return the connected 2D paths
088     * @see #add(Iterable)
089     * @see #connectAll()
090     */
091    public List<LinePath> connectAll(final Iterable<LineConvexSubset> subsets) {
092        add(subsets);
093        return connectAll();
094    }
095
096    /** Connect all current line subsets into connected paths, returning the result as a
097     * list of line paths.
098     *
099     * <p>The connector is reset after this call. Further calls to
100     * add or connect line subsets will result in new paths being generated.</p>
101     * @return the connected 2D paths
102     */
103    public List<LinePath> connectAll() {
104        final List<ConnectableLineSubset> roots = computePathRoots();
105        final List<LinePath> paths = new ArrayList<>(roots.size());
106
107        for (final ConnectableLineSubset root : roots) {
108            paths.add(toPath(root));
109        }
110
111        return paths;
112    }
113
114    /** Convert the linked list of path elements starting at the argument
115     * into a {@link LinePath}.
116     * @param root root of a connected path linked list
117     * @return a line path representing the linked list path
118     */
119    private LinePath toPath(final ConnectableLineSubset root) {
120        final LinePath.Builder builder = LinePath.builder(null);
121
122        builder.append(root.getLineSubset());
123
124        ConnectableLineSubset current = root.getNext();
125
126        while (current != null && current != root) {
127            builder.append(current.getLineSubset());
128            current = current.getNext();
129        }
130
131        return builder.build();
132    }
133
134    /** Internal class used to connect line subsets together.
135     */
136    protected static class ConnectableLineSubset
137        extends AbstractPathConnector.ConnectableElement<ConnectableLineSubset> {
138        /** Line subset start point. This will be used to connect to other path elements. */
139        private final Vector2D start;
140
141        /** Line subset for the entry. */
142        private final LineConvexSubset subset;
143
144        /** Create a new instance with the given start point. This constructor is
145         * intended only for performing searches for other path elements.
146         * @param start start point
147         */
148        public ConnectableLineSubset(final Vector2D start) {
149            this(start, null);
150        }
151
152        /** Create a new instance from the given line subset.
153         * @param subset subset instance
154         */
155        public ConnectableLineSubset(final LineConvexSubset subset) {
156            this(subset.getStartPoint(), subset);
157        }
158
159        /** Create a new instance with the given start point and line subset.
160         * @param start start point
161         * @param subset line subset instance
162         */
163        private ConnectableLineSubset(final Vector2D start, final LineConvexSubset subset) {
164            this.start = start;
165            this.subset = subset;
166        }
167
168        /** Get the line subset for this instance.
169         * @return the line subset for this instance
170         */
171        public LineConvexSubset getLineSubset() {
172            return subset;
173        }
174
175        /** {@inheritDoc} */
176        @Override
177        public boolean hasStart() {
178            return start != null;
179        }
180
181        /** {@inheritDoc} */
182        @Override
183        public boolean hasEnd() {
184            return subset != null && subset.getEndPoint() != null;
185        }
186
187        /** Return true if this instance has a size equivalent to zero.
188         * @return true if this instance has a size equivalent to zero.
189         */
190        public boolean hasZeroSize() {
191            return subset != null && subset.getPrecision().eqZero(subset.getSize());
192        }
193
194        /** {@inheritDoc} */
195        @Override
196        public boolean endPointsEq(final ConnectableLineSubset other) {
197            if (hasEnd() && other.hasEnd()) {
198                return subset.getEndPoint()
199                        .eq(other.subset.getEndPoint(), subset.getPrecision());
200            }
201
202            return false;
203        }
204
205        /** {@inheritDoc} */
206        @Override
207        public boolean canConnectTo(final ConnectableLineSubset next) {
208            final Vector2D end = subset.getEndPoint();
209            final Vector2D nextStart = next.start;
210
211            return end != null && nextStart != null &&
212                    end.eq(nextStart, subset.getPrecision());
213        }
214
215        /** {@inheritDoc} */
216        @Override
217        public double getRelativeAngle(final ConnectableLineSubset next) {
218            return subset.getLine().angle(next.getLineSubset().getLine());
219        }
220
221        /** {@inheritDoc} */
222        @Override
223        public ConnectableLineSubset getConnectionSearchKey() {
224            return new ConnectableLineSubset(subset.getEndPoint());
225        }
226
227        /** {@inheritDoc} */
228        @Override
229        public boolean shouldContinueConnectionSearch(final ConnectableLineSubset candidate, final boolean ascending) {
230
231            if (candidate.hasStart()) {
232                final double candidateX = candidate.getLineSubset().getStartPoint().getX();
233                final double thisX = subset.getEndPoint().getX();
234                final int cmp = subset.getPrecision().compare(candidateX, thisX);
235
236                return ascending ? cmp <= 0 : cmp >= 0;
237            }
238
239            return true;
240        }
241
242        /** {@inheritDoc} */
243        @Override
244        public int compareTo(final ConnectableLineSubset other) {
245            // sort by coordinates
246            int cmp = Vector2D.COORDINATE_ASCENDING_ORDER.compare(start, other.start);
247            if (cmp == 0) {
248                // sort entries without line subsets before ones with
249                final boolean thisHasSubset = subset != null;
250                final boolean otherHasSubset = other.subset != null;
251
252                cmp = Boolean.compare(thisHasSubset, otherHasSubset);
253
254                if (cmp == 0 && thisHasSubset) {
255                    // place point-like line subsets before ones with non-zero length
256                    cmp = Boolean.compare(this.hasZeroSize(), other.hasZeroSize());
257
258                    if (cmp == 0) {
259                        // sort by line angle
260                        final double aAngle = Angle.Rad.WITHIN_MINUS_PI_AND_PI.applyAsDouble(
261                                this.getLineSubset().getLine().getAngle());
262                        final double bAngle = Angle.Rad.WITHIN_MINUS_PI_AND_PI.applyAsDouble(
263                                other.getLineSubset().getLine().getAngle());
264
265                        cmp = Double.compare(aAngle, bAngle);
266                    }
267                }
268            }
269            return cmp;
270        }
271
272        /** {@inheritDoc} */
273        @Override
274        public int hashCode() {
275            return Objects.hash(start, subset);
276        }
277
278        /** {@inheritDoc} */
279        @Override
280        public boolean equals(final Object obj) {
281            if (this == obj) {
282                return true;
283            }
284            if (obj == null || !this.getClass().equals(obj.getClass())) {
285                return false;
286            }
287
288            final ConnectableLineSubset other = (ConnectableLineSubset) obj;
289            return Objects.equals(this.start, other.start) &&
290                    Objects.equals(this.subset, other.subset);
291        }
292
293        /** {@inheritDoc} */
294        @Override
295        protected ConnectableLineSubset getSelf() {
296            return this;
297        }
298    }
299}