[Geom4j-developer] SF.net SVN: geom4j:[26] trunk/src/net/sourceforge/geom4j
Status: Pre-Alpha
Brought to you by:
skhenkin
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. |