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