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 <l...@apache.org> Authored: Wed Dec 3 12:20:18 2014 +0100 Committer: Luc Maisonobe <l...@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) {
