1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.geometry.euclidean.twod.path;
18
19 import java.util.ArrayList;
20 import java.util.List;
21 import java.util.Objects;
22
23 import org.apache.commons.geometry.euclidean.internal.AbstractPathConnector;
24 import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
25 import org.apache.commons.geometry.euclidean.twod.Vector2D;
26 import org.apache.commons.numbers.angle.Angle;
27
28 /** Abstract class for joining collections of line subsets into connected
29 * paths. This class is not thread-safe.
30 */
31 public abstract class AbstractLinePathConnector
32 extends AbstractPathConnector<AbstractLinePathConnector.ConnectableLineSubset> {
33 /** Add a line subset to the connector, leaving it unconnected until a later call to
34 * to {@link #connect(Iterable)} or {@link #connectAll()}.
35 * @param subset line subset to add
36 * @see #connect(Iterable)
37 * @see #connectAll()
38 */
39 public void add(final LineConvexSubset subset) {
40 addPathElement(new ConnectableLineSubset(subset));
41 }
42
43 /** Add a collection of line subsets to the connector, leaving them unconnected
44 * until a later call to {@link #connect(Iterable)} or
45 * {@link #connectAll()}.
46 * @param subsets line subsets to add
47 * @see #connect(Iterable)
48 * @see #connectAll()
49 * @see #add(LineConvexSubset)
50 */
51 public void add(final Iterable<? extends LineConvexSubset> subsets) {
52 for (final LineConvexSubset subset : subsets) {
53 add(subset);
54 }
55 }
56
57 /** Add a collection of line subsets to the connector and attempt to connect each new
58 * line subset with existing subsets. Connections made at this time will not be
59 * overwritten by subsequent calls to this or other connection methods.
60 * (eg, {@link #connectAll()}).
61 *
62 * <p>The connector is not reset by this call. Additional line subsets can still be added
63 * to the current set of paths.</p>
64 * @param subsets line subsets to connect
65 * @see #connectAll()
66 */
67 public void connect(final Iterable<? extends LineConvexSubset> subsets) {
68 final List<ConnectableLineSubset> newEntries = new ArrayList<>();
69
70 for (final LineConvexSubset subset : subsets) {
71 newEntries.add(new ConnectableLineSubset(subset));
72 }
73
74 connectPathElements(newEntries);
75 }
76
77 /** Add the given line subsets to this instance and connect all current
78 * subsets into connected paths. This call is equivalent to
79 * <pre>
80 * connector.add(subsets);
81 * List<LinePath> result = connector.connectAll();
82 * </pre>
83 *
84 * <p>The connector is reset after this call. Further calls to
85 * add or connect line subsets will result in new paths being generated.</p>
86 * @param subsets line subsets to add
87 * @return the connected 2D paths
88 * @see #add(Iterable)
89 * @see #connectAll()
90 */
91 public List<LinePath> connectAll(final Iterable<LineConvexSubset> subsets) {
92 add(subsets);
93 return connectAll();
94 }
95
96 /** Connect all current line subsets into connected paths, returning the result as a
97 * list of line paths.
98 *
99 * <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 }