[Geom4j-developer] SF.net SVN: geom4j:[26] trunk/src/net/sourceforge/geom4j
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[26] trunk/src/net/sourceforge/geom4j
|
From: <skh...@us...> - 2010-01-12 22:49:16
|
Revision: 26
http://geom4j.svn.sourceforge.net/geom4j/?rev=26&view=rev
Author: skhenkin
Date: 2010-01-12 22:49:05 +0000 (Tue, 12 Jan 2010)
Log Message:
-----------
Method for finding the middle point of a segment.
Fix for Bentley-Ottman algorithm for segment intersections.
Triangulation.fit() improved.
Modified Paths:
--------------
trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java
trunk/src/net/sourceforge/geom4j/Segment.java
trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java
trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java
trunk/src/net/sourceforge/geom4j/SegmentSet.java
trunk/src/net/sourceforge/geom4j/SegmentTest.java
trunk/src/net/sourceforge/geom4j/Triangulation.java
trunk/src/net/sourceforge/geom4j/TriangulationTest.java
Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2010-01-09 21:20:22 UTC (rev 25)
+++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2010-01-12 22:49:05 UTC (rev 26)
@@ -47,7 +47,7 @@
new Point(3, 3),
new Point(3, 4));
Triangulation triangulation = polygon.triangulate(PolygonTriangulationAlgorithm.CONVEX);
- assertTrue(triangulation.fits(polygon));
+ assertFalse(triangulation.fits(polygon));
}
}
Modified: trunk/src/net/sourceforge/geom4j/Segment.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Segment.java 2010-01-09 21:20:22 UTC (rev 25)
+++ trunk/src/net/sourceforge/geom4j/Segment.java 2010-01-12 22:49:05 UTC (rev 26)
@@ -296,4 +296,12 @@
}
}
}
+
+ /**
+ * Get middle point of the segment
+ */
+ public Point getMiddlePoint() {
+ return new Point((startPoint.getX() + endPoint.getX()) / 2,
+ (startPoint.getY() + endPoint.getY()) / 2);
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2010-01-09 21:20:22 UTC (rev 25)
+++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2010-01-12 22:49:05 UTC (rev 26)
@@ -146,10 +146,11 @@
*/
protected void addIntersectionEvent(
SmartQueue<Event> eventQueue, Segment seg1,
- Segment seg2, Point curPoint) {
+ Segment seg2, Point curPoint, boolean isLeftPoint) {
if (seg1 != null && seg2 != null) {
for (Point p : seg1.intersects(seg2).getPoints()) {
- if (p.getX() >= curPoint.getX()) {
+ if (p.getX() >= curPoint.getX() && isLeftPoint
+ || p.getX() > curPoint.getX() && !isLeftPoint) {
IntersectionEvent templateEvent = new IntersectionEvent(p, seg1, seg2, sweepLineComparator);
Event existingEvent = eventQueue.find(templateEvent);
if (existingEvent != null && existingEvent instanceof IntersectionEvent) {
@@ -191,9 +192,9 @@
Segment segAfter = sweepLine.next(segment);
sweepLineComparator.setBefore(false);
addIntersectionEvent(eventQueue, segAfter, segment,
- segment.getLeftPoint());
+ segment.getLeftPoint(), true);
addIntersectionEvent(eventQueue, segment, segBefore,
- segment.getLeftPoint());
+ segment.getLeftPoint(), true);
}
@Override
@@ -244,7 +245,7 @@
Segment segBefore = sweepLine.previous(segment);
Segment segAfter = sweepLine.next(segment);
addIntersectionEvent(eventQueue, segAfter, segBefore,
- segment.getRightPoint());
+ segment.getRightPoint(), false);
sweepLine.remove(segment);
}
@@ -312,8 +313,8 @@
Segment sBelow = getFirstSegment();
sweepLine.revert(sBelow, sAbove);
sweepLineComparator.setBefore(false);
- addIntersectionEvent(eventQueue, sAbove, sweepLine.previous(sAbove), p);
- addIntersectionEvent(eventQueue, sweepLine.next(sBelow), sBelow, p);
+ addIntersectionEvent(eventQueue, sAbove, sweepLine.previous(sAbove), p, true);
+ addIntersectionEvent(eventQueue, sweepLine.next(sBelow), sBelow, p, true);
}
private Segment getLastSegment() {
Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-09 21:20:22 UTC (rev 25)
+++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-12 22:49:05 UTC (rev 26)
@@ -208,4 +208,23 @@
PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN);
assertEquals(naiveSet, boSet);
}
+
+ @Test
+ public void testBentleyOttmanSpecialCase() {
+ double[][] coords = new double[][] {
+ //{ 0, 0, 20, 40},
+ {20, 40, 40, 10},
+ //{ 0, 0, 20, 20},
+ {20, 20, 40, 10},
+ { 0, 0, 40, 10}
+ };
+ SegmentSet ss = new SegmentSet();
+ for (int i = 0; i < coords.length; i++) {
+ ss.add(new Segment(new Point(coords[i][0], coords[i][1]),
+ new Point(coords[i][2], coords[i][3])));
+ }
+ PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE);
+ PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN);
+ assertEquals(naiveSet, boSet);
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/SegmentSet.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/SegmentSet.java 2010-01-09 21:20:22 UTC (rev 25)
+++ trunk/src/net/sourceforge/geom4j/SegmentSet.java 2010-01-12 22:49:05 UTC (rev 26)
@@ -16,6 +16,7 @@
package net.sourceforge.geom4j;
import java.util.Arrays;
+import java.util.Collection;
/**
* A set of segments
@@ -29,14 +30,22 @@
}
public SegmentSet(Segment... segments) {
- super(Arrays.asList(segments));
+ this(Arrays.asList(segments));
}
+ public SegmentSet(Collection<Segment> segments) {
+ super(segments);
+ }
+
@Override
public SegmentSet add(Segment f) {
return (SegmentSet) super.add(f);
}
+ public SegmentSet add(SegmentSet segmentSet) {
+ return (SegmentSet) super.add(segmentSet);
+ }
+
/**
* Get all intersections between the segments of this set.
* @param alg intersection algorithm to use
Modified: trunk/src/net/sourceforge/geom4j/SegmentTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/SegmentTest.java 2010-01-09 21:20:22 UTC (rev 25)
+++ trunk/src/net/sourceforge/geom4j/SegmentTest.java 2010-01-12 22:49:05 UTC (rev 26)
@@ -116,5 +116,11 @@
Segment s1 = new Segment(p1, p2);
Segment s2 = new Segment(p2, p1);
assertEquals(s1.hashCode(), s2.hashCode());
- }
+ }
+
+ @Test
+ public void testMiddlePoint() {
+ assertEquals(new Point(5, 5), new Segment(new Point(3, 8), new Point(7, 2)).getMiddlePoint());
+ assertEquals(new Point(0, 0), new Segment(new Point(-30, -80), new Point(30, 80)).getMiddlePoint());
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/Triangulation.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Triangulation.java 2010-01-09 21:20:22 UTC (rev 25)
+++ trunk/src/net/sourceforge/geom4j/Triangulation.java 2010-01-12 22:49:05 UTC (rev 26)
@@ -33,7 +33,9 @@
* 2. The vertices of triangulation and polygon match.
* 3. Every segment in triangulation comes at most twice.
* 4. Segments that come once form the polygon.
- * 5. Other segments don't intersect in points other than polygon vertices.
+ * 5. All segments don't intersect in points other than polygon vertices.
+ * 6. Segments that come twice lie on the outside of the polygon.
+ * Actually we test if their middle points lie on the outside.
*/
// 1
if (size() != polygon.getVertexCount() - 2) {
@@ -64,9 +66,16 @@
return false;
}
// 5
- if (!new PointSet(polygon.getVertices()).contains(doubles.getAllIntersectionPoints())) {
+ if (!new PointSet(polygon.getVertices()).contains(
+ new SegmentSet().add(singles).add(doubles).getAllIntersectionPoints())) {
return false;
}
+ // 6
+ for (Segment s: doubles) {
+ if (!s.getMiddlePoint().isInside(polygon)) {
+ return false;
+ }
+ }
// everything is fine
return true;
}
Modified: trunk/src/net/sourceforge/geom4j/TriangulationTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2010-01-09 21:20:22 UTC (rev 25)
+++ trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2010-01-12 22:49:05 UTC (rev 26)
@@ -54,4 +54,47 @@
.add(new Triangle(new Point(30, 10), new Point(0, 40), new Point(60, 70)));
assertTrue(triangulation.fits(polygon));
}
+
+ @Test
+ public void testIncorrectFitting1() {
+ Polygon polygon = new Polygon(
+ new Point(0, 0),
+ new Point(20, 40),
+ new Point(40, 10),
+ new Point(20, 20));
+ Triangulation triangulation = new Triangulation();
+ triangulation.add(new Triangle(new Point(0, 0), new Point(20, 40), new Point(40, 10)))
+ .add(new Triangle(new Point(0, 0), new Point(20, 20), new Point(40, 10)));
+ assertFalse(triangulation.fits(polygon));
+ }
+
+ @Test
+ public void testIncorrectFitting2() {
+ Polygon polygon = new Polygon(
+ new Point(0, 0),
+ new Point(10, 40),
+ new Point(50, 30),
+ new Point(20, 0),
+ new Point(10, 20));
+ Triangulation triangulation = new Triangulation();
+ triangulation.add(new Triangle(new Point(0, 0), new Point(10, 40), new Point(50, 30)))
+ .add(new Triangle(new Point(0, 0), new Point(50, 30), new Point(20, 0)))
+ .add(new Triangle(new Point(0, 0), new Point(10, 20), new Point(20, 0)));
+ assertFalse(triangulation.fits(polygon));
+ }
+
+ @Test
+ public void testIncorrectFitting3() {
+ Polygon polygon = new Polygon(
+ new Point(0, 0),
+ new Point(10, 40),
+ new Point(50, 30),
+ new Point(20, 0),
+ new Point(10, 20));
+ Triangulation triangulation = new Triangulation();
+ triangulation.add(new Triangle(new Point(0, 0), new Point(10, 40), new Point(50, 30)))
+ .add(new Triangle(new Point(0, 0), new Point(50, 30), new Point(10, 20)))
+ .add(new Triangle(new Point(20, 0), new Point(10, 20), new Point(50, 30)));
+ assertFalse(triangulation.fits(polygon));
+ }
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
