Package org.apache.commons.math3.geometry.euclidean.twod

Class PolygonsSet

    • Field Detail

      • DEFAULT_TOLERANCE

        private static final double DEFAULT_TOLERANCE
        Default value for tolerance.
        See Also:
        Constant Field Values

      • vertices

        private Vector2D[][] vertices
        Vertices organized as boundary loops.

    • Constructor Detail

      • PolygonsSet

        public PolygonsSet​(double tolerance)
        Build a polygons set representing the whole plane.
        Parameters:
        tolerance - tolerance below which points are considered identical
        Since:
        3.3

      • PolygonsSet

        public PolygonsSet​(BSPTree<Euclidean2D> tree,
                   double tolerance)
        Build a polygons set from a BSP tree.

        The leaf nodes of the BSP tree must have a 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 Boolean.TRUE and Boolean.FALSE

        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, will therefore generate problems like NullPointerException or 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.

        Parameters:
        tree - inside/outside BSP tree representing the region
        tolerance - tolerance below which points are considered identical
        Since:
        3.3

      • PolygonsSet

        public PolygonsSet​(java.util.Collection<SubHyperplane<Euclidean2D>> boundary,
                   double tolerance)
        Build a polygons set from a Boundary REPresentation (B-rep).

        The boundary is provided as a collection of sub-hyperplanes. Each sub-hyperplane has the interior part of the region on its minus side and the exterior on its plus side.

        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 checkPoint method will not be meaningful anymore.

        If the boundary is empty, the region will represent the whole space.

        Parameters:
        boundary - collection of boundary elements, as a collection of SubHyperplane objects
        tolerance - tolerance below which points are considered identical
        Since:
        3.3

      • PolygonsSet

        public PolygonsSet​(double xMin,
                   double xMax,
                   double yMin,
                   double yMax,
                   double tolerance)
        Build a parallellepipedic box.
        Parameters:
        xMin - low bound along the x direction
        xMax - high bound along the x direction
        yMin - low bound along the y direction
        yMax - high bound along the y direction
        tolerance - tolerance below which points are considered identical
        Since:
        3.3

      • PolygonsSet

        public PolygonsSet​(double hyperplaneThickness,
                   Vector2D... vertices)
        Build a polygon from a simple list of vertices.

        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.

        This constructor does not handle polygons with a boundary forming several disconnected paths (such as polygons with holes).

        For cases where this simple constructor applies, it is expected to be numerically more robust than the general constructor using subhyperplanes.

        If the list is empty, the region will represent the whole space.

        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 π angle. Such cases need to carefully adjust the 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 hyperplaneThickness parameter.

        Parameters:
        hyperplaneThickness - tolerance below which points are considered to belong to the hyperplane (which is therefore more a slab)
        vertices - vertices of the simple loop boundary

      • PolygonsSet

        @Deprecated
public PolygonsSet()
        Deprecated.
        as of 3.3, replaced with PolygonsSet(double)
        Build a polygons set representing the whole real line.

      • PolygonsSet

        @Deprecated
public PolygonsSet​(BSPTree<Euclidean2D> tree)
        Deprecated.
        as of 3.3, replaced with PolygonsSet(BSPTree, double)
        Build a polygons set from a BSP tree.

        The leaf nodes of the BSP tree must have a 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 Boolean.TRUE and Boolean.FALSE

        Parameters:
        tree - inside/outside BSP tree representing the region

      • PolygonsSet

        @Deprecated
public PolygonsSet​(java.util.Collection<SubHyperplane<Euclidean2D>> boundary)
        Deprecated.
        as of 3.3, replaced with PolygonsSet(Collection, double)
        Build a polygons set from a Boundary REPresentation (B-rep).

        The boundary is provided as a collection of sub-hyperplanes. Each sub-hyperplane has the interior part of the region on its minus side and the exterior on its plus side.

        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 checkPoint method will not be meaningful anymore.

        If the boundary is empty, the region will represent the whole space.

        Parameters:
        boundary - collection of boundary elements, as a collection of SubHyperplane objects

      • PolygonsSet

        @Deprecated
public PolygonsSet​(double xMin,
                   double xMax,
                   double yMin,
                   double yMax)
        Deprecated.
        as of 3.3, replaced with PolygonsSet(double, double, double, double, double)
        Build a parallellepipedic box.
        Parameters:
        xMin - low bound along the x direction
        xMax - high bound along the x direction
        yMin - low bound along the y direction
        yMax - high bound along the y direction

    • Method Detail

      • boxBoundary

        private static Line[] boxBoundary​(double xMin,
                                  double xMax,
                                  double yMin,
                                  double yMax,
                                  double tolerance)
        Create a list of hyperplanes representing the boundary of a box.
        Parameters:
        xMin - low bound along the x direction
        xMax - high bound along the x direction
        yMin - low bound along the y direction
        yMax - high bound along the y direction
        tolerance - tolerance below which points are considered identical
        Returns:
        boundary of the box

      • verticesToTree

        private static BSPTree<Euclidean2D> verticesToTree​(double hyperplaneThickness,
                                                   Vector2D... vertices)
        Build the BSP tree of a polygons set from a simple list of vertices.

        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.

        This constructor does not handle polygons with a boundary forming several disconnected paths (such as polygons with holes).

        For cases where this simple constructor applies, it is expected to be numerically more robust than the general constructor using subhyperplanes.

        Parameters:
        hyperplaneThickness - tolerance below which points are consider to belong to the hyperplane (which is therefore more a slab)
        vertices - vertices of the simple loop boundary
        Returns:
        the BSP tree of the input vertices

      • insertEdges

        private static void insertEdges​(double hyperplaneThickness,
                                BSPTree<Euclidean2D> node,
                                java.util.List<PolygonsSet.Edge> edges)
        Recursively build a tree by inserting cut sub-hyperplanes.
        Parameters:
        hyperplaneThickness - tolerance below which points are consider to belong to the hyperplane (which is therefore more a slab)
        node - current tree node (it is a leaf node at the beginning of the call)
        edges - list of edges to insert in the cell defined by this node (excluding edges not belonging to the cell defined by this node)

      • buildNew

        public PolygonsSet buildNew​(BSPTree<Euclidean2D> tree)
        Build a region using the instance as a prototype.

        This method allow to create new instances without knowing exactly the type of the region. It is an application of the prototype design pattern.

        The leaf nodes of the BSP tree must have a 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 Boolean.TRUE and Boolean.FALSE. The tree also must have either null internal nodes or internal nodes representing the boundary as specified in the getTree method).

        Specified by:
        buildNew in interface Region<Euclidean2D>
        Specified by:
        buildNew in class AbstractRegion<Euclidean2D,​Euclidean1D>
        Parameters:
        tree - inside/outside BSP tree representing the new region
        Returns:
        the built region

      • getVertices

        public Vector2D[][] getVertices()
        Get the vertices of the polygon.

        The polygon boundary can be represented as an array of loops, each loop being itself an array of vertices.

        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.

        If the polygon has no boundary at all, a zero length loop array will be returned.

        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.

        Returns:
        vertices of the polygon, organized as oriented boundary loops with the open loops first (the returned value is guaranteed to be non-null)

      • naturalFollowerConnections

        private int naturalFollowerConnections​(java.util.List<PolygonsSet.ConnectableSegment> segments)
        Connect the segments using only natural follower information.
        Parameters:
        segments - segments complete segments list
        Returns:
        number of connections performed

      • splitEdgeConnections

        private int splitEdgeConnections​(java.util.List<PolygonsSet.ConnectableSegment> segments)
        Connect the segments resulting from a line splitting a straight edge.
        Parameters:
        segments - segments complete segments list
        Returns:
        number of connections performed

      • closeVerticesConnections

        private int closeVerticesConnections​(java.util.List<PolygonsSet.ConnectableSegment> segments)
        Connect the segments using Euclidean distance.

        This connection heuristic should be used last, as it relies only on a fuzzy distance criterion.

        Parameters:
        segments - segments complete segments list
        Returns:
        number of connections performed

      • getUnprocessed

        private PolygonsSet.ConnectableSegment getUnprocessed​(java.util.List<PolygonsSet.ConnectableSegment> segments)
        Get first unprocessed segment from a list.
        Parameters:
        segments - segments list
        Returns:
        first segment that has not been processed yet or null if all segments have been processed

      • followLoop

        private java.util.List<Segment> followLoop​(PolygonsSet.ConnectableSegment defining)
        Build the loop containing a segment.

        The segment put in the loop will be marked as processed.

        Parameters:
        defining - segment used to define the loop
        Returns:
        loop containing the segment (may be null if the loop is a degenerated infinitely thin 2 points loop

      • filterSpuriousVertices

        private void filterSpuriousVertices​(java.util.List<Segment> loop)
        Filter out spurious vertices on straight lines (at machine precision).
        Parameters:
        loop - segments loop to filter (will be modified in-place)