PolygonsSet.java

  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.  */

  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;

  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;

  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;

  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> {

  53.     /** Vertices organized as boundary loops. */
  54.     private Vector2D[][] vertices;

  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.     }

  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.     }

  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.     }

  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.     }

  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.      * &pi; 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.     }

  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.     }

  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) {

  204.         final int n = vertices.length;
  205.         if (n == 0) {
  206.             // the tree represents the whole space
  207.             return new BSPTree<>(Boolean.TRUE);
  208.         }

  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.         }

  218.         // build the edges
  219.         List<Edge> edges = new ArrayList<>(n);
  220.         for (int i = 0; i < n; ++i) {

  222.             // get the endpoints of the edge
  223.             final Vertex start = vArray[i];
  224.             final Vertex end   = vArray[(i + 1) % n];

  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);

  230.             // create the edge and store it
  231.             edges.add(new Edge(start, end, line));

  233.         }

  235.         // build the tree top-down
  236.         final BSPTree<Euclidean2D, Vector2D, Line, SubLine> tree = new BSPTree<>();
  237.         insertEdges(hyperplaneThickness, tree, edges);

  239.         return tree;

  241.     }

  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) {

  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.         }

  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();

  279.         bindings.get(start).add(newLine);
  280.         bindings.get(end).add(newLine);

  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.         }

  290.         return newLine;

  292.     }

  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) {

  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.         }

  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.         }

  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.         }

  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.         }

  390.     }

  392.     /** Internal class for holding vertices while they are processed to build a BSP tree. */
  393.     private static class Vertex {

  395.         /** Vertex location. */
  396.         private final Vector2D location;

  398.         /** Incoming edge. */
  399.         private Edge incoming;

  401.         /** Outgoing edge. */
  402.         private Edge outgoing;

  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.         }

  413.         /** Get Vertex location.
  414.          * @return vertex location
  415.          */
  416.         public Vector2D getLocation() {
  417.             return location;
  418.         }

  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.         }

  431.         /** Get incoming edge.
  432.          * @return incoming edge
  433.          */
  434.         public Edge getIncoming() {
  435.             return incoming;
  436.         }

  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.         }

  449.         /** Get outgoing edge.
  450.          * @return outgoing edge
  451.          */
  452.         public Edge getOutgoing() {
  453.             return outgoing;
  454.         }

  456.     }

  458.     /** Internal class for holding edges while they are processed to build a BSP tree. */
  459.     private static class Edge {

  461.         /** Start vertex. */
  462.         private final Vertex start;

  464.         /** End vertex. */
  465.         private final Vertex end;

  467.         /** Line supporting the edge. */
  468.         private final Line line;

  470.         /** Node whose cut hyperplane contains this edge. */
  471.         private BSPTree<Euclidean2D, Vector2D, Line, SubLine> node;

  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) {

  480.             this.start = start;
  481.             this.end   = end;
  482.             this.line  = line;
  483.             this.node  = null;

  485.             // connect the vertices back to the edge
  486.             start.setOutgoing(this);
  487.             end.setIncoming(this);

  489.         }

  491.         /** Get start vertex.
  492.          * @return start vertex
  493.          */
  494.         public Vertex getStart() {
  495.             return start;
  496.         }

  498.         /** Get end vertex.
  499.          * @return end vertex
  500.          */
  501.         public Vertex getEnd() {
  502.             return end;
  503.         }

  505.         /** Get the line supporting this edge.
  506.          * @return line supporting this edge
  507.          */
  508.         public Line getLine() {
  509.             return line;
  510.         }

  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.         }

  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.         }

  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.         }

  545.     }

  547.     /** {@inheritDoc} */
  548.     @Override
  549.     public PolygonsSet buildNew(final BSPTree<Euclidean2D, Vector2D, Line, SubLine> tree) {
  550.         return new PolygonsSet(tree, getTolerance());
  551.     }

  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.     }

  563.     /** {@inheritDoc} */
  564.     @Override
  565.     protected void computeGeometricalProperties() {

  567.         final Vector2D[][] v = getVertices();

  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

  586.             double sum  = 0;
  587.             double sumX = 0;
  588.             double sumY = 0;

  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.             }

  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.             }

  614.         }

  616.     }

  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 {

  647.                 // build the unconnected segments
  648.                 final SegmentsBuilder visitor = new SegmentsBuilder(getTolerance());
  649.                 getTree(true).visit(visitor);
  650.                 final List<ConnectableSegment> segments = visitor.getSegments();

  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.                 }

  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.                 }

  679.                 if (pending != 0) {
  680.                     // this should not happen
  681.                     throw new MathIllegalStateException(LocalizedGeometryFormats.OUTLINE_BOUNDARY_LOOP_OPEN);
  682.                 }

  684.                 // transform the loops in an array of arrays of points
  685.                 vertices = new Vector2D[loops.size()][];
  686.                 int i = 0;

  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) {

  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 {

  711.                                 if (j < (array.length - 2)) {
  712.                                     // current point
  713.                                     array[j++] = segment.getStart();
  714.                                 }

  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.                             }

  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.                 }

  736.             }
  737.         }

  739.         return vertices.clone();

  741.     }

  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.     }

  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.     }

  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.     }

  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.     }

  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) {

  854.         final List<Segment> loop = new ArrayList<>();
  855.         loop.add(defining);
  856.         defining.setProcessed(true);

  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.         }

  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.         }

  877.         // filter out spurious vertices
  878.         filterSpuriousVertices(loop);

  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.         }

  887.     }

  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.     }

  907.     /** Private extension of Segment allowing connection. */
  908.     private static class ConnectableSegment extends Segment {

  910.         /** Node containing segment. */
  911.         private final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node;

  913.         /** Node whose intersection with current node defines start point. */
  914.         private final BSPTree<Euclidean2D, Vector2D, Line, SubLine> startNode;

  916.         /** Node whose intersection with current node defines end point. */
  917.         private final BSPTree<Euclidean2D, Vector2D, Line, SubLine> endNode;

  919.         /** Previous segment. */
  920.         private ConnectableSegment previous;

  922.         /** Next segment. */
  923.         private ConnectableSegment next;

  925.         /** Indicator for completely processed segments. */
  926.         private boolean processed;

  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.         }

  949.         /** Get the node containing segment.
  950.          * @return node containing segment
  951.          */
  952.         public BSPTree<Euclidean2D, Vector2D, Line, SubLine> getNode() {
  953.             return node;
  954.         }

  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.         }

  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.         }

  970.         /** Get the previous segment.
  971.          * @return previous segment
  972.          */
  973.         public ConnectableSegment getPrevious() {
  974.             return previous;
  975.         }

  977.         /** Set the previous segment.
  978.          * @param previous previous segment
  979.          */
  980.         public void setPrevious(final ConnectableSegment previous) {
  981.             this.previous = previous;
  982.         }

  984.         /** Get the next segment.
  985.          * @return next segment
  986.          */
  987.         public ConnectableSegment getNext() {
  988.             return next;
  989.         }

  991.         /** Set the next segment.
  992.          * @param next previous segment
  993.          */
  994.         public void setNext(final ConnectableSegment next) {
  995.             this.next = next;
  996.         }

  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.         }

  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.         }

  1012.     }

  1014.     /** Visitor building segments. */
  1015.     private static class SegmentsBuilder implements BSPTreeVisitor<Euclidean2D, Vector2D, Line, SubLine> {

  1017.         /** Tolerance for close nodes connection. */
  1018.         private final double tolerance;

  1020.         /** Built segments. */
  1021.         private final List<ConnectableSegment> segments;

  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.         }

  1031.         /** {@inheritDoc} */
  1032.         @Override
  1033.         public Order visitOrder(final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node) {
  1034.             return Order.MINUS_SUB_PLUS;
  1035.         }

  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.         }

  1052.         /** {@inheritDoc} */
  1053.         @Override
  1054.         public void visitLeafNode(final BSPTree<Euclidean2D, Vector2D, Line, SubLine> node) {
  1055.         }

  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) {

  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()));

  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);

  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.                 }

  1088.             }
  1089.         }

  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) {

  1099.             if (point == null) {
  1100.                 return null;
  1101.             }

  1103.             BSPTree<Euclidean2D, Vector2D, Line, SubLine> selected = null;

  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.             }

  1114.             return min <= tolerance ? selected : null;

  1116.         }

  1118.         /** Get the segments.
  1119.          * @return built segments
  1120.          */
  1121.         public List<ConnectableSegment> getSegments() {
  1122.             return segments;
  1123.         }

  1125.     }

  1127. }
Created with JaCoCo 0.8.12.202403310830