/*
 * 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
 *
 *      http://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.
 */
package org.apache.commons.math3.geometry.euclidean.twod;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import org.apache.commons.math3.geometry.Point;
import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
import org.apache.commons.math3.geometry.euclidean.oned.Interval;
import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet;
import org.apache.commons.math3.geometry.euclidean.oned.Vector1D;
import org.apache.commons.math3.geometry.partitioning.AbstractRegion;
import org.apache.commons.math3.geometry.partitioning.AbstractSubHyperplane;
import org.apache.commons.math3.geometry.partitioning.BSPTree;
import org.apache.commons.math3.geometry.partitioning.BSPTreeVisitor;
import org.apache.commons.math3.geometry.partitioning.BoundaryAttribute;
import org.apache.commons.math3.geometry.partitioning.Hyperplane;
import org.apache.commons.math3.geometry.partitioning.Side;
import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
import org.apache.commons.math3.util.FastMath;
import org.apache.commons.math3.util.Precision;

This class represents a 2D region: a set of polygons.
Since:3.0
/** This class represents a 2D region: a set of polygons. * @since 3.0 */
public class PolygonsSet extends AbstractRegion<Euclidean2D, Euclidean1D> {
Default value for tolerance.
/** Default value for tolerance. */
private static final double DEFAULT_TOLERANCE = 1.0e-10;
Vertices organized as boundary loops.
/** Vertices organized as boundary loops. */
private Vector2D[][] vertices;
Build a polygons set representing the whole plane.
Params:
  • tolerance – tolerance below which points are considered identical
Since:3.3
/** Build a polygons set representing the whole plane. * @param tolerance tolerance below which points are considered identical * @since 3.3 */
public PolygonsSet(final double tolerance) { super(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.

Params:
  • tree – inside/outside BSP tree representing the region
  • tolerance – tolerance below which points are considered identical
Since:3.3
/** 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 * @since 3.3 */
public PolygonsSet(final BSPTree<Euclidean2D> tree, final double tolerance) { super(tree, 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.

Params:
  • boundary – collection of boundary elements, as a collection of SubHyperplane objects
  • tolerance – tolerance below which points are considered identical
Since:3.3
/** 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.apache.commons.math3.geometry.partitioning.Region#checkPoint(org.apache.commons.math3.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 * @since 3.3 */
public PolygonsSet(final Collection<SubHyperplane<Euclidean2D>> boundary, final double tolerance) { super(boundary, tolerance); }
Build a parallellepipedic box.
Params:
  • 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
/** 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 * @since 3.3 */
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.

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.

Params:
  • 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
/** 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) 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); }
Build a polygons set representing the whole real line.
Deprecated:as of 3.3, replaced with PolygonsSet(double)
/** Build a polygons set representing the whole real line. * @deprecated as of 3.3, replaced with {@link #PolygonsSet(double)} */
@Deprecated public PolygonsSet() { this(DEFAULT_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

Params:
  • tree – inside/outside BSP tree representing the region
Deprecated:as of 3.3, replaced with PolygonsSet(BSPTree<Euclidean2D>, double)
/** 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> * @param tree inside/outside BSP tree representing the region * @deprecated as of 3.3, replaced with {@link #PolygonsSet(BSPTree, double)} */
@Deprecated public PolygonsSet(final BSPTree<Euclidean2D> tree) { this(tree, DEFAULT_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.

Params:
  • boundary – collection of boundary elements, as a collection of SubHyperplane objects
Deprecated:as of 3.3, replaced with PolygonsSet(Collection<SubHyperplane<Euclidean2D>>, double)
/** 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.apache.commons.math3.geometry.partitioning.Region#checkPoint(org.apache.commons.math3.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 * @deprecated as of 3.3, replaced with {@link #PolygonsSet(Collection, double)} */
@Deprecated public PolygonsSet(final Collection<SubHyperplane<Euclidean2D>> boundary) { this(boundary, DEFAULT_TOLERANCE); }
Build a parallellepipedic box.
Params:
  • 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
Deprecated:as of 3.3, replaced with PolygonsSet(double, double, double, double, double)
/** 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 * @deprecated as of 3.3, replaced with {@link #PolygonsSet(double, double, double, double, double)} */
@Deprecated public PolygonsSet(final double xMin, final double xMax, final double yMin, final double yMax) { this(xMin, xMax, yMin, yMax, DEFAULT_TOLERANCE); }
Create a list of hyperplanes representing the boundary of a box.
Params:
  • 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
/** 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; } 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.

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.

Params:
  • 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
/** 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) 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]; for (int i = 0; i < n; ++i) { vArray[i] = new Vertex(vertices[i]); } // build the edges List<Edge> edges = new ArrayList<Edge>(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 Line line = start.sharedLineWith(end); if (line == null) { line = new Line(start.getLocation(), end.getLocation(), hyperplaneThickness); } // create the edge and store it edges.add(new Edge(start, end, line)); // check if another vertex also happens to be on this line for (final Vertex vertex : vArray) { if (vertex != start && vertex != end && FastMath.abs(line.getOffset((Point<Euclidean2D>) vertex.getLocation())) <= hyperplaneThickness) { vertex.bindWith(line); } } } // build the tree top-down final BSPTree<Euclidean2D> tree = new BSPTree<Euclidean2D>(); insertEdges(hyperplaneThickness, tree, edges); return tree; }
Recursively build a tree by inserting cut sub-hyperplanes.
Params:
  • 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)
/** 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<Edge>(); final List<Edge> minusList = new ArrayList<Edge>(); 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.
/** Internal class for holding vertices while they are processed to build a BSP tree. */
private static class Vertex {
Vertex location.
/** Vertex location. */
private final Vector2D location;
Incoming edge.
/** Incoming edge. */
private Edge incoming;
Outgoing edge.
/** Outgoing edge. */
private Edge outgoing;
Lines bound with this vertex.
/** Lines bound with this vertex. */
private final List<Line> lines;
Build a non-processed vertex not owned by any node yet.
Params:
  • location – vertex location
/** 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; this.lines = new ArrayList<Line>(); }
Get Vertex location.
Returns:vertex location
/** Get Vertex location. * @return vertex location */
public Vector2D getLocation() { return location; }
Bind a line considered to contain this vertex.
Params:
  • line – line to bind with this vertex
/** Bind a line considered to contain this vertex. * @param line line to bind with this vertex */
public void bindWith(final Line line) { lines.add(line); }
Get the common line bound with both the instance and another vertex, if any.

When two vertices are both bound to the same line, this means they are already handled by node associated with this line, so there is no need to create a cut hyperplane for them.

Params:
  • vertex – other vertex to check instance against
Returns:line bound with both the instance and another vertex, or null if the two vertices do not share a line yet
/** Get the common line bound with both the instance and another vertex, if any. * <p> * When two vertices are both bound to the same line, this means they are * already handled by node associated with this line, so there is no need * to create a cut hyperplane for them. * </p> * @param vertex other vertex to check instance against * @return line bound with both the instance and another vertex, or null if the * two vertices do not share a line yet */
public Line sharedLineWith(final Vertex vertex) { for (final Line line1 : lines) { for (final Line line2 : vertex.lines) { if (line1 == line2) { return line1; } } } return null; }
Set incoming edge.

The line supporting the incoming edge is automatically bound with the instance.

Params:
  • incoming – incoming edge
/** 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; bindWith(incoming.getLine()); }
Get incoming edge.
Returns:incoming edge
/** Get incoming edge. * @return incoming edge */
public Edge getIncoming() { return incoming; }
Set outgoing edge.

The line supporting the outgoing edge is automatically bound with the instance.

Params:
  • outgoing – outgoing edge
/** 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; bindWith(outgoing.getLine()); }
Get outgoing edge.
Returns:outgoing edge
/** 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.
/** Internal class for holding edges while they are processed to build a BSP tree. */
private static class Edge {
Start vertex.
/** Start vertex. */
private final Vertex start;
End vertex.
/** End vertex. */
private final Vertex end;
Line supporting the edge.
/** Line supporting the edge. */
private final Line line;
Node whose cut hyperplane contains this edge.
/** Node whose cut hyperplane contains this edge. */
private BSPTree<Euclidean2D> node;
Build an edge not contained in any node yet.
Params:
  • start – start vertex
  • end – end vertex
  • line – line supporting the edge
/** 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.
Returns:start vertex
/** Get start vertex. * @return start vertex */
public Vertex getStart() { return start; }
Get end vertex.
Returns:end vertex
/** Get end vertex. * @return end vertex */
public Vertex getEnd() { return end; }
Get the line supporting this edge.
Returns:line supporting this edge
/** 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.
Params:
  • node – node whose cut hyperplane contains this edge
/** 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.
Returns:node whose cut hyperplane contains this edge (null if edge has not yet been inserted into the BSP tree)
/** 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.

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.

Params:
  • splitLine – line splitting the edge in two halves
Returns:split vertex (its incoming and outgoing edges are the two halves)
/** 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)); splitVertex.bindWith(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}
/** {@inheritDoc} */
@Override public PolygonsSet buildNew(final BSPTree<Euclidean2D> tree) { return new PolygonsSet(tree, getTolerance()); }
{@inheritDoc}
/** {@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.

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)
/** 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) { pending -= closeVerticesConnections(segments); } // create the segment loops final ArrayList<List<Segment>> loops = new ArrayList<List<Segment>>(); 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.
Params:
  • segments – segments complete segments list
Returns:number of connections performed
/** 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.
Params:
  • segments – segments complete segments list
Returns:number of connections performed
/** 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.

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

Params:
  • segments – segments complete segments list
Returns:number of connections performed
/** 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.
Params:
  • segments – segments list
Returns:first segment that has not been processed yet or null if all segments have been processed
/** 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.

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

Params:
  • 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
/** 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<Segment>(); 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; } else { return loop; } }
Filter out spurious vertices on straight lines (at machine precision).
Params:
  • loop – segments loop to filter (will be modified in-place)
/** 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 extension of Segment allowing connection. */
private static class ConnectableSegment extends Segment {
Node containing segment.
/** Node containing segment. */
private final BSPTree<Euclidean2D> node;
Node whose intersection with current node defines start point.
/** Node whose intersection with current node defines start point. */
private final BSPTree<Euclidean2D> startNode;
Node whose intersection with current node defines end point.
/** Node whose intersection with current node defines end point. */
private final BSPTree<Euclidean2D> endNode;
Previous segment.
/** Previous segment. */
private ConnectableSegment previous;
Next segment.
/** Next segment. */
private ConnectableSegment next;
Indicator for completely processed segments.
/** Indicator for completely processed segments. */
private boolean processed;
Build a segment.
Params:
  • start – start point of the segment
  • end – end point of the segment
  • line – line containing the segment
  • node – node containing the segment
  • startNode – node whose intersection with current node defines start point
  • endNode – node whose intersection with current node defines end point
/** 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.
Returns:node containing segment
/** 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.
Returns:node whose intersection with current node defines start point
/** 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.
Returns:node whose intersection with current node defines end point
/** 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.
Returns:previous segment
/** Get the previous segment. * @return previous segment */
public ConnectableSegment getPrevious() { return previous; }
Set the previous segment.
Params:
  • previous – previous segment
/** Set the previous segment. * @param previous previous segment */
public void setPrevious(final ConnectableSegment previous) { this.previous = previous; }
Get the next segment.
Returns:next segment
/** Get the next segment. * @return next segment */
public ConnectableSegment getNext() { return next; }
Set the next segment.
Params:
  • next – previous segment
/** Set the next segment. * @param next previous segment */
public void setNext(final ConnectableSegment next) { this.next = next; }
Set the processed flag.
Params:
  • processed – processed flag to set
/** 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.
Returns:true if the segment has been processed
/** Check if the segment has been processed. * @return true if the segment has been processed */
public boolean isProcessed() { return processed; } }
Visitor building segments.
/** Visitor building segments. */
private static class SegmentsBuilder implements BSPTreeVisitor<Euclidean2D> {
Tolerance for close nodes connection.
/** Tolerance for close nodes connection. */
private final double tolerance;
Built segments.
/** Built segments. */
private final List<ConnectableSegment> segments;
Simple constructor.
Params:
  • tolerance – tolerance for close nodes connection
/** Simple constructor. * @param tolerance tolerance for close nodes connection */
SegmentsBuilder(final double tolerance) { this.tolerance = tolerance; this.segments = new ArrayList<ConnectableSegment>(); }
{@inheritDoc}
/** {@inheritDoc} */
public Order visitOrder(final BSPTree<Euclidean2D> node) { return Order.MINUS_SUB_PLUS; }
{@inheritDoc}
/** {@inheritDoc} */
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}
/** {@inheritDoc} */
public void visitLeafNode(final BSPTree<Euclidean2D> node) { }
Add the contribution of a boundary facet.
Params:
  • sub – boundary facet
  • node – node containing segment
  • splitters – splitters for the boundary facet
  • reversed – if true, the facet has the inside on its plus side
/** 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) { @SuppressWarnings("unchecked") 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.
Params:
  • point – reference point
  • candidates – candidate nodes
Returns:node closest to point, or null if no node is closer than tolerance
/** 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) { 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.
Returns:built segments
/** Get the segments. * @return built segments */
public List<ConnectableSegment> getSegments() { return segments; } } }