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 * https://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
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.geometry.euclidean.twod;
23
24 import java.util.ArrayList;
25 import java.util.Collection;
26 import java.util.IdentityHashMap;
27 import java.util.List;
28 import java.util.Map;
29
30 import org.hipparchus.exception.MathIllegalStateException;
31 import org.hipparchus.geometry.LocalizedGeometryFormats;
32 import org.hipparchus.geometry.euclidean.oned.Euclidean1D;
33 import org.hipparchus.geometry.euclidean.oned.Interval;
34 import org.hipparchus.geometry.euclidean.oned.IntervalsSet;
35 import org.hipparchus.geometry.euclidean.oned.OrientedPoint;
36 import org.hipparchus.geometry.euclidean.oned.SubOrientedPoint;
37 import org.hipparchus.geometry.euclidean.oned.Vector1D;
38 import org.hipparchus.geometry.partitioning.AbstractRegion;
39 import org.hipparchus.geometry.partitioning.BSPTree;
40 import org.hipparchus.geometry.partitioning.BSPTreeVisitor;
41 import org.hipparchus.geometry.partitioning.BoundaryAttribute;
42 import org.hipparchus.geometry.partitioning.InteriorPointFinder;
43 import org.hipparchus.geometry.partitioning.Side;
44 import org.hipparchus.geometry.partitioning.SubHyperplane;
45 import org.hipparchus.util.FastMath;
46 import org.hipparchus.util.Precision;
47
48 /** This class represents a 2D region: a set of polygons.
49 */
50 public class PolygonsSet
51 extends AbstractRegion<Euclidean2D, Vector2D, Line, SubLine, Euclidean1D, Vector1D, OrientedPoint, SubOrientedPoint> {
52
53 /** Vertices organized as boundary loops. */
54 private Vector2D[][] vertices;
55
56 /** Build a polygons set representing the whole plane.
57 * @param tolerance tolerance below which points are considered identical
58 */
59 public PolygonsSet(final double tolerance) {
60 super(tolerance);
61 }
62
63 /** Build a polygons set from a BSP tree.
64 * <p>The leaf nodes of the BSP tree <em>must</em> have a
65 * {@code Boolean} attribute representing the inside status of
66 * the corresponding cell (true for inside cells, false for outside
67 * cells). In order to avoid building too many small objects, it is
68 * recommended to use the predefined constants
69 * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
70 * <p>
71 * This constructor is aimed at expert use, as building the tree may
72 * be a difficult task. It is not intended for general use and for
73 * performances reasons does not check thoroughly its input, as this would
74 * require walking the full tree each time. Failing to provide a tree with
75 * the proper attributes, <em>will</em> therefore generate problems like
76 * {@link NullPointerException} or {@link ClassCastException} only later on.
77 * This limitation is known and explains why this constructor is for expert
78 * use only. The caller does have the responsibility to provided correct arguments.
79 * </p>
80 * @param tree inside/outside BSP tree representing the region
81 * @param tolerance tolerance below which points are considered identical
82 */
83 public PolygonsSet(final BSPTree<Euclidean2D, Vector2D, Line, SubLine> tree, final double tolerance) {
84 super(tree, tolerance);
85 }
86
87 /** Build a polygons set from a Boundary REPresentation (B-rep).
88 * <p>The boundary is provided as a collection of {@link
89 * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
90 * interior part of the region on its minus side and the exterior on
91 * its plus side.</p>
92 * <p>The boundary elements can be in any order, and can form
93 * several non-connected sets (like for example polygons with holes
94 * or a set of disjoint polygons considered as a whole). In
95 * fact, the elements do not even need to be connected together
96 * (their topological connections are not used here). However, if the
97 * boundary does not really separate an inside open from an outside
98 * open (open having here its topological meaning), then subsequent
99 * calls to the {@link
100 * org.hipparchus.geometry.partitioning.Region#checkPoint(org.hipparchus.geometry.Point)
101 * checkPoint} method will not be meaningful anymore.</p>
102 * <p>If the boundary is empty, the region will represent the whole
103 * space.</p>
104 * @param boundary collection of boundary elements, as a
105 * collection of {@link SubHyperplane SubHyperplane} objects
106 * @param tolerance tolerance below which points are considered identical
107 */
108 public PolygonsSet(final Collection<SubLine> boundary, final double tolerance) {
109 super(boundary, tolerance);
110 }
111
112 /** Build a parallellepipedic box.
113 * @param xMin low bound along the x direction
114 * @param xMax high bound along the x direction
115 * @param yMin low bound along the y direction
116 * @param yMax high bound along the y direction
117 * @param tolerance tolerance below which points are considered identical
118 */
119 public PolygonsSet(final double xMin, final double xMax,
120 final double yMin, final double yMax,
121 final double tolerance) {
122 super(boxBoundary(xMin, xMax, yMin, yMax, tolerance), tolerance);
123 }
124
125 /** Build a polygon from a simple list of vertices.
126 * <p>The boundary is provided as a list of points considering to
127 * represent the vertices of a simple loop. The interior part of the
128 * region is on the left side of this path and the exterior is on its
129 * right side.</p>
130 * <p>This constructor does not handle polygons with a boundary
131 * forming several disconnected paths (such as polygons with holes).</p>
132 * <p>For cases where this simple constructor applies, it is expected to
133 * be numerically more robust than the {@link #PolygonsSet(Collection,double) general
134 * constructor} using {@link SubHyperplane subhyperplanes}.</p>
135 * <p>If the list is empty, the region will represent the whole
136 * space.</p>
137 * <p>
138 * Polygons with thin pikes or dents are inherently difficult to handle because
139 * they involve lines with almost opposite directions at some vertices. Polygons
140 * whose vertices come from some physical measurement with noise are also
141 * difficult because an edge that should be straight may be broken in lots of
142 * different pieces with almost equal directions. In both cases, computing the
143 * lines intersections is not numerically robust due to the almost 0 or almost
144 * π angle. Such cases need to carefully adjust the {@code hyperplaneThickness}
145 * parameter. A too small value would often lead to completely wrong polygons
146 * with large area wrongly identified as inside or outside. Large values are
147 * often much safer. As a rule of thumb, a value slightly below the size of the
148 * most accurate detail needed is a good value for the {@code hyperplaneThickness}
149 * parameter.
150 * </p>
151 * @param hyperplaneThickness tolerance below which points are considered to
152 * belong to the hyperplane (which is therefore more a slab)
153 * @param vertices vertices of the simple loop boundary
154 */
155 public PolygonsSet(final double hyperplaneThickness, final Vector2D ... vertices) {
156 super(verticesToTree(hyperplaneThickness, vertices), hyperplaneThickness);
157 }
158
159 /** Create a list of hyperplanes representing the boundary of a box.
160 * @param xMin low bound along the x direction
161 * @param xMax high bound along the x direction
162 * @param yMin low bound along the y direction
163 * @param yMax high bound along the y direction
164 * @param tolerance tolerance below which points are considered identical
165 * @return boundary of the box
166 */
167 private static Line[] boxBoundary(final double xMin, final double xMax,
168 final double yMin, final double yMax,
169 final double tolerance) {
170 if ((xMin >= xMax - tolerance) || (yMin >= yMax - tolerance)) {
171 // too thin box, build an empty polygons set
172 return null; // NOPMD
173 }
174 final Vector2D minMin = new Vector2D(xMin, yMin);
175 final Vector2D minMax = new Vector2D(xMin, yMax);
176 final Vector2D maxMin = new Vector2D(xMax, yMin);
177 final Vector2D maxMax = new Vector2D(xMax, yMax);
178 return new Line[] {
179 new Line(minMin, maxMin, tolerance),
180 new Line(maxMin, maxMax, tolerance),
181 new Line(maxMax, minMax, tolerance),
182 new Line(minMax, minMin, tolerance)
183 };
184 }
185
186 /** Build the BSP tree of a polygons set from a simple list of vertices.
187 * <p>The boundary is provided as a list of points considering to
188 * represent the vertices of a simple loop. The interior part of the
189 * region is on the left side of this path and the exterior is on its
190 * right side.</p>
191 * <p>This constructor does not handle polygons with a boundary
192 * forming several disconnected paths (such as polygons with holes).</p>
193 * <p>For cases where this simple constructor applies, it is expected to
194 * be numerically more robust than the {@link #PolygonsSet(Collection,double) general
195 * constructor} using {@link SubHyperplane subhyperplanes}.</p>
196 * @param hyperplaneThickness tolerance below which points are consider to
197 * belong to the hyperplane (which is therefore more a slab)
198 * @param vertices vertices of the simple loop boundary
199 * @return the BSP tree of the input vertices
200 */
201 private static BSPTree<Euclidean2D, Vector2D, Line, SubLine> verticesToTree(final double hyperplaneThickness,
202 final Vector2D ... vertices) {
203
204 final int n = vertices.length;
205 if (n == 0) {
206 // the tree represents the whole space
207 return new BSPTree<>(Boolean.TRUE);
208 }
209
210 // build the vertices
211 final Vertex[] vArray = new Vertex[n];
212 final Map<Vertex, List<Line>> bindings = new IdentityHashMap<>(n);
213 for (int i = 0; i < n; ++i) {
214 vArray[i] = new Vertex(vertices[i]);
215 bindings.put(vArray[i], new ArrayList<>());
216 }
217
218 // build the edges
219 List<Edge> edges = new ArrayList<>(n);
220 for (int i = 0; i < n; ++i) {
221
222 // get the endpoints of the edge
223 final Vertex start = vArray[i];
224 final Vertex end = vArray[(i + 1) % n];
225
226 // get the line supporting the edge, taking care not to recreate it if it was
227 // already created earlier due to another edge being aligned with the current one
228 final Line line = supportingLine(start, end, vArray, bindings, hyperplaneThickness);
229
230 // create the edge and store it
231 edges.add(new Edge(start, end, line));
232
233 }
234
235 // build the tree top-down
236 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> tree = new BSPTree<>();
237 insertEdges(hyperplaneThickness, tree, edges);
238
239 return tree;
240
241 }
242
243 /** Get the supporting line for two vertices.
244 * @param start start vertex of an edge being built
245 * @param end end vertex of an edge being built
246 * @param vArray array containing all vertices
247 * @param bindings bindings between vertices and lines
248 * @param hyperplaneThickness tolerance below which points are consider to
249 * belong to the hyperplane (which is therefore more a slab)
250 * @return line bound with both start and end and in the proper orientation
251 */
252 private static Line supportingLine(final Vertex start, final Vertex end,
253 final Vertex[] vArray,
254 final Map<Vertex, List<Line>> bindings,
255 final double hyperplaneThickness) {
256
257 Line toBeReversed = null;
258 for (final Line line1 : bindings.get(start)) {
259 for (final Line line2 : bindings.get(end)) {
260 if (line1 == line2) {
261 // we already know a line to which both vertices belong
262 final double xs = line1.toSubSpace(start.getLocation()).getX();
263 final double xe = line1.toSubSpace(end.getLocation()).getX();
264 if (xe >= xs) {
265 // the known line has the proper orientation
266 return line1;
267 } else {
268 toBeReversed = line1;
269 }
270 }
271 }
272 }
273
274 // we need to create a new circle
275 final Line newLine = (toBeReversed == null) ?
276 new Line(start.getLocation(), end.getLocation(), hyperplaneThickness) :
277 toBeReversed.getReverse();
278
279 bindings.get(start).add(newLine);
280 bindings.get(end).add(newLine);
281
282 // check if another vertex also happens to be on this line
283 for (final Vertex vertex : vArray) {
284 if (vertex != start && vertex != end &&
285 FastMath.abs(newLine.getOffset(vertex.getLocation())) <= hyperplaneThickness) {
286 bindings.get(vertex).add(newLine);
287 }
288 }
289
290 return newLine;
291
292 }
293
294 /** Recursively build a tree by inserting cut sub-hyperplanes.
295 * @param hyperplaneThickness tolerance below which points are consider to
296 * belong to the hyperplane (which is therefore more a slab)
297 * @param node current tree node (it is a leaf node at the beginning
298 * of the call)
299 * @param edges list of edges to insert in the cell defined by this node
300 * (excluding edges not belonging to the cell defined by this node)
301 */
302 private static void insertEdges(final double hyperplaneThickness,
303 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node,
304 final List<Edge> edges) {
305
306 // find an edge with an hyperplane that can be inserted in the node
307 int index = 0;
308 Edge inserted =null;
309 while (inserted == null && index < edges.size()) {
310 inserted = edges.get(index++);
311 if (inserted.getNode() == null) {
312 if (node.insertCut(inserted.getLine())) {
313 inserted.setNode(node);
314 } else {
315 inserted = null;
316 }
317 } else {
318 inserted = null;
319 }
320 }
321
322 if (inserted == null) {
323 // no suitable edge was found, the node remains a leaf node
324 // we need to set its inside/outside boolean indicator
325 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> parent = node.getParent();
326 if (parent == null || node == parent.getMinus()) {
327 node.setAttribute(Boolean.TRUE);
328 } else {
329 node.setAttribute(Boolean.FALSE);
330 }
331 return;
332 }
333
334 // we have split the node by inserting an edge as a cut sub-hyperplane
335 // distribute the remaining edges in the two sub-trees
336 final List<Edge> plusList = new ArrayList<>();
337 final List<Edge> minusList = new ArrayList<>();
338 for (final Edge edge : edges) {
339 if (edge != inserted) {
340 final double startOffset = inserted.getLine().getOffset(edge.getStart().getLocation());
341 final double endOffset = inserted.getLine().getOffset(edge.getEnd().getLocation());
342 Side startSide = (FastMath.abs(startOffset) <= hyperplaneThickness) ?
343 Side.HYPER : ((startOffset < 0) ? Side.MINUS : Side.PLUS);
344 Side endSide = (FastMath.abs(endOffset) <= hyperplaneThickness) ?
345 Side.HYPER : ((endOffset < 0) ? Side.MINUS : Side.PLUS);
346 switch (startSide) {
347 case PLUS:
348 if (endSide == Side.MINUS) {
349 // we need to insert a split point on the hyperplane
350 final Vertex splitPoint = edge.split(inserted.getLine());
351 minusList.add(splitPoint.getOutgoing());
352 plusList.add(splitPoint.getIncoming());
353 } else {
354 plusList.add(edge);
355 }
356 break;
357 case MINUS:
358 if (endSide == Side.PLUS) {
359 // we need to insert a split point on the hyperplane
360 final Vertex splitPoint = edge.split(inserted.getLine());
361 minusList.add(splitPoint.getIncoming());
362 plusList.add(splitPoint.getOutgoing());
363 } else {
364 minusList.add(edge);
365 }
366 break;
367 default:
368 if (endSide == Side.PLUS) {
369 plusList.add(edge);
370 } else if (endSide == Side.MINUS) {
371 minusList.add(edge);
372 }
373 break;
374 }
375 }
376 }
377
378 // recurse through lower levels
379 if (!plusList.isEmpty()) {
380 insertEdges(hyperplaneThickness, node.getPlus(), plusList);
381 } else {
382 node.getPlus().setAttribute(Boolean.FALSE);
383 }
384 if (!minusList.isEmpty()) {
385 insertEdges(hyperplaneThickness, node.getMinus(), minusList);
386 } else {
387 node.getMinus().setAttribute(Boolean.TRUE);
388 }
389
390 }
391
392 /** Internal class for holding vertices while they are processed to build a BSP tree. */
393 private static class Vertex {
394
395 /** Vertex location. */
396 private final Vector2D location;
397
398 /** Incoming edge. */
399 private Edge incoming;
400
401 /** Outgoing edge. */
402 private Edge outgoing;
403
404 /** Build a non-processed vertex not owned by any node yet.
405 * @param location vertex location
406 */
407 Vertex(final Vector2D location) {
408 this.location = location;
409 this.incoming = null;
410 this.outgoing = null;
411 }
412
413 /** Get Vertex location.
414 * @return vertex location
415 */
416 public Vector2D getLocation() {
417 return location;
418 }
419
420 /** Set incoming edge.
421 * <p>
422 * The line supporting the incoming edge is automatically bound
423 * with the instance.
424 * </p>
425 * @param incoming incoming edge
426 */
427 public void setIncoming(final Edge incoming) {
428 this.incoming = incoming;
429 }
430
431 /** Get incoming edge.
432 * @return incoming edge
433 */
434 public Edge getIncoming() {
435 return incoming;
436 }
437
438 /** Set outgoing edge.
439 * <p>
440 * The line supporting the outgoing edge is automatically bound
441 * with the instance.
442 * </p>
443 * @param outgoing outgoing edge
444 */
445 public void setOutgoing(final Edge outgoing) {
446 this.outgoing = outgoing;
447 }
448
449 /** Get outgoing edge.
450 * @return outgoing edge
451 */
452 public Edge getOutgoing() {
453 return outgoing;
454 }
455
456 }
457
458 /** Internal class for holding edges while they are processed to build a BSP tree. */
459 private static class Edge {
460
461 /** Start vertex. */
462 private final Vertex start;
463
464 /** End vertex. */
465 private final Vertex end;
466
467 /** Line supporting the edge. */
468 private final Line line;
469
470 /** Node whose cut hyperplane contains this edge. */
471 private BSPTree<Euclidean2D, Vector2D, Line, SubLine> node;
472
473 /** Build an edge not contained in any node yet.
474 * @param start start vertex
475 * @param end end vertex
476 * @param line line supporting the edge
477 */
478 Edge(final Vertex start, final Vertex end, final Line line) {
479
480 this.start = start;
481 this.end = end;
482 this.line = line;
483 this.node = null;
484
485 // connect the vertices back to the edge
486 start.setOutgoing(this);
487 end.setIncoming(this);
488
489 }
490
491 /** Get start vertex.
492 * @return start vertex
493 */
494 public Vertex getStart() {
495 return start;
496 }
497
498 /** Get end vertex.
499 * @return end vertex
500 */
501 public Vertex getEnd() {
502 return end;
503 }
504
505 /** Get the line supporting this edge.
506 * @return line supporting this edge
507 */
508 public Line getLine() {
509 return line;
510 }
511
512 /** Set the node whose cut hyperplane contains this edge.
513 * @param node node whose cut hyperplane contains this edge
514 */
515 public void setNode(final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node) {
516 this.node = node;
517 }
518
519 /** Get the node whose cut hyperplane contains this edge.
520 * @return node whose cut hyperplane contains this edge
521 * (null if edge has not yet been inserted into the BSP tree)
522 */
523 public BSPTree<Euclidean2D, Vector2D, Line, SubLine> getNode() {
524 return node;
525 }
526
527 /** Split the edge.
528 * <p>
529 * Once split, this edge is not referenced anymore by the vertices,
530 * it is replaced by the two half-edges and an intermediate splitting
531 * vertex is introduced to connect these two halves.
532 * </p>
533 * @param splitLine line splitting the edge in two halves
534 * @return split vertex (its incoming and outgoing edges are the two halves)
535 */
536 public Vertex split(final Line splitLine) {
537 final Vertex splitVertex = new Vertex(line.intersection(splitLine));
538 final Edge startHalf = new Edge(start, splitVertex, line);
539 final Edge endHalf = new Edge(splitVertex, end, line);
540 startHalf.node = node;
541 endHalf.node = node;
542 return splitVertex;
543 }
544
545 }
546
547 /** {@inheritDoc} */
548 @Override
549 public PolygonsSet buildNew(final BSPTree<Euclidean2D, Vector2D, Line, SubLine> tree) {
550 return new PolygonsSet(tree, getTolerance());
551 }
552
553 /** {@inheritDoc} */
554 @Override
555 public Vector2D getInteriorPoint() {
556 final InteriorPointFinder<Euclidean2D, Vector2D, Line, SubLine> finder =
557 new InteriorPointFinder<>(Vector2D.ZERO);
558 getTree(false).visit(finder);
559 final BSPTree.InteriorPoint<Euclidean2D, Vector2D> interior = finder.getPoint();
560 return interior == null ? null : interior.getPoint();
561 }
562
563 /** {@inheritDoc} */
564 @Override
565 protected void computeGeometricalProperties() {
566
567 final Vector2D[][] v = getVertices();
568
569 if (v.length == 0) {
570 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> tree = getTree(false);
571 if (tree.getCut() == null && (Boolean) tree.getAttribute()) {
572 // the instance covers the whole space
573 setSize(Double.POSITIVE_INFINITY);
574 setBarycenter(Vector2D.NaN);
575 } else {
576 setSize(0);
577 setBarycenter(new Vector2D(0, 0));
578 }
579 } else if (v[0][0] == null) {
580 // there is at least one open-loop: the polygon is infinite
581 setSize(Double.POSITIVE_INFINITY);
582 setBarycenter(Vector2D.NaN);
583 } else {
584 // all loops are closed, we compute some integrals around the shape
585
586 double sum = 0;
587 double sumX = 0;
588 double sumY = 0;
589
590 for (Vector2D[] loop : v) {
591 double x1 = loop[loop.length - 1].getX();
592 double y1 = loop[loop.length - 1].getY();
593 for (final Vector2D point : loop) {
594 final double x0 = x1;
595 final double y0 = y1;
596 x1 = point.getX();
597 y1 = point.getY();
598 final double factor = x0 * y1 - y0 * x1;
599 sum += factor;
600 sumX += factor * (x0 + x1);
601 sumY += factor * (y0 + y1);
602 }
603 }
604
605 if (sum < 0) {
606 // the polygon as a finite outside surrounded by an infinite inside
607 setSize(Double.POSITIVE_INFINITY);
608 setBarycenter(Vector2D.NaN);
609 } else {
610 setSize(sum / 2);
611 setBarycenter(new Vector2D(sumX / (3 * sum), sumY / (3 * sum)));
612 }
613
614 }
615
616 }
617
618 /** Get the vertices of the polygon.
619 * <p>The polygon boundary can be represented as an array of loops,
620 * each loop being itself an array of vertices.</p>
621 * <p>In order to identify open loops which start and end by
622 * infinite edges, the open loops arrays start with a null point. In
623 * this case, the first non null point and the last point of the
624 * array do not represent real vertices, they are dummy points
625 * intended only to get the direction of the first and last edge. An
626 * open loop consisting of a single infinite line will therefore be
627 * represented by a three elements array with one null point
628 * followed by two dummy points. The open loops are always the first
629 * ones in the loops array.</p>
630 * <p>If the polygon has no boundary at all, a zero length loop
631 * array will be returned.</p>
632 * <p>All line segments in the various loops have the inside of the
633 * region on their left side and the outside on their right side
634 * when moving in the underlying line direction. This means that
635 * closed loops surrounding finite areas obey the direct
636 * trigonometric orientation.</p>
637 * @return vertices of the polygon, organized as oriented boundary
638 * loops with the open loops first (the returned value is guaranteed
639 * to be non-null)
640 */
641 public Vector2D[][] getVertices() {
642 if (vertices == null) {
643 if (getTree(false).getCut() == null) {
644 vertices = new Vector2D[0][];
645 } else {
646
647 // build the unconnected segments
648 final SegmentsBuilder visitor = new SegmentsBuilder(getTolerance());
649 getTree(true).visit(visitor);
650 final List<ConnectableSegment> segments = visitor.getSegments();
651
652 // connect all segments, using topological criteria first
653 // and using Euclidean distance only as a last resort
654 int pending = segments.size();
655 pending -= naturalFollowerConnections(segments);
656 if (pending > 0) {
657 pending -= splitEdgeConnections(segments);
658 }
659 if (pending > 0) {
660 pending -= closeVerticesConnections(segments);
661 }
662
663 // create the segment loops
664 final ArrayList<List<Segment>> loops = new ArrayList<>();
665 for (ConnectableSegment s = getUnprocessed(segments); s != null; s = getUnprocessed(segments)) {
666 final List<Segment> loop = followLoop(s);
667 if (loop != null && !loop.isEmpty()) {
668 if (loop.get(0).getStart() == null) {
669 // this is an open loop, we put it on the front
670 loops.add(0, loop);
671 --pending;
672 } else {
673 // this is a closed loop, we put it on the back
674 loops.add(loop);
675 }
676 }
677 }
678
679 if (pending != 0) {
680 // this should not happen
681 throw new MathIllegalStateException(LocalizedGeometryFormats.OUTLINE_BOUNDARY_LOOP_OPEN);
682 }
683
684 // transform the loops in an array of arrays of points
685 vertices = new Vector2D[loops.size()][];
686 int i = 0;
687
688 for (final List<Segment> loop : loops) {
689 if (loop.size() < 2) {
690 // single infinite line
691 final Line line = loop.get(0).getLine();
692 vertices[i++] = new Vector2D[] {
693 null,
694 line.toSpace(new Vector1D(-Float.MAX_VALUE)),
695 line.toSpace(new Vector1D(+Float.MAX_VALUE))
696 };
697 } else if (loop.get(0).getStart() == null) {
698 // open loop with at least one real point
699 final Vector2D[] array = new Vector2D[loop.size() + 3];
700 int j = 0;
701 for (Segment segment : loop) {
702
703 if (j == 0) {
704 // null point and first dummy point
705 double x = segment.getLine().toSubSpace(segment.getEnd()).getX();
706 x -= FastMath.max(1.0, FastMath.abs(x / 2));
707 array[j++] = null;
708 array[j++] = segment.getLine().toSpace(new Vector1D(x));
709 } else {
710
711 if (j < (array.length - 2)) {
712 // current point
713 array[j++] = segment.getStart();
714 }
715
716 if (j == (array.length - 2)) {
717 // last dummy point
718 double x = segment.getLine().toSubSpace(segment.getStart()).getX();
719 x += FastMath.max(1.0, FastMath.abs(x / 2));
720 array[j++] = segment.getLine().toSpace(new Vector1D(x));
721 }
722 }
723
724 }
725 vertices[i++] = array;
726 } else {
727 final Vector2D[] array = new Vector2D[loop.size()];
728 int j = 0;
729 for (Segment segment : loop) {
730 array[j++] = segment.getStart();
731 }
732 vertices[i++] = array;
733 }
734 }
735
736 }
737 }
738
739 return vertices.clone();
740
741 }
742
743 /** Connect the segments using only natural follower information.
744 * @param segments segments complete segments list
745 * @return number of connections performed
746 */
747 private int naturalFollowerConnections(final List<ConnectableSegment> segments) {
748 int connected = 0;
749 for (final ConnectableSegment segment : segments) {
750 if (segment.getNext() == null) {
751 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node = segment.getNode();
752 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> end = segment.getEndNode();
753 for (final ConnectableSegment candidateNext : segments) {
754 if (candidateNext.getPrevious() == null &&
755 candidateNext.getNode() == end &&
756 candidateNext.getStartNode() == node) {
757 // connect the two segments
758 segment.setNext(candidateNext);
759 candidateNext.setPrevious(segment);
760 ++connected;
761 break;
762 }
763 }
764 }
765 }
766 return connected;
767 }
768
769 /** Connect the segments resulting from a line splitting a straight edge.
770 * @param segments segments complete segments list
771 * @return number of connections performed
772 */
773 private int splitEdgeConnections(final List<ConnectableSegment> segments) {
774 int connected = 0;
775 for (final ConnectableSegment segment : segments) {
776 if (segment.getNext() == null) {
777 final Line hyperplane = segment.getNode().getCut().getHyperplane();
778 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> end = segment.getEndNode();
779 for (final ConnectableSegment candidateNext : segments) {
780 if (candidateNext.getPrevious() == null &&
781 candidateNext.getNode().getCut().getHyperplane() == hyperplane &&
782 candidateNext.getStartNode() == end) {
783 // connect the two segments
784 segment.setNext(candidateNext);
785 candidateNext.setPrevious(segment);
786 ++connected;
787 break;
788 }
789 }
790 }
791 }
792 return connected;
793 }
794
795 /** Connect the segments using Euclidean distance.
796 * <p>
797 * This connection heuristic should be used last, as it relies
798 * only on a fuzzy distance criterion.
799 * </p>
800 * @param segments segments complete segments list
801 * @return number of connections performed
802 */
803 private int closeVerticesConnections(final List<ConnectableSegment> segments) {
804 int connected = 0;
805 for (final ConnectableSegment segment : segments) {
806 if (segment.getNext() == null && segment.getEnd() != null) {
807 final Vector2D end = segment.getEnd();
808 ConnectableSegment selectedNext = null;
809 double min = Double.POSITIVE_INFINITY;
810 for (final ConnectableSegment candidateNext : segments) {
811 if (candidateNext.getPrevious() == null && candidateNext.getStart() != null) {
812 final double distance = Vector2D.distance(end, candidateNext.getStart());
813 if (distance < min) {
814 selectedNext = candidateNext;
815 min = distance;
816 }
817 }
818 }
819 if (min <= getTolerance()) {
820 // connect the two segments
821 segment.setNext(selectedNext);
822 selectedNext.setPrevious(segment);
823 ++connected;
824 }
825 }
826 }
827 return connected;
828 }
829
830 /** Get first unprocessed segment from a list.
831 * @param segments segments list
832 * @return first segment that has not been processed yet
833 * or null if all segments have been processed
834 */
835 private ConnectableSegment getUnprocessed(final List<ConnectableSegment> segments) {
836 for (final ConnectableSegment segment : segments) {
837 if (!segment.isProcessed()) {
838 return segment;
839 }
840 }
841 return null;
842 }
843
844 /** Build the loop containing a segment.
845 * <p>
846 * The segment put in the loop will be marked as processed.
847 * </p>
848 * @param defining segment used to define the loop
849 * @return loop containing the segment (may be null if the loop is a
850 * degenerated infinitely thin 2 points loop)
851 */
852 private List<Segment> followLoop(final ConnectableSegment defining) {
853
854 final List<Segment> loop = new ArrayList<>();
855 loop.add(defining);
856 defining.setProcessed(true);
857
858 // add segments in connection order
859 ConnectableSegment next = defining.getNext();
860 while (next != defining && next != null) {
861 loop.add(next);
862 next.setProcessed(true);
863 next = next.getNext();
864 }
865
866 if (next == null) {
867 // the loop is open and we have found its end,
868 // we need to find its start too
869 ConnectableSegment previous = defining.getPrevious();
870 while (previous != null) {
871 loop.add(0, previous);
872 previous.setProcessed(true);
873 previous = previous.getPrevious();
874 }
875 }
876
877 // filter out spurious vertices
878 filterSpuriousVertices(loop);
879
880 if (loop.size() == 2 && loop.get(0).getStart() != null) {
881 // this is a degenerated infinitely thin closed loop, we simply ignore it
882 return null; // NOPMD
883 } else {
884 return loop;
885 }
886
887 }
888
889 /** Filter out spurious vertices on straight lines (at machine precision).
890 * @param loop segments loop to filter (will be modified in-place)
891 */
892 private void filterSpuriousVertices(final List<Segment> loop) {
893 for (int i = 0; i < loop.size(); ++i) {
894 final Segment previous = loop.get(i);
895 int j = (i + 1) % loop.size();
896 final Segment next = loop.get(j);
897 if (next != null &&
898 Precision.equals(previous.getLine().getAngle(), next.getLine().getAngle(), Precision.EPSILON)) {
899 // the vertex between the two edges is a spurious one
900 // replace the two segments by a single one
901 loop.set(j, new Segment(previous.getStart(), next.getEnd(), previous.getLine()));
902 loop.remove(i--);
903 }
904 }
905 }
906
907 /** Private extension of Segment allowing connection. */
908 private static class ConnectableSegment extends Segment {
909
910 /** Node containing segment. */
911 private final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node;
912
913 /** Node whose intersection with current node defines start point. */
914 private final BSPTree<Euclidean2D, Vector2D, Line, SubLine> startNode;
915
916 /** Node whose intersection with current node defines end point. */
917 private final BSPTree<Euclidean2D, Vector2D, Line, SubLine> endNode;
918
919 /** Previous segment. */
920 private ConnectableSegment previous;
921
922 /** Next segment. */
923 private ConnectableSegment next;
924
925 /** Indicator for completely processed segments. */
926 private boolean processed;
927
928 /** Build a segment.
929 * @param start start point of the segment
930 * @param end end point of the segment
931 * @param line line containing the segment
932 * @param node node containing the segment
933 * @param startNode node whose intersection with current node defines start point
934 * @param endNode node whose intersection with current node defines end point
935 */
936 ConnectableSegment(final Vector2D start, final Vector2D end, final Line line,
937 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node,
938 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> startNode,
939 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> endNode) {
940 super(start, end, line);
941 this.node = node;
942 this.startNode = startNode;
943 this.endNode = endNode;
944 this.previous = null;
945 this.next = null;
946 this.processed = false;
947 }
948
949 /** Get the node containing segment.
950 * @return node containing segment
951 */
952 public BSPTree<Euclidean2D, Vector2D, Line, SubLine> getNode() {
953 return node;
954 }
955
956 /** Get the node whose intersection with current node defines start point.
957 * @return node whose intersection with current node defines start point
958 */
959 public BSPTree<Euclidean2D, Vector2D, Line, SubLine> getStartNode() {
960 return startNode;
961 }
962
963 /** Get the node whose intersection with current node defines end point.
964 * @return node whose intersection with current node defines end point
965 */
966 public BSPTree<Euclidean2D, Vector2D, Line, SubLine> getEndNode() {
967 return endNode;
968 }
969
970 /** Get the previous segment.
971 * @return previous segment
972 */
973 public ConnectableSegment getPrevious() {
974 return previous;
975 }
976
977 /** Set the previous segment.
978 * @param previous previous segment
979 */
980 public void setPrevious(final ConnectableSegment previous) {
981 this.previous = previous;
982 }
983
984 /** Get the next segment.
985 * @return next segment
986 */
987 public ConnectableSegment getNext() {
988 return next;
989 }
990
991 /** Set the next segment.
992 * @param next previous segment
993 */
994 public void setNext(final ConnectableSegment next) {
995 this.next = next;
996 }
997
998 /** Set the processed flag.
999 * @param processed processed flag to set
1000 */
1001 public void setProcessed(final boolean processed) {
1002 this.processed = processed;
1003 }
1004
1005 /** Check if the segment has been processed.
1006 * @return true if the segment has been processed
1007 */
1008 public boolean isProcessed() {
1009 return processed;
1010 }
1011
1012 }
1013
1014 /** Visitor building segments. */
1015 private static class SegmentsBuilder implements BSPTreeVisitor<Euclidean2D, Vector2D, Line, SubLine> {
1016
1017 /** Tolerance for close nodes connection. */
1018 private final double tolerance;
1019
1020 /** Built segments. */
1021 private final List<ConnectableSegment> segments;
1022
1023 /** Simple constructor.
1024 * @param tolerance tolerance for close nodes connection
1025 */
1026 SegmentsBuilder(final double tolerance) {
1027 this.tolerance = tolerance;
1028 this.segments = new ArrayList<>();
1029 }
1030
1031 /** {@inheritDoc} */
1032 @Override
1033 public Order visitOrder(final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node) {
1034 return Order.MINUS_SUB_PLUS;
1035 }
1036
1037 /** {@inheritDoc} */
1038 @Override
1039 public void visitInternalNode(final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node) {
1040 @SuppressWarnings("unchecked")
1041 final BoundaryAttribute<Euclidean2D, Vector2D, Line, SubLine> attribute =
1042 (BoundaryAttribute<Euclidean2D, Vector2D, Line, SubLine>) node.getAttribute();
1043 final Iterable<BSPTree<Euclidean2D, Vector2D, Line, SubLine>> splitters = attribute.getSplitters();
1044 if (attribute.getPlusOutside() != null) {
1045 addContribution(attribute.getPlusOutside(), node, splitters, false);
1046 }
1047 if (attribute.getPlusInside() != null) {
1048 addContribution(attribute.getPlusInside(), node, splitters, true);
1049 }
1050 }
1051
1052 /** {@inheritDoc} */
1053 @Override
1054 public void visitLeafNode(final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node) {
1055 }
1056
1057 /** Add the contribution of a boundary facet.
1058 * @param sub boundary facet
1059 * @param node node containing segment
1060 * @param splitters splitters for the boundary facet
1061 * @param reversed if true, the facet has the inside on its plus side
1062 */
1063 private void addContribution(final SubLine sub,
1064 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node,
1065 final Iterable<BSPTree<Euclidean2D, Vector2D, Line, SubLine>> splitters,
1066 final boolean reversed) {
1067 final List<Interval> intervals = ((IntervalsSet) sub.getRemainingRegion()).asList();
1068 for (final Interval i : intervals) {
1069
1070 // find the 2D points
1071 final Vector2D startV = Double.isInfinite(i.getInf()) ?
1072 null : sub.getHyperplane().toSpace(new Vector1D(i.getInf()));
1073 final Vector2D endV = Double.isInfinite(i.getSup()) ?
1074 null : sub.getHyperplane().toSpace(new Vector1D(i.getSup()));
1075
1076 // recover the connectivity information
1077 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> startN = selectClosest(startV, splitters);
1078 final BSPTree<Euclidean2D, Vector2D, Line, SubLine> endN = selectClosest(endV, splitters);
1079
1080 if (reversed) {
1081 segments.add(new ConnectableSegment(endV, startV, sub.getHyperplane().getReverse(),
1082 node, endN, startN));
1083 } else {
1084 segments.add(new ConnectableSegment(startV, endV, sub.getHyperplane(),
1085 node, startN, endN));
1086 }
1087
1088 }
1089 }
1090
1091 /** Select the node whose cut sub-hyperplane is closest to specified point.
1092 * @param point reference point
1093 * @param candidates candidate nodes
1094 * @return node closest to point, or null if no node is closer than tolerance
1095 */
1096 private BSPTree<Euclidean2D, Vector2D, Line, SubLine>
1097 selectClosest(final Vector2D point, final Iterable<BSPTree<Euclidean2D, Vector2D, Line, SubLine>> candidates) {
1098
1099 if (point == null) {
1100 return null;
1101 }
1102
1103 BSPTree<Euclidean2D, Vector2D, Line, SubLine> selected = null;
1104
1105 double min = Double.POSITIVE_INFINITY;
1106 for (final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node : candidates) {
1107 final double distance = FastMath.abs(node.getCut().getHyperplane().getOffset(point));
1108 if (distance < min) {
1109 selected = node;
1110 min = distance;
1111 }
1112 }
1113
1114 return min <= tolerance ? selected : null;
1115
1116 }
1117
1118 /** Get the segments.
1119 * @return built segments
1120 */
1121 public List<ConnectableSegment> getSegments() {
1122 return segments;
1123 }
1124
1125 }
1126
1127 }