Author: luc
Date: Mon Jun 20 19:11:43 2011
New Revision: 1137749
URL: http://svn.apache.org/viewvc?rev=1137749&view=rev
Log:
Simplified SubLine API by introducing a public Segment class.
JIRA: MATH-592
Removed:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/SegmentBuilder.java
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/PolygonsSet.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/Segment.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/SubLine.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math/geometry/euclidean/twod/SubLineTest.java
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/PolygonsSet.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/PolygonsSet.java?rev=1137749&r1=1137748&r2=1137749&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/PolygonsSet.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/PolygonsSet.java
Mon Jun 20 19:11:43 2011
@@ -22,11 +22,17 @@ import java.util.List;
import org.apache.commons.math.exception.MathInternalError;
import org.apache.commons.math.geometry.euclidean.oned.Euclidean1D;
+import org.apache.commons.math.geometry.euclidean.oned.Interval;
+import org.apache.commons.math.geometry.euclidean.oned.IntervalsSet;
import org.apache.commons.math.geometry.euclidean.oned.Vector1D;
+import org.apache.commons.math.geometry.partitioning.AbstractSubHyperplane;
import org.apache.commons.math.geometry.partitioning.BSPTree;
+import org.apache.commons.math.geometry.partitioning.BSPTreeVisitor;
+import org.apache.commons.math.geometry.partitioning.BoundaryAttribute;
import org.apache.commons.math.geometry.partitioning.SubHyperplane;
import org.apache.commons.math.geometry.partitioning.AbstractRegion;
import org.apache.commons.math.geometry.partitioning.utilities.AVLTree;
+import org.apache.commons.math.geometry.partitioning.utilities.OrderedTuple;
import org.apache.commons.math.util.FastMath;
/** This class represents a 2D region: a set of polygons.
@@ -202,14 +208,14 @@ public class PolygonsSet extends Abstrac
// sort the segments according to their start point
final SegmentsBuilder visitor = new SegmentsBuilder();
getTree(true).visit(visitor);
- final AVLTree<Segment> sorted = visitor.getSorted();
+ final AVLTree<ComparableSegment> sorted = visitor.getSorted();
// identify the loops, starting from the open ones
// (their start segments are naturally at the sorted set
beginning)
- final ArrayList<List<Segment>> loops = new
ArrayList<List<Segment>>();
+ final ArrayList<List<ComparableSegment>> loops = new
ArrayList<List<ComparableSegment>>();
while (!sorted.isEmpty()) {
- final AVLTree<Segment>.Node node = sorted.getSmallest();
- final List<Segment> loop = followLoop(node, sorted);
+ final AVLTree<ComparableSegment>.Node node =
sorted.getSmallest();
+ final List<ComparableSegment> loop = followLoop(node,
sorted);
if (loop != null) {
loops.add(loop);
}
@@ -219,7 +225,7 @@ public class PolygonsSet extends Abstrac
vertices = new Vector2D[loops.size()][];
int i = 0;
- for (final List<Segment> loop : loops) {
+ for (final List<ComparableSegment> loop : loops) {
if (loop.size() < 2) {
// single infinite line
final Line line = loop.get(0).getLine();
@@ -280,11 +286,11 @@ public class PolygonsSet extends Abstrac
* @return a list of connected sub-hyperplanes starting at
* {@code node}
*/
- private List<Segment> followLoop(final AVLTree<Segment>.Node node,
- final AVLTree<Segment> sorted) {
+ private List<ComparableSegment> followLoop(final
AVLTree<ComparableSegment>.Node node,
+ final
AVLTree<ComparableSegment> sorted) {
- final ArrayList<Segment> loop = new ArrayList<Segment>();
- Segment segment = node.getElement();
+ final ArrayList<ComparableSegment> loop = new
ArrayList<ComparableSegment>();
+ ComparableSegment segment = node.getElement();
loop.add(segment);
final Vector2D globalStart = segment.getStart();
Vector2D end = segment.getEnd();
@@ -296,15 +302,15 @@ public class PolygonsSet extends Abstrac
while ((end != null) && (open || (globalStart.distance(end) >
1.0e-10))) {
// search the sub-hyperplane starting where the previous one ended
- AVLTree<Segment>.Node selectedNode = null;
- Segment selectedSegment = null;
- double selectedDistance = Double.POSITIVE_INFINITY;
- final Segment lowerLeft = new Segment(end, -1.0e-10,
-1.0e-10);
- final Segment upperRight = new Segment(end, +1.0e-10,
+1.0e-10);
- for (AVLTree<Segment>.Node n = sorted.getNotSmaller(lowerLeft);
+ AVLTree<ComparableSegment>.Node selectedNode = null;
+ ComparableSegment selectedSegment = null;
+ double selectedDistance =
Double.POSITIVE_INFINITY;
+ final ComparableSegment lowerLeft = new
ComparableSegment(end, -1.0e-10, -1.0e-10);
+ final ComparableSegment upperRight = new
ComparableSegment(end, +1.0e-10, +1.0e-10);
+ for (AVLTree<ComparableSegment>.Node n =
sorted.getNotSmaller(lowerLeft);
(n != null) && (n.getElement().compareTo(upperRight) <= 0);
n = n.getNext()) {
- segment = (Segment) n.getElement();
+ segment = n.getElement();
final double distance = end.distance(segment.getStart());
if (distance < selectedDistance) {
selectedNode = n;
@@ -339,4 +345,125 @@ public class PolygonsSet extends Abstrac
}
+ private static class ComparableSegment extends Segment implements
Comparable<ComparableSegment> {
+
+ /** Sorting key. */
+ private OrderedTuple sortingKey;
+
+ /** Build a segment.
+ * @param start start point of the segment
+ * @param end end point of the segment
+ * @param line line containing the segment
+ */
+ public ComparableSegment(final Vector2D start, final Vector2D end,
final Line line) {
+ super(start, end, line);
+ sortingKey = (start == null) ?
+ new OrderedTuple(Double.NEGATIVE_INFINITY,
Double.NEGATIVE_INFINITY) :
+ new OrderedTuple(start.getX(), start.getY());
+ }
+
+ /** Build a dummy segment.
+ * <p>
+ * The object built is not a real segment, only the sorting key is
used to
+ * allow searching in the neighborhood of a point. This is an horrible
hack ...
+ * </p>
+ * @param start start point of the segment
+ * @param dx abscissa offset from the start point
+ * @param dy ordinate offset from the start point
+ */
+ public ComparableSegment(final Vector2D start, final double dx, final
double dy) {
+ super(null, null, null);
+ sortingKey = new OrderedTuple(start.getX() + dx, start.getY() +
dy);
+ }
+
+ /** {@inheritDoc} */
+ public int compareTo(final ComparableSegment o) {
+ return sortingKey.compareTo(o.sortingKey);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean equals(final Object other) {
+ if (this == other) {
+ return true;
+ } else if (other instanceof ComparableSegment) {
+ return compareTo((ComparableSegment) other) == 0;
+ } else {
+ return false;
+ }
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public int hashCode() {
+ return getStart().hashCode() ^ getEnd().hashCode() ^
+ getLine().hashCode() ^ sortingKey.hashCode();
+ }
+
+ }
+
+ /** Visitor building segments. */
+ private static class SegmentsBuilder implements
BSPTreeVisitor<Euclidean2D> {
+
+ /** Sorted segments. */
+ private AVLTree<ComparableSegment> sorted;
+
+ /** Simple constructor. */
+ public SegmentsBuilder() {
+ sorted = new AVLTree<ComparableSegment>();
+ }
+
+ /** {@inheritDoc} */
+ public Order visitOrder(final BSPTree<Euclidean2D> node) {
+ return Order.MINUS_SUB_PLUS;
+ }
+
+ /** {@inheritDoc} */
+ public void visitInternalNode(final BSPTree<Euclidean2D> node) {
+ @SuppressWarnings("unchecked")
+ final BoundaryAttribute<Euclidean2D> attribute =
(BoundaryAttribute<Euclidean2D>) node.getAttribute();
+ if (attribute.getPlusOutside() != null) {
+ addContribution(attribute.getPlusOutside(), false);
+ }
+ if (attribute.getPlusInside() != null) {
+ addContribution(attribute.getPlusInside(), true);
+ }
+ }
+
+ /** {@inheritDoc} */
+ public void visitLeafNode(final BSPTree<Euclidean2D> node) {
+ }
+
+ /** Add he contribution of a boundary facet.
+ * @param sub boundary facet
+ * @param reversed if true, the facet has the inside on its plus side
+ */
+ private void addContribution(final SubHyperplane<Euclidean2D> sub,
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) {
+ final Vector2D start = Double.isInfinite(i.getLower()) ?
+ null : (Vector2D) line.toSpace(new
Vector1D(i.getLower()));
+ final Vector2D end = Double.isInfinite(i.getUpper()) ?
+ null : (Vector2D) line.toSpace(new
Vector1D(i.getUpper()));
+ if (reversed) {
+ sorted.insert(new ComparableSegment(end, start,
line.getReverse()));
+ } else {
+ sorted.insert(new ComparableSegment(start, end, line));
+ }
+ }
+ }
+
+ /** Get the sorted segments.
+ * @return sorted segments
+ */
+ public AVLTree<ComparableSegment> getSorted() {
+ return sorted;
+ }
+
+ }
+
}
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/Segment.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/Segment.java?rev=1137749&r1=1137748&r2=1137749&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/Segment.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/Segment.java
Mon Jun 20 19:11:43 2011
@@ -16,25 +16,21 @@
*/
package org.apache.commons.math.geometry.euclidean.twod;
-import org.apache.commons.math.geometry.partitioning.utilities.OrderedTuple;
-/** This class holds segments information before they are connected.
+/** Simple container for a two-points segment.
* @version $Id$
* @since 3.0
*/
-class Segment implements Comparable<Segment> {
+public class Segment {
/** Start point of the segment. */
- private final Vector2D start;
+ private final Vector2D start;
/** End point of the segments. */
- private final Vector2D end;
+ private final Vector2D end;
/** Line containing the segment. */
- private final Line line;
-
- /** Sorting key. */
- private OrderedTuple sortingKey;
+ private final Line line;
/** Build a segment.
* @param start start point of the segment
@@ -45,25 +41,6 @@ class Segment implements Comparable<Segm
this.start = start;
this.end = end;
this.line = line;
- sortingKey = (start == null) ?
- new OrderedTuple(Double.NEGATIVE_INFINITY,
Double.NEGATIVE_INFINITY) :
- new OrderedTuple(start.getX(), start.getY());
- }
-
- /** Build a dummy segment.
- * <p>
- * The object built is not a real segment, only the sorting key is used to
- * allow searching in the neighborhood of a point. This is an horrible
hack ...
- * </p>
- * @param start start point of the segment
- * @param dx abscissa offset from the start point
- * @param dy ordinate offset from the start point
- */
- public Segment(final Vector2D start, final double dx, final double dy) {
- this.start = null;
- this.end = null;
- this.line = null;
- sortingKey = new OrderedTuple(start.getX() + dx, start.getY() + dy);
}
/** Get the start point of the segment.
@@ -87,27 +64,4 @@ class Segment implements Comparable<Segm
return line;
}
- /** {@inheritDoc} */
- public int compareTo(final Segment o) {
- return sortingKey.compareTo(o.sortingKey);
- }
-
- /** {@inheritDoc} */
- @Override
- public boolean equals(final Object other) {
- if (this == other) {
- return true;
- } else if (other instanceof Segment) {
- return compareTo((Segment) other) == 0;
- } else {
- return false;
- }
- }
-
- /** {@inheritDoc} */
- @Override
- public int hashCode() {
- return start.hashCode() ^ end.hashCode() ^ line.hashCode() ^
sortingKey.hashCode();
- }
-
}
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/SubLine.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/SubLine.java?rev=1137749&r1=1137748&r2=1137749&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/SubLine.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math/geometry/euclidean/twod/SubLine.java
Mon Jun 20 19:11:43 2011
@@ -56,6 +56,13 @@ public class SubLine extends AbstractSub
super(new Line(start, end), buildIntervalSet(start, end));
}
+ /** Create a sub-line from a segment.
+ * @param segment single segment forming the sub-line
+ */
+ public SubLine(final Segment segment) {
+ super(segment.getLine(), buildIntervalSet(segment.getStart(),
segment.getEnd()));
+ }
+
/** Get the endpoints of the sub-line.
* <p>
* A subline may be any arbitrary number of disjoints segments, so the
endpoints
@@ -70,16 +77,16 @@ public class SubLine extends AbstractSub
* </p>
* @return list of segments endpoints
*/
- public List<Vector2D[]> getSegments() {
+ public List<Segment> getSegments() {
final Line line = (Line) getHyperplane();
final List<Interval> list = ((IntervalsSet)
getRemainingRegion()).asList();
- final List<Vector2D[]> segments = new ArrayList<Vector2D[]>();
+ final List<Segment> segments = new ArrayList<Segment>();
for (final Interval interval : list) {
final Vector2D start = line.toSpace(new
Vector1D(interval.getLower()));
final Vector2D end = line.toSpace(new
Vector1D(interval.getUpper()));
- segments.add(new Vector2D[] { start, end });
+ segments.add(new Segment(start, end, line));
}
return segments;
Modified:
commons/proper/math/trunk/src/test/java/org/apache/commons/math/geometry/euclidean/twod/SubLineTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/geometry/euclidean/twod/SubLineTest.java?rev=1137749&r1=1137748&r2=1137749&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math/geometry/euclidean/twod/SubLineTest.java
(original)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math/geometry/euclidean/twod/SubLineTest.java
Mon Jun 20 19:11:43 2011
@@ -28,35 +28,36 @@ public class SubLineTest {
@Test
public void testEndPoints() {
- SubLine sub = new SubLine(new Vector2D(-1, -7), new Vector2D(7, -1));
- List<Vector2D[]> segments = sub.getSegments();
+ Vector2D p1 = new Vector2D(-1, -7);
+ Vector2D p2 = new Vector2D(7, -1);
+ Segment segment = new Segment(p1, p2, new Line(p1, p2));
+ SubLine sub = new SubLine(segment);
+ List<Segment> segments = sub.getSegments();
Assert.assertEquals(1, segments.size());
- Assert.assertEquals(-1, segments.get(0)[0].getX(), 1.0e-10);
- Assert.assertEquals(-7, segments.get(0)[0].getY(), 1.0e-10);
- Assert.assertEquals( 7, segments.get(0)[1].getX(), 1.0e-10);
- Assert.assertEquals(-1, segments.get(0)[1].getY(), 1.0e-10);
+ Assert.assertEquals(0.0, new Vector2D(-1,
-7).distance(segments.get(0).getStart()), 1.0e-10);
+ Assert.assertEquals(0.0, new Vector2D( 7,
-1).distance(segments.get(0).getEnd()), 1.0e-10);
}
@Test
public void testNoEndPoints() {
SubLine wholeLine = new Line(new Vector2D(-1, 7), new Vector2D(7,
1)).wholeHyperplane();
- List<Vector2D[]> segments = wholeLine.getSegments();
+ List<Segment> segments = wholeLine.getSegments();
Assert.assertEquals(1, segments.size());
- Assert.assertTrue(Double.isInfinite(segments.get(0)[0].getX()) &&
- segments.get(0)[0].getX() < 0);
- Assert.assertTrue(Double.isInfinite(segments.get(0)[0].getY()) &&
- segments.get(0)[0].getY() > 0);
- Assert.assertTrue(Double.isInfinite(segments.get(0)[1].getX()) &&
- segments.get(0)[1].getX() > 0);
- Assert.assertTrue(Double.isInfinite(segments.get(0)[1].getY()) &&
- segments.get(0)[1].getY() < 0);
+ Assert.assertTrue(Double.isInfinite(segments.get(0).getStart().getX())
&&
+ segments.get(0).getStart().getX() < 0);
+ Assert.assertTrue(Double.isInfinite(segments.get(0).getStart().getY())
&&
+ segments.get(0).getStart().getY() > 0);
+ Assert.assertTrue(Double.isInfinite(segments.get(0).getEnd().getX()) &&
+ segments.get(0).getEnd().getX() > 0);
+ Assert.assertTrue(Double.isInfinite(segments.get(0).getEnd().getY()) &&
+ segments.get(0).getEnd().getY() < 0);
}
@Test
public void testNoSegments() {
SubLine empty = new SubLine(new Line(new Vector2D(-1, -7), new
Vector2D(7, -1)),
new
RegionFactory<Euclidean1D>().getComplement(new IntervalsSet()));
- List<Vector2D[]> segments = empty.getSegments();
+ List<Segment> segments = empty.getSegments();
Assert.assertEquals(0, segments.size());
}
@@ -65,7 +66,7 @@ public class SubLineTest {
SubLine twoSubs = new SubLine(new Line(new Vector2D(-1, -7), new
Vector2D(7, -1)),
new RegionFactory<Euclidean1D>().union(new
IntervalsSet(1, 2),
new
IntervalsSet(3, 4)));
- List<Vector2D[]> segments = twoSubs.getSegments();
+ List<Segment> segments = twoSubs.getSegments();
Assert.assertEquals(2, segments.size());
}
@@ -73,28 +74,26 @@ public class SubLineTest {
public void testHalfInfiniteNeg() {
SubLine empty = new SubLine(new Line(new Vector2D(-1, -7), new
Vector2D(7, -1)),
new IntervalsSet(Double.NEGATIVE_INFINITY,
0.0));
- List<Vector2D[]> segments = empty.getSegments();
+ List<Segment> segments = empty.getSegments();
Assert.assertEquals(1, segments.size());
- Assert.assertTrue(Double.isInfinite(segments.get(0)[0].getX()) &&
- segments.get(0)[0].getX() < 0);
- Assert.assertTrue(Double.isInfinite(segments.get(0)[0].getY()) &&
- segments.get(0)[0].getY() < 0);
- Assert.assertEquals( 3, segments.get(0)[1].getX(), 1.0e-10);
- Assert.assertEquals(-4, segments.get(0)[1].getY(), 1.0e-10);
+ Assert.assertTrue(Double.isInfinite(segments.get(0).getStart().getX())
&&
+ segments.get(0).getStart().getX() < 0);
+ Assert.assertTrue(Double.isInfinite(segments.get(0).getStart().getY())
&&
+ segments.get(0).getStart().getY() < 0);
+ Assert.assertEquals(0.0, new Vector2D(3,
-4).distance(segments.get(0).getEnd()), 1.0e-10);
}
@Test
public void testHalfInfinitePos() {
SubLine empty = new SubLine(new Line(new Vector2D(-1, -7), new
Vector2D(7, -1)),
new IntervalsSet(0.0,
Double.POSITIVE_INFINITY));
- List<Vector2D[]> segments = empty.getSegments();
+ List<Segment> segments = empty.getSegments();
Assert.assertEquals(1, segments.size());
- Assert.assertEquals( 3, segments.get(0)[0].getX(), 1.0e-10);
- Assert.assertEquals(-4, segments.get(0)[0].getY(), 1.0e-10);
- Assert.assertTrue(Double.isInfinite(segments.get(0)[1].getX()) &&
- segments.get(0)[1].getX() > 0);
- Assert.assertTrue(Double.isInfinite(segments.get(0)[1].getY()) &&
- segments.get(0)[1].getY() > 0);
+ Assert.assertEquals(0.0, new Vector2D(3,
-4).distance(segments.get(0).getStart()), 1.0e-10);
+ Assert.assertTrue(Double.isInfinite(segments.get(0).getEnd().getX()) &&
+ segments.get(0).getEnd().getX() > 0);
+ Assert.assertTrue(Double.isInfinite(segments.get(0).getEnd().getY()) &&
+ segments.get(0).getEnd().getY() > 0);
}
@Test
