You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2014/12/03 12:20:41 UTC
[2/2] [math] Filter out spurious vertices in polygons boundaries.
Filter out spurious vertices in polygons boundaries.
Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/10b1c517
Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/10b1c517
Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/10b1c517
Branch: refs/heads/master
Commit: 10b1c517cd5c0083cd0ad7a5f23167d66d1e59fd
Parents: b4fb13b
Author: Luc Maisonobe <lu...@apache.org>
Authored: Wed Dec 3 12:20:18 2014 +0100
Committer: Luc Maisonobe <lu...@apache.org>
Committed: Wed Dec 3 12:20:18 2014 +0100
----------------------------------------------------------------------
src/changes/changes.xml | 4 ++
.../geometry/euclidean/twod/PolygonsSet.java | 42 +++++++++---
.../euclidean/twod/PolygonsSetTest.java | 69 ++++++++++++++++++++
3 files changed, 105 insertions(+), 10 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-math/blob/10b1c517/src/changes/changes.xml
----------------------------------------------------------------------
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 8ab9a1a..869154f 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -73,6 +73,10 @@ Users are encouraged to upgrade to this version as this release not
2. A few methods in the FastMath class are in fact slower that their
counterpart in either Math or StrictMath (cf. MATH-740 and MATH-901).
">
+ <action dev="luc" type="update" >
+ Spurious vertices in the middle of otherwise straight edges are now
+ filtered out when rebuilding polygons boundaries from BSP trees.
+ </action>
<action dev="luc" type="fix" issue="MATH-1174" >
Fixed a problem with too thin polygons considered to have infinite size.
</action>
http://git-wip-us.apache.org/repos/asf/commons-math/blob/10b1c517/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java
index dc3ef33..46268f5 100644
--- a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java
+++ b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSet.java
@@ -34,6 +34,7 @@ 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
@@ -704,9 +705,9 @@ public class PolygonsSet extends AbstractRegion<Euclidean2D, Euclidean1D> {
}
// create the segment loops
- final ArrayList<List<ConnectableSegment>> loops = new ArrayList<List<ConnectableSegment>>();
+ final ArrayList<List<Segment>> loops = new ArrayList<List<Segment>>();
for (ConnectableSegment s = getUnprocessed(segments); s != null; s = getUnprocessed(segments)) {
- final List<ConnectableSegment> loop = followLoop(s);
+ 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
@@ -722,7 +723,7 @@ public class PolygonsSet extends AbstractRegion<Euclidean2D, Euclidean1D> {
vertices = new Vector2D[loops.size()][];
int i = 0;
- for (final List<ConnectableSegment> loop : loops) {
+ 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
@@ -886,9 +887,9 @@ public class PolygonsSet extends AbstractRegion<Euclidean2D, Euclidean1D> {
* @return loop containing the segment (may be null if the loop is a
* degenerated infinitely thin 2 points loop
*/
- private List<ConnectableSegment> followLoop(final ConnectableSegment defining) {
+ private List<Segment> followLoop(final ConnectableSegment defining) {
- final List<ConnectableSegment> loop = new ArrayList<ConnectableSegment>();
+ final List<Segment> loop = new ArrayList<Segment>();
loop.add(defining);
defining.setProcessed(true);
@@ -909,15 +910,36 @@ public class PolygonsSet extends AbstractRegion<Euclidean2D, Euclidean1D> {
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 {
- if (loop.size() == 2) {
- // this is a degenerated infinitely thin loop, we simply ignore it
- return null;
- }
+ return loop;
}
- 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. */
http://git-wip-us.apache.org/repos/asf/commons-math/blob/10b1c517/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java b/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java
index f965742..a459484 100644
--- a/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java
+++ b/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/PolygonsSetTest.java
@@ -23,6 +23,7 @@ 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.BSPTree;
+import org.apache.commons.math3.geometry.partitioning.BSPTreeVisitor;
import org.apache.commons.math3.geometry.partitioning.BoundaryProjection;
import org.apache.commons.math3.geometry.partitioning.Hyperplane;
import org.apache.commons.math3.geometry.partitioning.Region;
@@ -1153,6 +1154,74 @@ public class PolygonsSetTest {
}
+ @Test
+ public void testBoundarySimplification() {
+
+ // a simple square will result in a 4 cuts and 5 leafs tree
+ PolygonsSet square = new PolygonsSet(1.0e-10,
+ new Vector2D(0, 0),
+ new Vector2D(1, 0),
+ new Vector2D(1, 1),
+ new Vector2D(0, 1));
+ Vector2D[][] squareBoundary = square.getVertices();
+ Assert.assertEquals(1, squareBoundary.length);
+ Assert.assertEquals(4, squareBoundary[0].length);
+ Counter squareCount = new Counter();
+ squareCount.count(square);
+ Assert.assertEquals(4, squareCount.getInternalNodes());
+ Assert.assertEquals(5, squareCount.getLeafNodes());
+
+ // splitting the square in two halves increases the BSP tree
+ // with 3 more cuts and 3 more leaf nodes
+ SubLine cut = new Line(new Vector2D(0.5, 0.5), 0.0, square.getTolerance()).wholeHyperplane();
+ PolygonsSet splitSquare = new PolygonsSet(square.getTree(false).split(cut),
+ square.getTolerance());
+ Counter splitSquareCount = new Counter();
+ splitSquareCount.count(splitSquare);
+ Assert.assertEquals(squareCount.getInternalNodes() + 3, splitSquareCount.getInternalNodes());
+ Assert.assertEquals(squareCount.getLeafNodes() + 3, splitSquareCount.getLeafNodes());
+
+ // the number of vertices should not change, as the intermediate vertices
+ // at (0.0, 0.5) and (1.0, 0.5) induced by the top level horizontal split
+ // should be removed during the boundary extraction process
+ Vector2D[][] splitBoundary = splitSquare.getVertices();
+ Assert.assertEquals(1, splitBoundary.length);
+ Assert.assertEquals(4, splitBoundary[0].length);
+
+ }
+
+ private static class Counter {
+
+ private int internalNodes;
+ private int leafNodes;
+
+ public void count(PolygonsSet polygonsSet) {
+ leafNodes = 0;
+ internalNodes = 0;
+ polygonsSet.getTree(false).visit(new BSPTreeVisitor<Euclidean2D>() {
+ public Order visitOrder(BSPTree<Euclidean2D> node) {
+ return Order.SUB_PLUS_MINUS;
+ }
+ public void visitInternalNode(BSPTree<Euclidean2D> node) {
+ ++internalNodes;
+ }
+ public void visitLeafNode(BSPTree<Euclidean2D> node) {
+ ++leafNodes;
+ }
+
+ });
+ }
+
+ public int getInternalNodes() {
+ return internalNodes;
+ }
+
+ public int getLeafNodes() {
+ return leafNodes;
+ }
+
+ }
+
private PolygonsSet buildSet(Vector2D[][] vertices) {
ArrayList<SubHyperplane<Euclidean2D>> edges = new ArrayList<SubHyperplane<Euclidean2D>>();
for (int i = 0; i < vertices.length; ++i) {