/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      https://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  /*
   * This is not the original file distributed by the Apache Software Foundation
   * It has been modified by the Hipparchus project
   */
  package org.hipparchus.geometry.euclidean.twod;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.IdentityHashMap;
  import java.util.List;
  import java.util.Map;
  
  import org.hipparchus.geometry.Point;
  import org.hipparchus.geometry.euclidean.oned.Euclidean1D;
  import org.hipparchus.geometry.euclidean.oned.Interval;
  import org.hipparchus.geometry.euclidean.oned.IntervalsSet;
  import org.hipparchus.geometry.euclidean.oned.Vector1D;
  import org.hipparchus.geometry.partitioning.AbstractRegion;
  import org.hipparchus.geometry.partitioning.AbstractSubHyperplane;
  import org.hipparchus.geometry.partitioning.BSPTree;
  import org.hipparchus.geometry.partitioning.BSPTreeVisitor;
  import org.hipparchus.geometry.partitioning.BoundaryAttribute;
  import org.hipparchus.geometry.partitioning.Hyperplane;
  import org.hipparchus.geometry.partitioning.Side;
  import org.hipparchus.geometry.partitioning.SubHyperplane;
  import org.hipparchus.util.FastMath;
  import org.hipparchus.util.Precision;
  
  /** This class represents a 2D region: a set of polygons.
   */
  public class PolygonsSet extends AbstractRegion<Euclidean2D, Euclidean1D> {
  
      /** Vertices organized as boundary loops. */
      private Vector2D[][] vertices;
  
      /** Build a polygons set representing the whole plane.
       * @param tolerance tolerance below which points are considered identical
       */
      public PolygonsSet(final double tolerance) {
          super(tolerance);
      }
  
      /** Build a polygons set from a BSP tree.
       * <p>The leaf nodes of the BSP tree <em>must</em> have a
       * {@code Boolean} attribute representing the inside status of
       * the corresponding cell (true for inside cells, false for outside
       * cells). In order to avoid building too many small objects, it is
       * recommended to use the predefined constants
       * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
       * <p>
       * This constructor is aimed at expert use, as building the tree may
       * be a difficult task. It is not intended for general use and for
       * performances reasons does not check thoroughly its input, as this would
       * require walking the full tree each time. Failing to provide a tree with
       * the proper attributes, <em>will</em> therefore generate problems like
       * {@link NullPointerException} or {@link ClassCastException} only later on.
       * This limitation is known and explains why this constructor is for expert
       * use only. The caller does have the responsibility to provided correct arguments.
       * </p>
       * @param tree inside/outside BSP tree representing the region
       * @param tolerance tolerance below which points are considered identical
       */
      public PolygonsSet(final BSPTree<Euclidean2D> tree, final double tolerance) {
          super(tree, tolerance);
      }
  
      /** Build a polygons set from a Boundary REPresentation (B-rep).
       * <p>The boundary is provided as a collection of {@link
       * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
       * interior part of the region on its minus side and the exterior on
       * its plus side.</p>
       * <p>The boundary elements can be in any order, and can form
       * several non-connected sets (like for example polygons with holes
       * or a set of disjoint polygons considered as a whole). In
       * fact, the elements do not even need to be connected together
       * (their topological connections are not used here). However, if the
       * boundary does not really separate an inside open from an outside
       * open (open having here its topological meaning), then subsequent
       * calls to the {@link
       * org.hipparchus.geometry.partitioning.Region#checkPoint(org.hipparchus.geometry.Point)
       * checkPoint} method will not be meaningful anymore.</p>
       * <p>If the boundary is empty, the region will represent the whole
      * space.</p>
      * @param boundary collection of boundary elements, as a
      * collection of {@link SubHyperplane SubHyperplane} objects
      * @param tolerance tolerance below which points are considered identical
      */
     public PolygonsSet(final Collection<SubHyperplane<Euclidean2D>> boundary, final double tolerance) {
         super(boundary, tolerance);
     }
 
     /** Build a parallellepipedic box.
      * @param xMin low bound along the x direction
      * @param xMax high bound along the x direction
      * @param yMin low bound along the y direction
      * @param yMax high bound along the y direction
      * @param tolerance tolerance below which points are considered identical
      */
     public PolygonsSet(final double xMin, final double xMax,
                        final double yMin, final double yMax,
                        final double tolerance) {
         super(boxBoundary(xMin, xMax, yMin, yMax, tolerance), tolerance);
     }
 
     /** Build a polygon from a simple list of vertices.
      * <p>The boundary is provided as a list of points considering to
      * represent the vertices of a simple loop. The interior part of the
      * region is on the left side of this path and the exterior is on its
      * right side.</p>
      * <p>This constructor does not handle polygons with a boundary
      * forming several disconnected paths (such as polygons with holes).</p>
      * <p>For cases where this simple constructor applies, it is expected to
      * be numerically more robust than the {@link #PolygonsSet(Collection,double) general
      * constructor} using {@link SubHyperplane subhyperplanes}.</p>
      * <p>If the list is empty, the region will represent the whole
      * space.</p>
      * <p>
      * Polygons with thin pikes or dents are inherently difficult to handle because
      * they involve lines with almost opposite directions at some vertices. Polygons
      * whose vertices come from some physical measurement with noise are also
      * difficult because an edge that should be straight may be broken in lots of
      * different pieces with almost equal directions. In both cases, computing the
      * lines intersections is not numerically robust due to the almost 0 or almost
      * &pi; angle. Such cases need to carefully adjust the {@code hyperplaneThickness}
      * parameter. A too small value would often lead to completely wrong polygons
      * with large area wrongly identified as inside or outside. Large values are
      * often much safer. As a rule of thumb, a value slightly below the size of the
      * most accurate detail needed is a good value for the {@code hyperplaneThickness}
      * parameter.
      * </p>
      * @param hyperplaneThickness tolerance below which points are considered to
      * belong to the hyperplane (which is therefore more a slab)
      * @param vertices vertices of the simple loop boundary
      */
     public PolygonsSet(final double hyperplaneThickness, final Vector2D ... vertices) {
         super(verticesToTree(hyperplaneThickness, vertices), hyperplaneThickness);
     }
 
     /** Create a list of hyperplanes representing the boundary of a box.
      * @param xMin low bound along the x direction
      * @param xMax high bound along the x direction
      * @param yMin low bound along the y direction
      * @param yMax high bound along the y direction
      * @param tolerance tolerance below which points are considered identical
      * @return boundary of the box
      */
     private static Line[] boxBoundary(final double xMin, final double xMax,
                                       final double yMin, final double yMax,
                                       final double tolerance) {
         if ((xMin >= xMax - tolerance) || (yMin >= yMax - tolerance)) {
             // too thin box, build an empty polygons set
             return null; // NOPMD
         }
         final Vector2D minMin = new Vector2D(xMin, yMin);
         final Vector2D minMax = new Vector2D(xMin, yMax);
         final Vector2D maxMin = new Vector2D(xMax, yMin);
         final Vector2D maxMax = new Vector2D(xMax, yMax);
         return new Line[] {
             new Line(minMin, maxMin, tolerance),
             new Line(maxMin, maxMax, tolerance),
             new Line(maxMax, minMax, tolerance),
             new Line(minMax, minMin, tolerance)
         };
     }
 
     /** Build the BSP tree of a polygons set from a simple list of vertices.
      * <p>The boundary is provided as a list of points considering to
      * represent the vertices of a simple loop. The interior part of the
      * region is on the left side of this path and the exterior is on its
      * right side.</p>
      * <p>This constructor does not handle polygons with a boundary
      * forming several disconnected paths (such as polygons with holes).</p>
      * <p>For cases where this simple constructor applies, it is expected to
      * be numerically more robust than the {@link #PolygonsSet(Collection,double) general
      * constructor} using {@link SubHyperplane subhyperplanes}.</p>
      * @param hyperplaneThickness tolerance below which points are consider to
      * belong to the hyperplane (which is therefore more a slab)
      * @param vertices vertices of the simple loop boundary
      * @return the BSP tree of the input vertices
      */
     private static BSPTree<Euclidean2D> verticesToTree(final double hyperplaneThickness,
                                                        final Vector2D ... vertices) {
 
         final int n = vertices.length;
         if (n == 0) {
             // the tree represents the whole space
             return new BSPTree<Euclidean2D>(Boolean.TRUE);
         }
 
         // build the vertices
         final Vertex[] vArray = new Vertex[n];
         final Map<Vertex, List<Line>> bindings = new IdentityHashMap<>(n);
         for (int i = 0; i < n; ++i) {
             vArray[i] = new Vertex(vertices[i]);
             bindings.put(vArray[i], new ArrayList<>());
         }
 
         // build the edges
         List<Edge> edges = new ArrayList<>(n);
         for (int i = 0; i < n; ++i) {
 
             // get the endpoints of the edge
             final Vertex start = vArray[i];
             final Vertex end   = vArray[(i + 1) % n];
 
             // get the line supporting the edge, taking care not to recreate it if it was
             // already created earlier due to another edge being aligned with the current one
             final Line line = supportingLine(start, end, vArray, bindings, hyperplaneThickness);
 
             // create the edge and store it
             edges.add(new Edge(start, end, line));
 
         }
 
         // build the tree top-down
         final BSPTree<Euclidean2D> tree = new BSPTree<>();
         insertEdges(hyperplaneThickness, tree, edges);
 
         return tree;
 
     }
 
     /** Get the supporting line for two vertices.
      * @param start start vertex of an edge being built
      * @param end end vertex of an edge being built
      * @param vArray array containing all vertices
      * @param bindings bindings between vertices and lines
      * @param hyperplaneThickness tolerance below which points are consider to
      * belong to the hyperplane (which is therefore more a slab)
      * @return line bound with both start and end and in the proper orientation
      */
     private static Line supportingLine(final Vertex start, final Vertex end,
                                        final Vertex[] vArray,
                                        final Map<Vertex, List<Line>> bindings,
                                        final double hyperplaneThickness) {
 
         Line toBeReversed = null;
         for (final Line line1 : bindings.get(start)) {
             for (final Line line2 : bindings.get(end)) {
                 if (line1 == line2) {
                     // we already know a line to which both vertices belong
                     final double xs = line1.toSubSpace(start.getLocation()).getX();
                     final double xe = line1.toSubSpace(end.getLocation()).getX();
                     if (xe >= xs) {
                         // the known line has the proper orientation
                         return line1;
                     } else {
                         toBeReversed = line1;
                     }
                 }
             }
         }
 
         // we need to create a new circle
         final Line newLine = (toBeReversed == null) ?
                              new Line(start.getLocation(), end.getLocation(), hyperplaneThickness) :
                              toBeReversed.getReverse();
 
         bindings.get(start).add(newLine);
         bindings.get(end).add(newLine);
 
         // check if another vertex also happens to be on this line
         for (final Vertex vertex : vArray) {
             if (vertex != start && vertex != end &&
                 FastMath.abs(newLine.getOffset(vertex.getLocation())) <= hyperplaneThickness) {
                 bindings.get(vertex).add(newLine);
             }
         }
 
         return newLine;
 
     }
 
     /** Recursively build a tree by inserting cut sub-hyperplanes.
      * @param hyperplaneThickness tolerance below which points are consider to
      * belong to the hyperplane (which is therefore more a slab)
      * @param node current tree node (it is a leaf node at the beginning
      * of the call)
      * @param edges list of edges to insert in the cell defined by this node
      * (excluding edges not belonging to the cell defined by this node)
      */
     private static void insertEdges(final double hyperplaneThickness,
                                     final BSPTree<Euclidean2D> node,
                                     final List<Edge> edges) {
 
         // find an edge with an hyperplane that can be inserted in the node
         int index = 0;
         Edge inserted =null;
         while (inserted == null && index < edges.size()) {
             inserted = edges.get(index++);
             if (inserted.getNode() == null) {
                 if (node.insertCut(inserted.getLine())) {
                     inserted.setNode(node);
                 } else {
                     inserted = null;
                 }
             } else {
                 inserted = null;
             }
         }
 
         if (inserted == null) {
             // no suitable edge was found, the node remains a leaf node
             // we need to set its inside/outside boolean indicator
             final BSPTree<Euclidean2D> parent = node.getParent();
             if (parent == null || node == parent.getMinus()) {
                 node.setAttribute(Boolean.TRUE);
             } else {
                 node.setAttribute(Boolean.FALSE);
             }
             return;
         }
 
         // we have split the node by inserting an edge as a cut sub-hyperplane
         // distribute the remaining edges in the two sub-trees
         final List<Edge> plusList  = new ArrayList<>();
         final List<Edge> minusList = new ArrayList<>();
         for (final Edge edge : edges) {
             if (edge != inserted) {
                 final double startOffset = inserted.getLine().getOffset((Point<Euclidean2D>) edge.getStart().getLocation());
                 final double endOffset   = inserted.getLine().getOffset((Point<Euclidean2D>) edge.getEnd().getLocation());
                 Side startSide = (FastMath.abs(startOffset) <= hyperplaneThickness) ?
                                  Side.HYPER : ((startOffset < 0) ? Side.MINUS : Side.PLUS);
                 Side endSide   = (FastMath.abs(endOffset) <= hyperplaneThickness) ?
                                  Side.HYPER : ((endOffset < 0) ? Side.MINUS : Side.PLUS);
                 switch (startSide) {
                     case PLUS:
                         if (endSide == Side.MINUS) {
                             // we need to insert a split point on the hyperplane
                             final Vertex splitPoint = edge.split(inserted.getLine());
                             minusList.add(splitPoint.getOutgoing());
                             plusList.add(splitPoint.getIncoming());
                         } else {
                             plusList.add(edge);
                         }
                         break;
                     case MINUS:
                         if (endSide == Side.PLUS) {
                             // we need to insert a split point on the hyperplane
                             final Vertex splitPoint = edge.split(inserted.getLine());
                             minusList.add(splitPoint.getIncoming());
                             plusList.add(splitPoint.getOutgoing());
                         } else {
                             minusList.add(edge);
                         }
                         break;
                     default:
                         if (endSide == Side.PLUS) {
                             plusList.add(edge);
                         } else if (endSide == Side.MINUS) {
                             minusList.add(edge);
                         }
                         break;
                 }
             }
         }
 
         // recurse through lower levels
         if (!plusList.isEmpty()) {
             insertEdges(hyperplaneThickness, node.getPlus(),  plusList);
         } else {
             node.getPlus().setAttribute(Boolean.FALSE);
         }
         if (!minusList.isEmpty()) {
             insertEdges(hyperplaneThickness, node.getMinus(), minusList);
         } else {
             node.getMinus().setAttribute(Boolean.TRUE);
         }
 
     }
 
     /** Internal class for holding vertices while they are processed to build a BSP tree. */
     private static class Vertex {
 
         /** Vertex location. */
         private final Vector2D location;
 
         /** Incoming edge. */
         private Edge incoming;
 
         /** Outgoing edge. */
         private Edge outgoing;
 
         /** Build a non-processed vertex not owned by any node yet.
          * @param location vertex location
          */
         Vertex(final Vector2D location) {
             this.location = location;
             this.incoming = null;
             this.outgoing = null;
         }
 
         /** Get Vertex location.
          * @return vertex location
          */
         public Vector2D getLocation() {
             return location;
         }
 
         /** Set incoming edge.
          * <p>
          * The line supporting the incoming edge is automatically bound
          * with the instance.
          * </p>
          * @param incoming incoming edge
          */
         public void setIncoming(final Edge incoming) {
             this.incoming = incoming;
         }
 
         /** Get incoming edge.
          * @return incoming edge
          */
         public Edge getIncoming() {
             return incoming;
         }
 
         /** Set outgoing edge.
          * <p>
          * The line supporting the outgoing edge is automatically bound
          * with the instance.
          * </p>
          * @param outgoing outgoing edge
          */
         public void setOutgoing(final Edge outgoing) {
             this.outgoing = outgoing;
         }
 
         /** Get outgoing edge.
          * @return outgoing edge
          */
         public Edge getOutgoing() {
             return outgoing;
         }
 
     }
 
     /** Internal class for holding edges while they are processed to build a BSP tree. */
     private static class Edge {
 
         /** Start vertex. */
         private final Vertex start;
 
         /** End vertex. */
         private final Vertex end;
 
         /** Line supporting the edge. */
         private final Line line;
 
         /** Node whose cut hyperplane contains this edge. */
         private BSPTree<Euclidean2D> node;
 
         /** Build an edge not contained in any node yet.
          * @param start start vertex
          * @param end end vertex
          * @param line line supporting the edge
          */
         Edge(final Vertex start, final Vertex end, final Line line) {
 
             this.start = start;
             this.end   = end;
             this.line  = line;
             this.node  = null;
 
             // connect the vertices back to the edge
             start.setOutgoing(this);
             end.setIncoming(this);
 
         }
 
         /** Get start vertex.
          * @return start vertex
          */
         public Vertex getStart() {
             return start;
         }
 
         /** Get end vertex.
          * @return end vertex
          */
         public Vertex getEnd() {
             return end;
         }
 
         /** Get the line supporting this edge.
          * @return line supporting this edge
          */
         public Line getLine() {
             return line;
         }
 
         /** Set the node whose cut hyperplane contains this edge.
          * @param node node whose cut hyperplane contains this edge
          */
         public void setNode(final BSPTree<Euclidean2D> node) {
             this.node = node;
         }
 
         /** Get the node whose cut hyperplane contains this edge.
          * @return node whose cut hyperplane contains this edge
          * (null if edge has not yet been inserted into the BSP tree)
          */
         public BSPTree<Euclidean2D> getNode() {
             return node;
         }
 
         /** Split the edge.
          * <p>
          * Once split, this edge is not referenced anymore by the vertices,
          * it is replaced by the two half-edges and an intermediate splitting
          * vertex is introduced to connect these two halves.
          * </p>
          * @param splitLine line splitting the edge in two halves
          * @return split vertex (its incoming and outgoing edges are the two halves)
          */
         public Vertex split(final Line splitLine) {
             final Vertex splitVertex = new Vertex(line.intersection(splitLine));
             final Edge startHalf = new Edge(start, splitVertex, line);
             final Edge endHalf   = new Edge(splitVertex, end, line);
             startHalf.node = node;
             endHalf.node   = node;
             return splitVertex;
         }
 
     }
 
     /** {@inheritDoc} */
     @Override
     public PolygonsSet buildNew(final BSPTree<Euclidean2D> tree) {
         return new PolygonsSet(tree, getTolerance());
     }
 
     /** {@inheritDoc} */
     @Override
     protected void computeGeometricalProperties() {
 
         final Vector2D[][] v = getVertices();
 
         if (v.length == 0) {
             final BSPTree<Euclidean2D> tree = getTree(false);
             if (tree.getCut() == null && (Boolean) tree.getAttribute()) {
                 // the instance covers the whole space
                 setSize(Double.POSITIVE_INFINITY);
                 setBarycenter((Point<Euclidean2D>) Vector2D.NaN);
             } else {
                 setSize(0);
                 setBarycenter((Point<Euclidean2D>) new Vector2D(0, 0));
             }
         } else if (v[0][0] == null) {
             // there is at least one open-loop: the polygon is infinite
             setSize(Double.POSITIVE_INFINITY);
             setBarycenter((Point<Euclidean2D>) Vector2D.NaN);
         } else {
             // all loops are closed, we compute some integrals around the shape
 
             double sum  = 0;
             double sumX = 0;
             double sumY = 0;
 
             for (Vector2D[] loop : v) {
                 double x1 = loop[loop.length - 1].getX();
                 double y1 = loop[loop.length - 1].getY();
                 for (final Vector2D point : loop) {
                     final double x0 = x1;
                     final double y0 = y1;
                     x1 = point.getX();
                     y1 = point.getY();
                     final double factor = x0 * y1 - y0 * x1;
                     sum  += factor;
                     sumX += factor * (x0 + x1);
                     sumY += factor * (y0 + y1);
                 }
             }
 
             if (sum < 0) {
                 // the polygon as a finite outside surrounded by an infinite inside
                 setSize(Double.POSITIVE_INFINITY);
                 setBarycenter((Point<Euclidean2D>) Vector2D.NaN);
             } else {
                 setSize(sum / 2);
                 setBarycenter((Point<Euclidean2D>) new Vector2D(sumX / (3 * sum), sumY / (3 * sum)));
             }
 
         }
 
     }
 
     /** Get the vertices of the polygon.
      * <p>The polygon boundary can be represented as an array of loops,
      * each loop being itself an array of vertices.</p>
      * <p>In order to identify open loops which start and end by
      * infinite edges, the open loops arrays start with a null point. In
      * this case, the first non null point and the last point of the
      * array do not represent real vertices, they are dummy points
      * intended only to get the direction of the first and last edge. An
      * open loop consisting of a single infinite line will therefore be
      * represented by a three elements array with one null point
      * followed by two dummy points. The open loops are always the first
      * ones in the loops array.</p>
      * <p>If the polygon has no boundary at all, a zero length loop
      * array will be returned.</p>
      * <p>All line segments in the various loops have the inside of the
      * region on their left side and the outside on their right side
      * when moving in the underlying line direction. This means that
      * closed loops surrounding finite areas obey the direct
      * trigonometric orientation.</p>
      * @return vertices of the polygon, organized as oriented boundary
      * loops with the open loops first (the returned value is guaranteed
      * to be non-null)
      */
     public Vector2D[][] getVertices() {
         if (vertices == null) {
             if (getTree(false).getCut() == null) {
                 vertices = new Vector2D[0][];
             } else {
 
                 // build the unconnected segments
                 final SegmentsBuilder visitor = new SegmentsBuilder(getTolerance());
                 getTree(true).visit(visitor);
                 final List<ConnectableSegment> segments = visitor.getSegments();
 
                 // connect all segments, using topological criteria first
                 // and using Euclidean distance only as a last resort
                 int pending = segments.size();
                 pending -= naturalFollowerConnections(segments);
                 if (pending > 0) {
                     pending -= splitEdgeConnections(segments);
                 }
                 if (pending > 0) {
                     closeVerticesConnections(segments);
                 }
 
                 // create the segment loops
                 final ArrayList<List<Segment>> loops = new ArrayList<>();
                 for (ConnectableSegment s = getUnprocessed(segments); s != null; s = getUnprocessed(segments)) {
                     final List<Segment> loop = followLoop(s);
                     if (loop != null) {
                         if (loop.get(0).getStart() == null) {
                             // this is an open loop, we put it on the front
                             loops.add(0, loop);
                         } else {
                             // this is a closed loop, we put it on the back
                             loops.add(loop);
                         }
                     }
                 }
 
                 // transform the loops in an array of arrays of points
                 vertices = new Vector2D[loops.size()][];
                 int i = 0;
 
                 for (final List<Segment> loop : loops) {
                     if (loop.size() < 2 ||
                         (loop.size() == 2 && loop.get(0).getStart() == null && loop.get(1).getEnd() == null)) {
                         // single infinite line
                         final Line line = loop.get(0).getLine();
                         vertices[i++] = new Vector2D[] {
                             null,
                             line.toSpace((Point<Euclidean1D>) new Vector1D(-Float.MAX_VALUE)),
                             line.toSpace((Point<Euclidean1D>) new Vector1D(+Float.MAX_VALUE))
                         };
                     } else if (loop.get(0).getStart() == null) {
                         // open loop with at least one real point
                         final Vector2D[] array = new Vector2D[loop.size() + 2];
                         int j = 0;
                         for (Segment segment : loop) {
 
                             if (j == 0) {
                                 // null point and first dummy point
                                 double x = segment.getLine().toSubSpace((Point<Euclidean2D>) segment.getEnd()).getX();
                                 x -= FastMath.max(1.0, FastMath.abs(x / 2));
                                 array[j++] = null;
                                 array[j++] = segment.getLine().toSpace((Point<Euclidean1D>) new Vector1D(x));
                             }
 
                             if (j < (array.length - 1)) {
                                 // current point
                                 array[j++] = segment.getEnd();
                             }
 
                             if (j == (array.length - 1)) {
                                 // last dummy point
                                 double x = segment.getLine().toSubSpace((Point<Euclidean2D>) segment.getStart()).getX();
                                 x += FastMath.max(1.0, FastMath.abs(x / 2));
                                 array[j++] = segment.getLine().toSpace((Point<Euclidean1D>) new Vector1D(x));
                             }
 
                         }
                         vertices[i++] = array;
                     } else {
                         final Vector2D[] array = new Vector2D[loop.size()];
                         int j = 0;
                         for (Segment segment : loop) {
                             array[j++] = segment.getStart();
                         }
                         vertices[i++] = array;
                     }
                 }
 
             }
         }
 
         return vertices.clone();
 
     }
 
     /** Connect the segments using only natural follower information.
      * @param segments segments complete segments list
      * @return number of connections performed
      */
     private int naturalFollowerConnections(final List<ConnectableSegment> segments) {
         int connected = 0;
         for (final ConnectableSegment segment : segments) {
             if (segment.getNext() == null) {
                 final BSPTree<Euclidean2D> node = segment.getNode();
                 final BSPTree<Euclidean2D> end  = segment.getEndNode();
                 for (final ConnectableSegment candidateNext : segments) {
                     if (candidateNext.getPrevious()  == null &&
                         candidateNext.getNode()      == end &&
                         candidateNext.getStartNode() == node) {
                         // connect the two segments
                         segment.setNext(candidateNext);
                         candidateNext.setPrevious(segment);
                         ++connected;
                         break;
                     }
                 }
             }
         }
         return connected;
     }
 
     /** Connect the segments resulting from a line splitting a straight edge.
      * @param segments segments complete segments list
      * @return number of connections performed
      */
     private int splitEdgeConnections(final List<ConnectableSegment> segments) {
         int connected = 0;
         for (final ConnectableSegment segment : segments) {
             if (segment.getNext() == null) {
                 final Hyperplane<Euclidean2D> hyperplane = segment.getNode().getCut().getHyperplane();
                 final BSPTree<Euclidean2D> end  = segment.getEndNode();
                 for (final ConnectableSegment candidateNext : segments) {
                     if (candidateNext.getPrevious()                      == null &&
                         candidateNext.getNode().getCut().getHyperplane() == hyperplane &&
                         candidateNext.getStartNode()                     == end) {
                         // connect the two segments
                         segment.setNext(candidateNext);
                         candidateNext.setPrevious(segment);
                         ++connected;
                         break;
                     }
                 }
             }
         }
         return connected;
     }
 
     /** Connect the segments using Euclidean distance.
      * <p>
      * This connection heuristic should be used last, as it relies
      * only on a fuzzy distance criterion.
      * </p>
      * @param segments segments complete segments list
      * @return number of connections performed
      */
     private int closeVerticesConnections(final List<ConnectableSegment> segments) {
         int connected = 0;
         for (final ConnectableSegment segment : segments) {
             if (segment.getNext() == null && segment.getEnd() != null) {
                 final Vector2D end = segment.getEnd();
                 ConnectableSegment selectedNext = null;
                 double min = Double.POSITIVE_INFINITY;
                 for (final ConnectableSegment candidateNext : segments) {
                     if (candidateNext.getPrevious() == null && candidateNext.getStart() != null) {
                         final double distance = Vector2D.distance(end, candidateNext.getStart());
                         if (distance < min) {
                             selectedNext = candidateNext;
                             min          = distance;
                         }
                     }
                 }
                 if (min <= getTolerance()) {
                     // connect the two segments
                     segment.setNext(selectedNext);
                     selectedNext.setPrevious(segment);
                     ++connected;
                 }
             }
         }
         return connected;
     }
 
     /** Get first unprocessed segment from a list.
      * @param segments segments list
      * @return first segment that has not been processed yet
      * or null if all segments have been processed
      */
     private ConnectableSegment getUnprocessed(final List<ConnectableSegment> segments) {
         for (final ConnectableSegment segment : segments) {
             if (!segment.isProcessed()) {
                 return segment;
             }
         }
         return null;
     }
 
     /** Build the loop containing a segment.
      * <p>
      * The segment put in the loop will be marked as processed.
      * </p>
      * @param defining segment used to define the loop
      * @return loop containing the segment (may be null if the loop is a
      * degenerated infinitely thin 2 points loop
      */
     private List<Segment> followLoop(final ConnectableSegment defining) {
 
         final List<Segment> loop = new ArrayList<>();
         loop.add(defining);
         defining.setProcessed(true);
 
         // add segments in connection order
         ConnectableSegment next = defining.getNext();
         while (next != defining && next != null) {
             loop.add(next);
             next.setProcessed(true);
             next = next.getNext();
         }
 
         if (next == null) {
             // the loop is open and we have found its end,
             // we need to find its start too
             ConnectableSegment previous = defining.getPrevious();
             while (previous != null) {
                 loop.add(0, previous);
                 previous.setProcessed(true);
                 previous = previous.getPrevious();
             }
         }
 
         // filter out spurious vertices
         filterSpuriousVertices(loop);
 
         if (loop.size() == 2 && loop.get(0).getStart() != null) {
             // this is a degenerated infinitely thin closed loop, we simply ignore it
             return null; // NOPMD
         } else {
             return loop;
         }
 
     }
 
     /** Filter out spurious vertices on straight lines (at machine precision).
      * @param loop segments loop to filter (will be modified in-place)
      */
     private void filterSpuriousVertices(final List<Segment> loop) {
         for (int i = 0; i < loop.size(); ++i) {
             final Segment previous = loop.get(i);
             int j = (i + 1) % loop.size();
             final Segment next = loop.get(j);
             if (next != null &&
                 Precision.equals(previous.getLine().getAngle(), next.getLine().getAngle(), Precision.EPSILON)) {
                 // the vertex between the two edges is a spurious one
                 // replace the two segments by a single one
                 loop.set(j, new Segment(previous.getStart(), next.getEnd(), previous.getLine()));
                 loop.remove(i--);
             }
         }
     }
 
     /** Private extension of Segment allowing connection. */
     private static class ConnectableSegment extends Segment {
 
         /** Node containing segment. */
         private final BSPTree<Euclidean2D> node;
 
         /** Node whose intersection with current node defines start point. */
         private final BSPTree<Euclidean2D> startNode;
 
         /** Node whose intersection with current node defines end point. */
         private final BSPTree<Euclidean2D> endNode;
 
         /** Previous segment. */
         private ConnectableSegment previous;
 
         /** Next segment. */
         private ConnectableSegment next;
 
         /** Indicator for completely processed segments. */
         private boolean processed;
 
         /** Build a segment.
          * @param start start point of the segment
          * @param end end point of the segment
          * @param line line containing the segment
          * @param node node containing the segment
          * @param startNode node whose intersection with current node defines start point
          * @param endNode node whose intersection with current node defines end point
          */
         ConnectableSegment(final Vector2D start, final Vector2D end, final Line line,
                            final BSPTree<Euclidean2D> node,
                            final BSPTree<Euclidean2D> startNode,
                            final BSPTree<Euclidean2D> endNode) {
             super(start, end, line);
             this.node      = node;
             this.startNode = startNode;
             this.endNode   = endNode;
             this.previous  = null;
             this.next      = null;
             this.processed = false;
         }
 
         /** Get the node containing segment.
          * @return node containing segment
          */
         public BSPTree<Euclidean2D> getNode() {
             return node;
         }
 
         /** Get the node whose intersection with current node defines start point.
          * @return node whose intersection with current node defines start point
          */
         public BSPTree<Euclidean2D> getStartNode() {
             return startNode;
         }
 
         /** Get the node whose intersection with current node defines end point.
          * @return node whose intersection with current node defines end point
          */
         public BSPTree<Euclidean2D> getEndNode() {
             return endNode;
         }
 
         /** Get the previous segment.
          * @return previous segment
          */
         public ConnectableSegment getPrevious() {
             return previous;
         }
 
         /** Set the previous segment.
          * @param previous previous segment
          */
         public void setPrevious(final ConnectableSegment previous) {
             this.previous = previous;
         }
 
         /** Get the next segment.
          * @return next segment
          */
         public ConnectableSegment getNext() {
             return next;
         }
 
         /** Set the next segment.
          * @param next previous segment
          */
         public void setNext(final ConnectableSegment next) {
             this.next = next;
         }
 
         /** Set the processed flag.
          * @param processed processed flag to set
          */
         public void setProcessed(final boolean processed) {
             this.processed = processed;
         }
 
         /** Check if the segment has been processed.
          * @return true if the segment has been processed
          */
         public boolean isProcessed() {
             return processed;
         }
 
     }
 
     /** Visitor building segments. */
     private static class SegmentsBuilder implements BSPTreeVisitor<Euclidean2D> {
 
         /** Tolerance for close nodes connection. */
         private final double tolerance;
 
         /** Built segments. */
         private final List<ConnectableSegment> segments;
 
         /** Simple constructor.
          * @param tolerance tolerance for close nodes connection
          */
         SegmentsBuilder(final double tolerance) {
             this.tolerance = tolerance;
             this.segments  = new ArrayList<>();
         }
 
         /** {@inheritDoc} */
         @Override
         public Order visitOrder(final BSPTree<Euclidean2D> node) {
             return Order.MINUS_SUB_PLUS;
         }
 
         /** {@inheritDoc} */
         @Override
         public void visitInternalNode(final BSPTree<Euclidean2D> node) {
             @SuppressWarnings("unchecked")
             final BoundaryAttribute<Euclidean2D> attribute = (BoundaryAttribute<Euclidean2D>) node.getAttribute();
             final Iterable<BSPTree<Euclidean2D>> splitters = attribute.getSplitters();
             if (attribute.getPlusOutside() != null) {
                 addContribution(attribute.getPlusOutside(), node, splitters, false);
             }
             if (attribute.getPlusInside() != null) {
                 addContribution(attribute.getPlusInside(), node, splitters, true);
             }
         }
 
         /** {@inheritDoc} */
         @Override
         public void visitLeafNode(final BSPTree<Euclidean2D> node) {
         }
 
         /** Add the contribution of a boundary facet.
          * @param sub boundary facet
          * @param node node containing segment
          * @param splitters splitters for the boundary facet
          * @param reversed if true, the facet has the inside on its plus side
          */
         private void addContribution(final SubHyperplane<Euclidean2D> sub,
                                      final BSPTree<Euclidean2D> node,
                                      final Iterable<BSPTree<Euclidean2D>> splitters,
                                      final boolean reversed) {
             final AbstractSubHyperplane<Euclidean2D, Euclidean1D> absSub =
                 (AbstractSubHyperplane<Euclidean2D, Euclidean1D>) sub;
             final Line line      = (Line) sub.getHyperplane();
             final List<Interval> intervals = ((IntervalsSet) absSub.getRemainingRegion()).asList();
             for (final Interval i : intervals) {
 
                 // find the 2D points
                 final Vector2D startV = Double.isInfinite(i.getInf()) ?
                                         null : (Vector2D) line.toSpace((Point<Euclidean1D>) new Vector1D(i.getInf()));
                 final Vector2D endV   = Double.isInfinite(i.getSup()) ?
                                         null : (Vector2D) line.toSpace((Point<Euclidean1D>) new Vector1D(i.getSup()));
 
                 // recover the connectivity information
                 final BSPTree<Euclidean2D> startN = selectClosest(startV, splitters);
                 final BSPTree<Euclidean2D> endN   = selectClosest(endV, splitters);
 
                 if (reversed) {
                     segments.add(new ConnectableSegment(endV, startV, line.getReverse(),
                                                         node, endN, startN));
                 } else {
                     segments.add(new ConnectableSegment(startV, endV, line,
                                                         node, startN, endN));
                 }
 
             }
         }
 
         /** Select the node whose cut sub-hyperplane is closest to specified point.
          * @param point reference point
          * @param candidates candidate nodes
          * @return node closest to point, or null if no node is closer than tolerance
          */
         private BSPTree<Euclidean2D> selectClosest(final Vector2D point, final Iterable<BSPTree<Euclidean2D>> candidates) {
 
             if (point == null) {
                 return null;
             }
 
             BSPTree<Euclidean2D> selected = null;
 
             double min = Double.POSITIVE_INFINITY;
             for (final BSPTree<Euclidean2D> node : candidates) {
                 final double distance = FastMath.abs(node.getCut().getHyperplane().getOffset(point));
                 if (distance < min) {
                     selected = node;
                     min      = distance;
                 }
             }
 
             return min <= tolerance ? selected : null;
 
         }
 
         /** Get the segments.
          * @return built segments
          */
         public List<ConnectableSegment> getSegments() {
             return segments;
         }
 
     }
 
 }