geom4j-developer Mailing List for geom4j
Status: Pre-Alpha
Brought to you by:
skhenkin
You can subscribe to this list here.
2009 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
(3) |
Dec
(12) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2010 |
Jan
(10) |
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
From: <skh...@us...> - 2010-01-17 09:24:11
|
Revision: 34 http://geom4j.svn.sourceforge.net/geom4j/?rev=34&view=rev Author: skhenkin Date: 2010-01-17 09:24:03 +0000 (Sun, 17 Jan 2010) Log Message: ----------- ToDo item added for improving ear clipping method performance Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/Polygon.java trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java Modified: trunk/src/net/sourceforge/geom4j/Polygon.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-17 08:59:01 UTC (rev 33) +++ trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-17 09:24:03 UTC (rev 34) @@ -19,7 +19,6 @@ import java.util.Collection; import java.util.Collections; import java.util.Iterator; -import java.util.LinkedList; import java.util.List; import net.sourceforge.geom4j.util.Utils; Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-17 08:59:01 UTC (rev 33) +++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-17 09:24:03 UTC (rev 34) @@ -61,7 +61,10 @@ * the conditions) and repeating until there is only one triangle left. */ static PolygonTriangulationAlgorithm EAR_CLIPPING = new PolygonTriangulationAlgorithm() { - @Override + /* TODO: improve it to be really O(n*n) + * keeping the lists of convex and non-convex vertices separate + */ + @Override public Triangulation run(Polygon polygon) { Triangulation triangulation = new Triangulation(); while (polygon.getVertexCount() >= 3) { This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2010-01-17 08:59:09
|
Revision: 33 http://geom4j.svn.sourceforge.net/geom4j/?rev=33&view=rev Author: skhenkin Date: 2010-01-17 08:59:01 +0000 (Sun, 17 Jan 2010) Log Message: ----------- Bug in Point.isInside() fixed. An initial version of ear clipping polygon triangulation algorithm implemented. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/Point.java trunk/src/net/sourceforge/geom4j/PointTest.java trunk/src/net/sourceforge/geom4j/Polygon.java trunk/src/net/sourceforge/geom4j/PolygonTest.java trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java Modified: trunk/src/net/sourceforge/geom4j/Point.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Point.java 2010-01-16 23:19:49 UTC (rev 32) +++ trunk/src/net/sourceforge/geom4j/Point.java 2010-01-17 08:59:01 UTC (rev 33) @@ -183,6 +183,10 @@ * and http://erich.realtimerendering.com/ptinpoly/ */ public boolean isInside(Polygon p) { + if (p.contains(this)) { + // the point lies on border of the polygon + return true; + } // Construct a "ray" to test crossings with. This is actually a long enough segment double maxX = getX() + 1; for (Point pt: p.getVertices()) { Modified: trunk/src/net/sourceforge/geom4j/PointTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointTest.java 2010-01-16 23:19:49 UTC (rev 32) +++ trunk/src/net/sourceforge/geom4j/PointTest.java 2010-01-17 08:59:01 UTC (rev 33) @@ -88,4 +88,15 @@ assertTrue(new Point(3, 1).isInside(p)); assertFalse(new Point(1, 0).isInside(p)); } + + + @Test + public void testPointInPolygonSpecialCase1() { + Polygon poly = new Polygon( + new Point(2, 0), + new Point(8, 3), + new Point(7, 5)); + Point pt = new Point(4, 2); + assertTrue(pt.isInside(poly)); + } } Modified: trunk/src/net/sourceforge/geom4j/Polygon.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 23:19:49 UTC (rev 32) +++ trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-17 08:59:01 UTC (rev 33) @@ -19,6 +19,7 @@ import java.util.Collection; import java.util.Collections; import java.util.Iterator; +import java.util.LinkedList; import java.util.List; import net.sourceforge.geom4j.util.Utils; @@ -225,23 +226,31 @@ return Math.abs(s); } - public Point getVertex(int i) { + public final Point getVertex(int i) { return vertices.get(i); } - public Point getNextVertex(int i) { - return getVertex(i == vertices.size()-1 ? 0 : i+1); + public final int getNextVertexIndex(int i) { + return i == vertices.size()-1 ? 0 : i+1; } - public Point getPreviousVertex(int i) { - return getVertex(i == 0 ? vertices.size()-1 : i-1); + public final Point getNextVertex(int i) { + return getVertex(getNextVertexIndex(i)); } - public Point getFirstVertex() { + public final int getPreviousVertexIndex(int i) { + return i == 0 ? vertices.size()-1 : i-1; + } + + public final Point getPreviousVertex(int i) { + return getVertex(getPreviousVertexIndex(i)); + } + + public final Point getFirstVertex() { return getVertex(0); } - public Point getLastVertex() { + public final Point getLastVertex() { return getVertex(getVertexCount()-1); } @@ -303,11 +312,27 @@ /** Check if the vertex number i is convex */ public boolean isConvexVertex(int i) { - return Utils.isNonRightTurn(getPreviousVertex(i), getVertex(i), getNextVertex(i)); + return !Utils.isNonLeftTurn(getPreviousVertex(i), getVertex(i), getNextVertex(i)); } /** Check if the vertex number i is concave */ public boolean isConcaveVertex(int i) { - return !isConvexVertex(i); + return !Utils.isNonRightTurn(getPreviousVertex(i), getVertex(i), getNextVertex(i)); } + + /** + * Create a polygon which is the same as given but without a vertex + * with the specified index. + */ + public Polygon withoutVertex(int vertexIndex) { + int n = this.vertices.size(); + Point[] vertices = new Point[n-1]; + for (int i = 0; i < vertexIndex; i++) { + vertices[i] = this.vertices.get(i); + } + for (int i = vertexIndex + 1; i < n; i++) { + vertices[i-1] = this.vertices.get(i); + } + return new Polygon(vertices); + } } Modified: trunk/src/net/sourceforge/geom4j/PolygonTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 23:19:49 UTC (rev 32) +++ trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-17 08:59:01 UTC (rev 33) @@ -195,7 +195,8 @@ assertTrue(p.isConvexVertex(0)); assertTrue(p.isConvexVertex(1)); assertTrue(p.isConvexVertex(2)); - assertTrue(p.isConvexVertex(3)); + assertFalse(p.isConvexVertex(3)); + assertFalse(p.isConcaveVertex(3)); assertTrue(p.isConvexVertex(4)); assertTrue(p.isConcaveVertex(5)); assertTrue(p.isConvexVertex(6)); @@ -225,5 +226,21 @@ assertEquals(new Point(8, 8), p.getPreviousVertex(7)); assertEquals(new Point(1, 4), p.getNextVertex(7)); } + + @Test + public void testWithoutVertex() { + Polygon p1 = new Polygon( + new Point(0, 0), + new Point(100, 0), + new Point(100, 100), + new Point(50, 100), + new Point(0, 50)); + Polygon p2 = new Polygon( + new Point(0, 0), + new Point(100, 0), + new Point(50, 100), + new Point(0, 50)); + assertEquals(p2, p1.withoutVertex(2)); + } } Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-16 23:19:49 UTC (rev 32) +++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-17 08:59:01 UTC (rev 33) @@ -64,8 +64,47 @@ @Override public Triangulation run(Polygon polygon) { Triangulation triangulation = new Triangulation(); + while (polygon.getVertexCount() >= 3) { + int earIndex = findEarVertexIndex(polygon); + triangulation.add(new Triangle( + polygon.getPreviousVertex(earIndex), + polygon.getVertex(earIndex), + polygon.getNextVertex(earIndex))); + polygon = polygon.withoutVertex(earIndex); + } return triangulation; } + + /** + * Find the index of an ear vertex in polygon + */ + private int findEarVertexIndex(Polygon polygon) { + int n = polygon.getVertexCount(); + for (int i = 0; i < n; i++) { + if (polygon.isConvexVertex(i)) { + // check if a concave vertex is inside the triangle + boolean concaveVertexInside = false; + for (int j = 0; j < n ; j++) { + if (j == i || j == polygon.getPreviousVertexIndex(i) + || j == polygon.getNextVertexIndex(i)) { + continue; // skip vertices that form current triangle + } + if (!polygon.isConvexVertex(j)){ + if (polygon.getVertex(j).isInside(new Triangle(polygon.getPreviousVertex(i), + polygon.getVertex(i), + polygon.getNextVertex(i)))) { + concaveVertexInside = true; + break; + } + } + } + if (!concaveVertexInside) { + return i; + } + } + } + throw new IllegalArgumentException("No ear can be found in polygon " + polygon); + } }; } Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2010-01-16 23:19:49 UTC (rev 32) +++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2010-01-17 08:59:01 UTC (rev 33) @@ -36,7 +36,7 @@ } @Test - public void testX() { + public void testConvexFailure() { Polygon polygon = new Polygon( new Point(1, 1), new Point(3, 2), @@ -50,4 +50,29 @@ assertFalse(triangulation.fits(polygon)); } + @Test + public void testEarClipping() { + Polygon polygon = new Polygon( + new Point(1, 1), + new Point(3, 2), + new Point(2, 0), + new Point(8, 3), + new Point(7, 5), + new Point(4, 2), + new Point(3, 3), + new Point(3, 4)); + Triangulation triangulation = polygon.triangulate(PolygonTriangulationAlgorithm.EAR_CLIPPING); + assertTrue(triangulation.fits(polygon)); + } + + @Test + public void testEarClippingPrimitive() { + Polygon polygon = new Polygon( + new Point(1, 1), + new Point(2, 0), + new Point(3, 2)); + Triangulation triangulation = polygon.triangulate(PolygonTriangulationAlgorithm.EAR_CLIPPING); + assertTrue(triangulation.fits(polygon)); + } + } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2010-01-16 23:19:57
|
Revision: 32 http://geom4j.svn.sourceforge.net/geom4j/?rev=32&view=rev Author: skhenkin Date: 2010-01-16 23:19:49 +0000 (Sat, 16 Jan 2010) Log Message: ----------- Polygon class refactored to store vertices in counter-clockwise traversal order Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java trunk/src/net/sourceforge/geom4j/Polygon.java trunk/src/net/sourceforge/geom4j/PolygonTest.java Added Paths: ----------- trunk/src/net/sourceforge/geom4j/util/Utils.java trunk/src/net/sourceforge/geom4j/util/UtilsTest.java Modified: trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2010-01-16 11:32:17 UTC (rev 31) +++ trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2010-01-16 23:19:49 UTC (rev 32) @@ -21,6 +21,8 @@ import java.util.LinkedList; import java.util.List; +import net.sourceforge.geom4j.util.Utils; + /** * An algorithm to construct convex hull (convex envelope) for a point set. * The convex hull is represented as a polygon. @@ -138,7 +140,7 @@ int m = 2; // a pointer to the top stack element for (int i = 2; i < points.size(); i++) { // test each point of the set - while (nonLeftTurn(stack[m-1], stack[m], points.get(i))) { + while (Utils.isNonLeftTurn(stack[m-1], stack[m], points.get(i))) { /* rollback if the turn is non-left, i.e. it breaks the rule for a convex polygon */ m--; @@ -151,14 +153,6 @@ hull.add(stack[i]); } return new Polygon(hull); - } - - /** Test if p1-p2-p3 form a non-left turn, i.e. straight line or right turn */ - private boolean nonLeftTurn(Point p1, Point p2, Point p3) { - Vector v1 = new Vector(p1, p2); - Vector v2 = new Vector(p2, p3); - return v1.crossProduct(v2) <= 0; - } - + } }; } Modified: trunk/src/net/sourceforge/geom4j/Polygon.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 11:32:17 UTC (rev 31) +++ trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 23:19:49 UTC (rev 32) @@ -17,9 +17,12 @@ import java.util.ArrayList; import java.util.Collection; +import java.util.Collections; import java.util.Iterator; import java.util.List; +import net.sourceforge.geom4j.util.Utils; + /** * A polygon is a closed shape in a plane. * This is immutable class. @@ -40,6 +43,7 @@ for (Point vertex: vertices) { this.vertices.add(vertex); } + orderCounterClockwise(); } public Polygon(Collection<Point> vertices) { @@ -196,21 +200,13 @@ /** Check if the polygon is convex or not */ public boolean isConvex() { - if (vertices.size() < 3) return true; // it's not really a polygon - // convex polygon <=> all cross products of its sides are of the same sign - Iterator<Point> i = vertices.iterator(); - Point p1 = vertices.get(getVertexCount()-1); - Point p2 = i.next(); - Vector v1 = new Vector(vertices.get(getVertexCount()-2), p1); - Vector v2 = new Vector(p1, p2); - double sign0 = Math.signum(v1.crossProduct(v2)); - while (i.hasNext()) { - p1 = p2; - p2 = i.next(); - v1 = v2; - v2 = new Vector(p1, p2); - double sign = Math.signum(v1.crossProduct(v2)); - if (sign0*sign < 0) { + /* check if there's no right turns in counter-clockwise traversal + * of the polygon vertices + */ + int n = vertices.size(); + for (int i = 0; i < n; i++) { + if (!Utils.isNonRightTurn(getPreviousVertex(i), + getVertex(i), getNextVertex(i))) { return false; } } @@ -233,6 +229,14 @@ return vertices.get(i); } + public Point getNextVertex(int i) { + return getVertex(i == vertices.size()-1 ? 0 : i+1); + } + + public Point getPreviousVertex(int i) { + return getVertex(i == 0 ? vertices.size()-1 : i-1); + } + public Point getFirstVertex() { return getVertex(0); } @@ -267,18 +271,39 @@ public Triangulation triangulate(PolygonTriangulationAlgorithm alg) { return alg.run(this); } - + + /** Order vertices so that the traversal order is counter clockwise */ + private void orderCounterClockwise() { + if (isClockwise()) { + Collections.reverse(vertices); + } + } + /** * Check if the traversal order of the vertices in the polygon is clockwise. * @return true for clockwise order and false for counter-clockwise */ - public boolean isClockwise() { - return true; // TODO: implement + boolean isClockwise() { + int n = vertices.size(); + // find rightmost vertex + int maxIdx = 0; + double maxX = Double.MIN_VALUE; + for (int i = 0; i < n; i++) { + if (vertices.get(i).getX() > maxX) { + maxIdx = i; + maxX = vertices.get(i).getX(); + } + } + // check if the the turn at this point is wrong + return isConcaveVertex(maxIdx) + || getPreviousVertex(maxIdx).getX() == getVertex(maxIdx).getX() + && getVertex(maxIdx).getX() == getNextVertex(maxIdx).getX() + && getPreviousVertex(maxIdx).getY() < getNextVertex(maxIdx).getY(); } /** Check if the vertex number i is convex */ public boolean isConvexVertex(int i) { - return true; // TODO: implement + return Utils.isNonRightTurn(getPreviousVertex(i), getVertex(i), getNextVertex(i)); } /** Check if the vertex number i is concave */ Modified: trunk/src/net/sourceforge/geom4j/PolygonTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 11:32:17 UTC (rev 31) +++ trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 23:19:49 UTC (rev 32) @@ -33,13 +33,13 @@ public void setUp() throws Exception { p = new Polygon( new Point(1, 4), - new Point(4, 8), + new Point(3, 4), + new Point(3, 6), + new Point(7, 3), + new Point(11, 6), + new Point(8, 10), new Point(8, 8), - new Point(8, 10), - new Point(11, 6), - new Point(7, 3), - new Point(3, 6), - new Point(3, 4)); + new Point(4, 8)); } @Test @@ -158,4 +158,72 @@ new Point(20, 20)) .isSimple()); } + + @Test + public void testIsClockwise() { + assertFalse(new Polygon( + new Point(4, 4), + new Point(5, 3), + new Point(6, 4), + new Point(5, 5)).isClockwise()); + assertFalse(new Polygon( + new Point(4, 4), + new Point(5, 5), + new Point(6, 4), + new Point(5, 3)).isClockwise()); + assertFalse(new Polygon( + new Point(4, 4), + new Point(5, 3), + new Point(6, 3), + new Point(6, 4), + new Point(6, 5), + new Point(5, 5)).isClockwise()); + } + + @Test + public void testConvexAndConcaveVertex1() { + Polygon p = new Polygon( + new Point(4, 4), //0 + new Point(5, 3), //1 + new Point(6, 3), //2 + new Point(6, 4), //3 + new Point(6, 5), //4 + new Point(5, 6), //5 + new Point(6, 7), //6 + new Point(5, 7), //7 + new Point(4, 6)); //8 + assertTrue(p.isConvexVertex(0)); + assertTrue(p.isConvexVertex(1)); + assertTrue(p.isConvexVertex(2)); + assertTrue(p.isConvexVertex(3)); + assertTrue(p.isConvexVertex(4)); + assertTrue(p.isConcaveVertex(5)); + assertTrue(p.isConvexVertex(6)); + assertTrue(p.isConvexVertex(7)); + assertTrue(p.isConvexVertex(8)); + + } + + @Test + public void testConvexAndConcaveVertex2() { + assertTrue(p.isConvexVertex(0)); + assertTrue(p.isConvexVertex(1)); + assertTrue(p.isConcaveVertex(2)); + assertTrue(p.isConvexVertex(3)); + assertTrue(p.isConvexVertex(4)); + assertTrue(p.isConvexVertex(5)); + assertTrue(p.isConcaveVertex(6)); + assertTrue(p.isConvexVertex(7)); + } + + @Test + public void testPreviousAndNextVertex() { + assertEquals(new Point(4, 8), p.getPreviousVertex(0)); + assertEquals(new Point(3, 4), p.getNextVertex(0)); + assertEquals(new Point(7, 3), p.getPreviousVertex(4)); + assertEquals(new Point(8, 10), p.getNextVertex(4)); + assertEquals(new Point(8, 8), p.getPreviousVertex(7)); + assertEquals(new Point(1, 4), p.getNextVertex(7)); + } } + Added: trunk/src/net/sourceforge/geom4j/util/Utils.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/Utils.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/Utils.java 2010-01-16 23:19:49 UTC (rev 32) @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j.util; + +import net.sourceforge.geom4j.Point; +import net.sourceforge.geom4j.Vector; + +/** + * Miscellaneous utility functions. + * + * @author Sergey Khenkin + * @since 1.0.0 + */ +public class Utils { + /** + * Test if p1-p2-p3 form a non-left turn, i.e. straight line or right turn + */ + public static boolean isNonLeftTurn(Point p1, Point p2, Point p3) { + return pointProduct(p1, p2, p3) <= 0; + } + + /** + * Test if p1-p2-p3 form a non-right turn, i.e. straight line or left turn + */ + public static boolean isNonRightTurn(Point p1, Point p2, Point p3) { + return pointProduct(p1, p2, p3) >= 0; + } + + private static double pointProduct(Point p1, Point p2, Point p3) { + Vector v1 = new Vector(p1, p2); + Vector v2 = new Vector(p2, p3); + return v1.crossProduct(v2); + } +} Added: trunk/src/net/sourceforge/geom4j/util/UtilsTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/UtilsTest.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/UtilsTest.java 2010-01-16 23:19:49 UTC (rev 32) @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j.util; + +import net.sourceforge.geom4j.Point; + +import org.junit.Test; +import static net.sourceforge.geom4j.util.Utils.*; +import static org.junit.Assert.*; + +/** + * Tests for miscellaneous utility functions + * + * @author Sergey Khenkin + * @since 1.0.0 + */ +public class UtilsTest { + @Test + public void testNonLeftTurn() { + assertTrue(isNonLeftTurn(new Point(5, 5), new Point(9, 8), new Point(11, 3))); + assertTrue(isNonLeftTurn(new Point(5, 5), new Point(9, 9), new Point(11, 11))); + assertFalse(isNonLeftTurn(new Point(5, 5), new Point(9, 9), new Point(8, 11))); + } + + @Test + public void testNonRightTurn() { + assertFalse(isNonRightTurn(new Point(5, 5), new Point(9, 8), new Point(11, 3))); + assertTrue(isNonRightTurn(new Point(5, 5), new Point(9, 9), new Point(11, 11))); + assertTrue(isNonRightTurn(new Point(5, 5), new Point(9, 9), new Point(8, 11))); + } +} This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2010-01-16 11:32:25
|
Revision: 31 http://geom4j.svn.sourceforge.net/geom4j/?rev=31&view=rev Author: skhenkin Date: 2010-01-16 11:32:17 +0000 (Sat, 16 Jan 2010) Log Message: ----------- Refactoring of the code to remove Polygon.addVertex() method completely. So from now on Polygon is an immutable class. This is also a preparation step for making polygons always counter-clockwise traversed. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java trunk/src/net/sourceforge/geom4j/PointTest.java trunk/src/net/sourceforge/geom4j/Polygon.java trunk/src/net/sourceforge/geom4j/PolygonTest.java trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java trunk/src/net/sourceforge/geom4j/TriangulationTest.java trunk/src/net/sourceforge/geom4j/demo/Demo.java Modified: trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2010-01-16 08:24:36 UTC (rev 30) +++ trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2010-01-16 11:32:17 UTC (rev 31) @@ -18,6 +18,7 @@ import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; +import java.util.LinkedList; import java.util.List; /** @@ -61,13 +62,14 @@ static ConvexHullAlgorithm JARVIS_MARCH = new ConvexHullAlgorithm() { @Override public Polygon run(PointSet ps) { - Polygon hull = new Polygon(); + List<Point> hull = new LinkedList<Point>(); Point pointOnHull = ps.getLeftmost(); + Point firstVertex = pointOnHull; do { - hull.addVertex(pointOnHull); + hull.add(pointOnHull); pointOnHull = getNextPoint(ps, pointOnHull); - } while (!pointOnHull.equals(hull.getFirstVertex())); - return hull; + } while (!pointOnHull.equals(firstVertex)); + return new Polygon(hull); } /* Find the point with the biggest polar angle @@ -143,12 +145,12 @@ } stack[++m] = points.get(i); } - - Polygon hull = new Polygon(); + + List<Point> hull = new LinkedList<Point>(); for (int i = 0; i <= m; i++) { - hull.addVertex(stack[i]); + hull.add(stack[i]); } - return hull; + return new Polygon(hull); } /** Test if p1-p2-p3 form a non-left turn, i.e. straight line or right turn */ Modified: trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java 2010-01-16 08:24:36 UTC (rev 30) +++ trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java 2010-01-16 11:32:17 UTC (rev 31) @@ -52,15 +52,15 @@ ps.add(new Point(11, 4)); ps.add(new Point(9, 2)); - ch = new Polygon(); - ch.addVertex(new Point(5, 1)); - ch.addVertex(new Point(9, 2)); - ch.addVertex(new Point(11, 4)); - ch.addVertex(new Point(10, 5)); - ch.addVertex(new Point(5, 7)); - ch.addVertex(new Point(3, 6)); - ch.addVertex(new Point(2, 4)); - ch.addVertex(new Point(2, 2)); + ch = new Polygon( + new Point(5, 1), + new Point(9, 2), + new Point(11, 4), + new Point(10, 5), + new Point(5, 7), + new Point(3, 6), + new Point(2, 4), + new Point(2, 2)); } Modified: trunk/src/net/sourceforge/geom4j/PointTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointTest.java 2010-01-16 08:24:36 UTC (rev 30) +++ trunk/src/net/sourceforge/geom4j/PointTest.java 2010-01-16 11:32:17 UTC (rev 31) @@ -53,18 +53,18 @@ @Test public void testPointInPolygon() { - Polygon p = new Polygon() - .addVertex(new Point(2, 0)) - .addVertex(new Point(1, 2)) - .addVertex(new Point(2, 5)) - .addVertex(new Point(3, 3)) - .addVertex(new Point(4, 5)) - .addVertex(new Point(5, 3)) - .addVertex(new Point(6, 5)) - .addVertex(new Point(7, 2)) - .addVertex(new Point(6, 1)) - .addVertex(new Point(5, 1)) - .addVertex(new Point(4, 0)); + Polygon p = new Polygon( + new Point(2, 0), + new Point(1, 2), + new Point(2, 5), + new Point(3, 3), + new Point(4, 5), + new Point(5, 3), + new Point(6, 5), + new Point(7, 2), + new Point(6, 1), + new Point(5, 1), + new Point(4, 0)); assertTrue(new Point(6, 4).isInside(p)); assertFalse(new Point(5, 4).isInside(p)); Modified: trunk/src/net/sourceforge/geom4j/Polygon.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 08:24:36 UTC (rev 30) +++ trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 11:32:17 UTC (rev 31) @@ -16,17 +16,18 @@ package net.sourceforge.geom4j; import java.util.ArrayList; +import java.util.Collection; import java.util.Iterator; import java.util.List; /** * A polygon is a closed shape in a plane. + * This is immutable class. * * @author Sergey Khenkin * @since 1.0.0 */ public class Polygon extends BasicFigure { - // TODO: think of making this class also immutable protected List<Point> vertices; @@ -41,11 +42,10 @@ } } - public Polygon addVertex(Point p) { - vertices.add(p); - return this; + public Polygon(Collection<Point> vertices) { + this(vertices.toArray(new Point[0])); } - + /** Get number of polygon's vertices (corners) */ public int getVertexCount() { return vertices.size(); @@ -267,4 +267,22 @@ public Triangulation triangulate(PolygonTriangulationAlgorithm alg) { return alg.run(this); } + + /** + * Check if the traversal order of the vertices in the polygon is clockwise. + * @return true for clockwise order and false for counter-clockwise + */ + public boolean isClockwise() { + return true; // TODO: implement + } + + /** Check if the vertex number i is convex */ + public boolean isConvexVertex(int i) { + return true; // TODO: implement + } + + /** Check if the vertex number i is concave */ + public boolean isConcaveVertex(int i) { + return !isConvexVertex(i); + } } Modified: trunk/src/net/sourceforge/geom4j/PolygonTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 08:24:36 UTC (rev 30) +++ trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 11:32:17 UTC (rev 31) @@ -27,18 +27,19 @@ * @since 1.0.0 */ public class PolygonTest { - Polygon p = new Polygon(); + Polygon p; @Before public void setUp() throws Exception { - p.addVertex(new Point(1, 4)) - .addVertex(new Point(4, 8)) - .addVertex(new Point(8, 8)) - .addVertex(new Point(8, 10)) - .addVertex(new Point(11, 6)) - .addVertex(new Point(7, 3)) - .addVertex(new Point(3, 6)) - .addVertex(new Point(3, 4)); + p = new Polygon( + new Point(1, 4), + new Point(4, 8), + new Point(8, 8), + new Point(8, 10), + new Point(11, 6), + new Point(7, 3), + new Point(3, 6), + new Point(3, 4)); } @Test Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-16 08:24:36 UTC (rev 30) +++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-16 11:32:17 UTC (rev 31) @@ -32,7 +32,8 @@ /** - * Straightforward algorithm for convex polygon triangulation + * Straightforward algorithm for convex polygon triangulation. + * Complexity is O(n) where n is the number of vertices of the polygon. */ static PolygonTriangulationAlgorithm CONVEX = new PolygonTriangulationAlgorithm() { @Override @@ -48,4 +49,23 @@ } }; + /** + * Ear clipping triangulation algorithm for simple polygons without holes. + * Has computational complexity of O(n*n) where n is the number + * of vertices of the polygon. + * The idea of the method is to use the assertion that any simple polygon + * without holes has at least two so called 'ears'. An ear is a triangle + * with two sides on the edge of the polygon and the other one completely + * inside it. The algorithm then consists of finding such an ear, removing + * it from the polygon (which results in a new polygon that still meets + * the conditions) and repeating until there is only one triangle left. + */ + static PolygonTriangulationAlgorithm EAR_CLIPPING = new PolygonTriangulationAlgorithm() { + @Override + public Triangulation run(Polygon polygon) { + Triangulation triangulation = new Triangulation(); + return triangulation; + } + }; + } Modified: trunk/src/net/sourceforge/geom4j/TriangulationTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2010-01-16 08:24:36 UTC (rev 30) +++ trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2010-01-16 11:32:17 UTC (rev 31) @@ -34,10 +34,7 @@ new Point(60, 70), new Point(30, 10) }; - Polygon polygon = new Polygon(); - for (Point point: points) { - polygon.addVertex(point); - } + Polygon polygon = new Polygon(points); assertEquals(new PointSet(points), polygon.triangulate().getVertices()); } Modified: trunk/src/net/sourceforge/geom4j/demo/Demo.java =================================================================== --- trunk/src/net/sourceforge/geom4j/demo/Demo.java 2010-01-16 08:24:36 UTC (rev 30) +++ trunk/src/net/sourceforge/geom4j/demo/Demo.java 2010-01-16 11:32:17 UTC (rev 31) @@ -57,16 +57,16 @@ */ private static void intersectionDemo() { // Create some polygon - Figure polygon = new Polygon() - .addVertex(new Point( 0, 0)) - .addVertex(new Point(10, 10)) - .addVertex(new Point(20, 0)) - .addVertex(new Point(30, 10)) - .addVertex(new Point(40, 0)) - .addVertex(new Point(50, 10)) - .addVertex(new Point(60, 0)) - .addVertex(new Point(70, 10)) - .addVertex(new Point(80, 0)); + Figure polygon = new Polygon( + new Point( 0, 0), + new Point(10, 10), + new Point(20, 0), + new Point(30, 10), + new Point(40, 0), + new Point(50, 10), + new Point(60, 0), + new Point(70, 10), + new Point(80, 0)); // Create some line Figure line = new Line(new Point(0, 5), new Point(80, 5)); // Iterate through the points of intersection @@ -81,17 +81,17 @@ */ private static void distanceDemo() { // Create some polygon - Figure square = new Polygon() - .addVertex(new Point( 0, 0)) - .addVertex(new Point( 0, 20)) - .addVertex(new Point(20, 20)) - .addVertex(new Point(20, 0)); + Figure square = new Polygon( + new Point( 0, 0), + new Point( 0, 20), + new Point(20, 20), + new Point(20, 0)); // Create another one - Figure diamond = new Polygon() - .addVertex(new Point(30, 10)) - .addVertex(new Point(35, 15)) - .addVertex(new Point(30, 20)) - .addVertex(new Point(25, 15)); + Figure diamond = new Polygon( + new Point(30, 10), + new Point(35, 15), + new Point(30, 20), + new Point(25, 15)); // Get the distance between them System.out.println("Distance: " + square.distanceTo(diamond)); } @@ -100,12 +100,12 @@ * Demonstrate convex polygon check */ private static void convexPolygonDemo() { - Polygon convex = new Polygon() - .addVertex(new Point(0, 0)) - .addVertex(new Point(100, 0)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(50, 100)) - .addVertex(new Point(0, 50)); + Polygon convex = new Polygon( + new Point(0, 0), + new Point(100, 0), + new Point(100, 100), + new Point(50, 100), + new Point(0, 50)); System.out.println(String.format("Polygon %s is %sconvex", convex, convex.isConvex() ? "" : "not ")); } @@ -113,11 +113,11 @@ * Demonstrate polygon area calculation */ private static void polygonAreaDemo() { - Polygon romb = new Polygon() - .addVertex(new Point(10, 10)) - .addVertex(new Point(50, 40)) - .addVertex(new Point(20, 80)) - .addVertex(new Point(-20, 50)); + Polygon romb = new Polygon( + new Point(10, 10), + new Point(50, 40), + new Point(20, 80), + new Point(-20, 50)); System.out.println("Area: " + romb.getArea()); } @@ -154,10 +154,10 @@ * Demonstrate point-in-polygon test */ private static void pointInsidePolygonDemo() { - Polygon triangle = new Polygon() - .addVertex(new Point(1, 1)) - .addVertex(new Point(6, 3)) - .addVertex(new Point(5, 4)); + Polygon triangle = new Polygon( + new Point(1, 1), + new Point(6, 3), + new Point(5, 4)); if (new Point(5, 3).isInside(triangle)) { System.out.println("Point (5, 3) is on the inside of the triangle."); @@ -184,20 +184,20 @@ * Demonstrate polygon simplicity test */ private static void simplePolygonDemo() { - Polygon p1 = new Polygon() - .addVertex(new Point(0, 0)) - .addVertex(new Point(100, 0)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(50, 100)) - .addVertex(new Point(0, 50)); + Polygon p1 = new Polygon( + new Point(0, 0), + new Point(100, 0), + new Point(100, 100), + new Point(50, 100), + new Point(0, 50)); System.out.println(String.format("Polygon %s is %ssimple", p1, p1.isSimple() ? "" : "not ")); - Polygon p2 = new Polygon() - .addVertex(new Point(0, 0)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(100, 0)) - .addVertex(new Point(50, 100)) - .addVertex(new Point(0, 50)); + Polygon p2 = new Polygon( + new Point(0, 0), + new Point(100, 100), + new Point(100, 0), + new Point(50, 100), + new Point(0, 50)); System.out.println(String.format("Polygon %s is %ssimple", p2, p2.isSimple() ? "" : "not ")); } @@ -206,11 +206,11 @@ * Demonstrate how to determine if one figure contains another */ private static void contentDemo() { - Figure square = new Polygon() - .addVertex(new Point(0, 0)) - .addVertex(new Point(100, 0)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(0, 100)); + Figure square = new Polygon( + new Point(0, 0), + new Point(100, 0), + new Point(100, 100), + new Point(0, 100)); Figure segment = new Segment(new Point(100, 20), new Point(100, 40)); if (square.contains(segment)) { System.out.println("Square " + square + " contains segment " + segment); @@ -221,12 +221,12 @@ * Demonstrate polygon triangulation */ private static void triangulationDemo() { - Polygon polygon = new Polygon() - .addVertex(new Point(0, 0)) - .addVertex(new Point(100, 0)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(50, 100)) - .addVertex(new Point(0, 50)); + Polygon polygon = new Polygon( + new Point(0, 0), + new Point(100, 0), + new Point(100, 100), + new Point(50, 100), + new Point(0, 50)); Triangulation triangulation = polygon.triangulate(); System.out.println(String.format("Triangulation of the polygon %s is %s", polygon, triangulation)); This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2010-01-16 08:24:42
|
Revision: 30 http://geom4j.svn.sourceforge.net/geom4j/?rev=30&view=rev Author: skhenkin Date: 2010-01-16 08:24:36 +0000 (Sat, 16 Jan 2010) Log Message: ----------- Precision bug fixed in Bentley-Ottmann algorithm implementation Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2010-01-15 22:21:21 UTC (rev 29) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2010-01-16 08:24:36 UTC (rev 30) @@ -22,6 +22,7 @@ import java.util.Set; import net.sourceforge.geom4j.util.BinaryTreeBasedSmartQueue; +import net.sourceforge.geom4j.util.ListBasedSmartQueue; import net.sourceforge.geom4j.util.SmartQueue; /** @@ -149,8 +150,8 @@ Segment seg2, Point curPoint, boolean isLeftPoint) { if (seg1 != null && seg2 != null) { for (Point p : seg1.intersects(seg2).getPoints()) { - if (p.getX() >= curPoint.getX() && isLeftPoint - || p.getX() > curPoint.getX() && !isLeftPoint) { + if (Config.greaterThanOrEqual(p.getX(), curPoint.getX()) && isLeftPoint + || Config.greaterThan(p.getX(), curPoint.getX()) && !isLeftPoint) { IntersectionEvent templateEvent = new IntersectionEvent(p, seg1, seg2, sweepLineComparator); Event existingEvent = eventQueue.find(templateEvent); if (existingEvent != null && existingEvent instanceof IntersectionEvent) { This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2010-01-15 22:21:32
|
Revision: 29 http://geom4j.svn.sourceforge.net/geom4j/?rev=29&view=rev Author: skhenkin Date: 2010-01-15 22:21:21 +0000 (Fri, 15 Jan 2010) Log Message: ----------- Precision bug fixed in Bentley-Ottmann algorithm implementation Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-15 15:23:21 UTC (rev 28) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-15 22:21:21 UTC (rev 29) @@ -221,7 +221,7 @@ * |/ \| * +----+ */ - final int N = 3; // number of vertices in the graph + final int N = 30; // number of vertices in the graph final double X1 = 0, X2 = 1000, Y1 = 0, Y2 = 1000; // generate random point set PointSet ps = new PointSet(); @@ -240,13 +240,12 @@ } } } -System.out.println(ss); - System.out.println(System.currentTimeMillis()); + //System.out.println(System.currentTimeMillis()); PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE); - System.out.println(System.currentTimeMillis()); + //System.out.println(System.currentTimeMillis()); PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); - System.out.println(System.currentTimeMillis()); - System.out.println(naiveSet.size()); + //System.out.println(System.currentTimeMillis()); + //System.out.println(naiveSet.size()); assertEquals(naiveSet, boSet); } @@ -297,9 +296,13 @@ ss.add(new Segment(new Point(x1, y1), new Point(x2, y2))); } } + //System.out.println(System.currentTimeMillis()); PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE); + //System.out.println(System.currentTimeMillis()); assertEquals(intersections, naiveSet); + //System.out.println(System.currentTimeMillis()); PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); + //System.out.println(System.currentTimeMillis()); assertEquals(naiveSet, boSet); } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2010-01-15 15:23:27
|
Revision: 28 http://geom4j.svn.sourceforge.net/geom4j/?rev=28&view=rev Author: skhenkin Date: 2010-01-15 15:23:21 +0000 (Fri, 15 Jan 2010) Log Message: ----------- "Stars" test added Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-15 07:45:33 UTC (rev 27) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-15 15:23:21 UTC (rev 28) @@ -212,6 +212,15 @@ @Test public void testRandomFullGraph() { + /* + * Test for segment sets of a full graph like this (N=4): + * +----+ + * |\ /| + * | \/ | + * | /\ | + * |/ \| + * +----+ + */ final int N = 3; // number of vertices in the graph final double X1 = 0, X2 = 1000, Y1 = 0, Y2 = 1000; // generate random point set @@ -255,7 +264,45 @@ SegmentIntersectionAlgorithm.NAIVE, SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); } + + @Test + public void testRandomStars() { + /* + * Test for a set of "stars" (groups of segments that + * intersect in one points), e.g.: + * + * \ | / \ | / \ | / + * \|/ \|/ \|/ + * ---*--- ---*--- ---*--- + * /|\ /|\ /|\ + * / | \ / | \ / | \ + * + */ + final int N = 30; // number of stars + final int K = 30; // number of segments in each star + final double Y = 100; + final double R = 100; + PointSet intersections = new PointSet(); + SegmentSet ss = new SegmentSet(); + Random r = new Random(); + for (int i = 0; i < N; i++) { + double x = i*R*3; + intersections.add(new Point(x, Y)); + for (int j = 0; j < K; j++) { + double x1 = x + r.nextDouble()*2*R - R; + double y1 = Y + r.nextDouble()*2*R - R; + double x2 = 2*x - x1; + double y2 = 2*Y - y1; + ss.add(new Segment(new Point(x1, y1), new Point(x2, y2))); + } + } + PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE); + assertEquals(intersections, naiveSet); + PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); + assertEquals(naiveSet, boSet); + } + private void assertEqualResults(double[][] segmentCoordinates, SegmentIntersectionAlgorithm alg1, SegmentIntersectionAlgorithm alg2) { This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2010-01-15 07:45:40
|
Revision: 27 http://geom4j.svn.sourceforge.net/geom4j/?rev=27&view=rev Author: skhenkin Date: 2010-01-15 07:45:33 +0000 (Fri, 15 Jan 2010) Log Message: ----------- Tests refactored. Full graph tricky test added which fails the algorithm. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-12 22:49:05 UTC (rev 26) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-15 07:45:33 UTC (rev 27) @@ -100,10 +100,11 @@ @Test public void testBigRandomSet() { - double X1 = 0, X2 = 1000, Y1 = 0, Y2 = 1000; + final int N = 300; + final double X1 = 0, X2 = 1000, Y1 = 0, Y2 = 1000; SegmentSet ss = new SegmentSet(); Random r = new Random(); - for (int i = 0; i < 300; i++) { + for (int i = 0; i < N; i++) { double x1 = r.nextDouble()*(X2-X1)+X1; double y1 = r.nextDouble()*(Y2-Y1)+Y1; double x2 = r.nextDouble()*(X2-X1)+X1; @@ -121,36 +122,32 @@ @Test public void testBentleyOttmanSpecialCase1() { - SegmentSet ss = new SegmentSet( - new Segment(new Point(7.288243310311859, 165.47985174930534), new Point(687.1335778157106, 878.6923172710824)), - new Segment(new Point(189.62978423631606, 843.6858467771974), new Point(997.5303220302917, 900.134939913248)), - new Segment(new Point(89.01407073223055, 331.76634850487164), new Point(967.7067870144189, 441.51160041074144))); - PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE); - PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); - assertEquals(naiveSet, boSet); + assertEqualResults( + new double[][] { + {7.288243310311859, 165.47985174930534, 687.1335778157106, 878.6923172710824}, + {189.62978423631606, 843.6858467771974, 997.5303220302917, 900.134939913248}, + {89.01407073223055, 331.76634850487164, 967.7067870144189, 441.51160041074144} + }, + SegmentIntersectionAlgorithm.NAIVE, + SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); } @Test public void testBentleyOttmanSpecialCase2() { - double[][] coords = new double[][] { + assertEqualResults( + new double[][] { {83, 19, 15, 60}, {47, 19, 36, 50}, {17, 39, 74, 62} - }; - 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); + }, + SegmentIntersectionAlgorithm.NAIVE, + SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); } @Test public void testBentleyOttmannPerformance() { // a number of segments in the set - int n = 1000; + final int N = 1000; /* chaining list of segments of this shape: * \/\/\/\/\/ * /\/\/\/\/\ @@ -158,7 +155,7 @@ * number of intersection is approximately 1.5*n */ SegmentSet ss = new SegmentSet(); - for (int i = 0; i < n/2; i++) { + for (int i = 0; i < N/2; i++) { ss.add(new Segment(new Point(i, 0), new Point(i+1, 1))); ss.add(new Segment(new Point(i, 1), new Point(i+1, 0))); } @@ -173,58 +170,102 @@ @Test public void testBentleyOttmanSpecialCase3SegmentsIntersection() { - double[][] coords = new double[][] { + assertEqualResults( + new double[][] { //{5, 2, 1, 1}, {3, 3, 1, 1}, {2, 0, 1, 1}, {1, 1, 8, 3}, //{1, 1, 7, 5} - }; - 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); + }, + SegmentIntersectionAlgorithm.NAIVE, + SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); } @Test public void testBentleyOttmanSpecialCase4SegmentsIntersection() { - double[][] coords = new double[][] { + assertEqualResults( + new double[][] { {5, 2, 1, 1}, {3, 3, 1, 1}, {2, 0, 1, 1}, {1, 1, 8, 3}, //{1, 1, 7, 5} - }; + }, + SegmentIntersectionAlgorithm.NAIVE, + SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); + } + + @Test + public void testBentleyOttmanSpecialCase5() { + assertEqualResults( + new double[][] { + // { 0, 0, 20, 40}, + { 20, 40, 40, 10 }, + // { 0, 0, 20, 20}, + { 20, 20, 40, 10 }, + { 0, 0, 40, 10 } + }, + SegmentIntersectionAlgorithm.NAIVE, + SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); + } + + @Test + public void testRandomFullGraph() { + final int N = 3; // number of vertices in the graph + final double X1 = 0, X2 = 1000, Y1 = 0, Y2 = 1000; + // generate random point set + PointSet ps = new PointSet(); + Random r = new Random(); + for (int i = 0; i < N; i++) { + double x = r.nextDouble()*(X2-X1)+X1; + double y = r.nextDouble()*(Y2-Y1)+Y1; + ps.add(new Point(x, y)); + } + // connect all point pairs 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]))); + for (Point p1: ps) { + for (Point p2: ps) { + if (!p1.equals(p2)) { + ss.add(new Segment(p1, p2)); + } + } } +System.out.println(ss); + System.out.println(System.currentTimeMillis()); PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE); + System.out.println(System.currentTimeMillis()); PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); + System.out.println(System.currentTimeMillis()); + System.out.println(naiveSet.size()); 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} - }; + public void testBentleyOttmanSpecialCase6() { + assertEqualResults( + new double[][] { +// {327, 113, 445, 217}, +// {190, 414, 327, 113}, +// {190, 414, 445, 217} + {327.2905356879866, 113.8601455130971, 445.1238717977011, 217.15382022225694}, + {190.09073114111064, 414.80446735274484, 327.2905356879866, 113.8601455130971}, + {190.09073114111064, 414.80446735274484, 445.1238717977011, 217.15382022225694} + }, + SegmentIntersectionAlgorithm.NAIVE, + SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); + } + + private void assertEqualResults(double[][] segmentCoordinates, + SegmentIntersectionAlgorithm alg1, + SegmentIntersectionAlgorithm alg2) { 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]))); + for (int i = 0; i < segmentCoordinates.length; i++) { + ss.add(new Segment(new Point(segmentCoordinates[i][0], segmentCoordinates[i][1]), + new Point(segmentCoordinates[i][2], segmentCoordinates[i][3]))); } - PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE); - PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); + PointSet naiveSet = ss.getAllIntersectionPoints(alg1); + PointSet boSet = ss.getAllIntersectionPoints(alg2); assertEquals(naiveSet, boSet); } } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
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. |
From: <skh...@us...> - 2010-01-09 21:20:29
|
Revision: 25 http://geom4j.svn.sourceforge.net/geom4j/?rev=25&view=rev Author: skhenkin Date: 2010-01-09 21:20:22 +0000 (Sat, 09 Jan 2010) Log Message: ----------- Bentley-Ottmman algorithm enhanced to work with points of intersection of more than 2 segments. Minor changes. Modified Paths: -------------- trunk/build.xml trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java trunk/src/net/sourceforge/geom4j/Triangulation.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java trunk/src/net/sourceforge/geom4j/util/SmartQueue.java Modified: trunk/build.xml =================================================================== --- trunk/build.xml 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/build.xml 2010-01-09 21:20:22 UTC (rev 25) @@ -19,6 +19,7 @@ <property name="app.bin.tgz" value="${build.dir}/${ant.project.name}-${app.version}-bin.tar.gz"/> <property name="app.src.zip" value="${build.dir}/${ant.project.name}-${app.version}-src.zip"/> <property name="app.src.tgz" value="${build.dir}/${ant.project.name}-${app.version}-src.tar.gz"/> + <property name="javadoc.dir" value="${build.dir}/javadoc"/> <path id="junit.classpath"> <fileset dir="${junit.dir}" includes="**/*.jar"/> @@ -108,7 +109,7 @@ </target> <target name="all" depends="package-application, package-binaries, - package-sources, package-tests, unit-test, run-demo" /> + package-sources, package-tests, unit-test, run-demo, javadoc" /> <target name="compile-debug"> <mkdir dir="${debug.classes.dir}"/> @@ -159,4 +160,20 @@ </target> <target name="coverage" depends="coverage-report" /> + + <target name="javadoc"> + <javadoc + destdir="${javadoc.dir}" + author="true" + version="true" + use="true" + windowtitle="Geom4J ${app.version}" + classpathref="junit.classpath"> + + <fileset dir="${src.dir}" defaultexcludes="yes" /> + + <doctitle><![CDATA[<h1>Geom4J - A Pure Java Computational Geometry Library</h1>]]></doctitle> + <bottom><![CDATA[<i>Copyright © 2009 Sergey Khenkin. All Rights Reserved.</i>]]></bottom> + </javadoc> + </target> </project> Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2010-01-09 21:20:22 UTC (rev 25) @@ -28,11 +28,26 @@ public class PolygonTriangulationAlgorithmTest { @Test - public void testNaive() { + public void testConvex() { Polygon polygon = new Polygon(new Point(0, 0), new Point(100, 0), new Point(100, 100), new Point(0, 100)); - Triangulation triangulation = polygon.triangulate(); + Triangulation triangulation = polygon.triangulate(PolygonTriangulationAlgorithm.CONVEX); assertTrue(triangulation.fits(polygon)); } + @Test + public void testX() { + Polygon polygon = new Polygon( + new Point(1, 1), + new Point(3, 2), + new Point(2, 0), + new Point(8, 3), + new Point(7, 5), + new Point(4, 2), + new Point(3, 3), + new Point(3, 4)); + Triangulation triangulation = polygon.triangulate(PolygonTriangulationAlgorithm.CONVEX); + assertTrue(triangulation.fits(polygon)); + } + } Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2010-01-09 21:20:22 UTC (rev 25) @@ -15,7 +15,11 @@ package net.sourceforge.geom4j; +import java.util.Collection; +import java.util.Collections; import java.util.Comparator; +import java.util.HashSet; +import java.util.Set; import net.sourceforge.geom4j.util.BinaryTreeBasedSmartQueue; import net.sourceforge.geom4j.util.SmartQueue; @@ -77,10 +81,9 @@ public PointSet run(SegmentSet segments) { // initialization SmartQueue<Event> eventQueue = initializeEventQueue(segments); - //SmartQueue<SweepLineSegment> sweepLine - // = new ListBasedSmartQueue<Segment>(sweepLineComparator); - SmartQueue<Segment> sweepLine = - new BinaryTreeBasedSmartQueue<Segment>(sweepLineComparator); + SmartQueue<Segment> sweepLine + //= new ListBasedSmartQueue<Segment>(sweepLineComparator); + = new BinaryTreeBasedSmartQueue<Segment>(sweepLineComparator); PointSet intersections = new PointSet(); // process all events in the queue while (!eventQueue.isEmpty()) { @@ -147,7 +150,16 @@ if (seg1 != null && seg2 != null) { for (Point p : seg1.intersects(seg2).getPoints()) { if (p.getX() >= curPoint.getX()) { - eventQueue.insert(new IntersectionEvent(p, seg1, seg2, sweepLineComparator)); + IntersectionEvent templateEvent = new IntersectionEvent(p, seg1, seg2, sweepLineComparator); + Event existingEvent = eventQueue.find(templateEvent); + if (existingEvent != null && existingEvent instanceof IntersectionEvent) { + // found a point where more than 2 segments intersect + ((IntersectionEvent) existingEvent).addSegment(seg1); + ((IntersectionEvent) existingEvent).addSegment(seg2); + } else { + // it's just a point of intersection of 2 segments + eventQueue.insert(templateEvent); + } } } } @@ -267,16 +279,23 @@ */ class IntersectionEvent extends Event { private Point p; - private Segment sAbove; - private Segment sBelow; + private Set<Segment> segments; public IntersectionEvent(Point p, Segment sAbove, Segment sBelow, SweepLineComparator sweepLineComparator) { super(sweepLineComparator); this.p = p; - this.sAbove = sAbove; - this.sBelow = sBelow; + this.segments = new HashSet<Segment>(); + this.segments.add(sBelow); + this.segments.add(sAbove); } + + public IntersectionEvent(Point p, Collection<Segment> segments, + SweepLineComparator sweepLineComparator) { + super(sweepLineComparator); + this.p = p; + this.segments = new HashSet<Segment>(segments); + } /** * On reaching intersection point of two segments on the sweep line add @@ -289,12 +308,24 @@ SmartQueue<Segment> sweepLine, PointSet intersectionSet) { intersectionSet.add(p); sweepLineComparator.setBefore(true); - sweepLine.swap(sAbove, sBelow); + Segment sAbove = getLastSegment(); + Segment sBelow = getFirstSegment(); + sweepLine.revert(sBelow, sAbove); sweepLineComparator.setBefore(false); addIntersectionEvent(eventQueue, sAbove, sweepLine.previous(sAbove), p); addIntersectionEvent(eventQueue, sweepLine.next(sBelow), sBelow, p); } + private Segment getLastSegment() { + //return segments.get(segments.size()-1); + return Collections.max(segments, sweepLineComparator); + } + + private Segment getFirstSegment() { + //return segments.get(0); + return Collections.min(segments, sweepLineComparator); + } + @Override public Point getPoint() { return p; @@ -306,19 +337,36 @@ } public String toString() { - return "<" + getType() + ", " + getPoint() + ", " + sAbove + ", " - + sBelow + ">"; + return "<" + getType() + ", " + getPoint() + ", [" + segments + "]>"; } @Override public boolean equals(Object obj) { if (obj instanceof IntersectionEvent) { IntersectionEvent ie = (IntersectionEvent) obj; - return p.equals(ie.p) && sAbove.equals(ie.sAbove) - && sBelow.equals(ie.sBelow); + return p.equals(ie.p) /* sAbove.equals(ie.sAbove) + && sBelow.equals(ie.sBelow) */; } return false; } + + private void addSegment(Segment s) { +/* Iterator<Segment> i = segments.iterator(); + int j = 0; + while (i.hasNext()) { + Segment intersectingSegment = i.next(); + if (sweepLineComparator.compare(intersectingSegment, s) < 0) { + //if (sweepLineComparator.compare(intersectingSegment, s) < 0) { + break; + } + if (intersectingSegment.equals(s)) { + return; + } + j++; + } + segments.add(j, s);*/ + segments.add(s); + } } /** Comparator for events in the event queue */ Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-09 21:20:22 UTC (rev 25) @@ -170,4 +170,42 @@ //System.out.println(naiveSet.size()); assertEquals(naiveSet, boSet); } + + @Test + public void testBentleyOttmanSpecialCase3SegmentsIntersection() { + double[][] coords = new double[][] { + //{5, 2, 1, 1}, + {3, 3, 1, 1}, + {2, 0, 1, 1}, + {1, 1, 8, 3}, + //{1, 1, 7, 5} + }; + 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); + } + + @Test + public void testBentleyOttmanSpecialCase4SegmentsIntersection() { + double[][] coords = new double[][] { + {5, 2, 1, 1}, + {3, 3, 1, 1}, + {2, 0, 1, 1}, + {1, 1, 8, 3}, + //{1, 1, 7, 5} + }; + 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/Triangulation.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Triangulation.java 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/src/net/sourceforge/geom4j/Triangulation.java 2010-01-09 21:20:22 UTC (rev 25) @@ -16,7 +16,7 @@ package net.sourceforge.geom4j; /** - * A polygon triangulation, actually a set of triangles. + * Polygon triangulation, actually a set of triangles. * * @author Sergey Khenkin * @since 1.0.0 @@ -64,9 +64,10 @@ return false; } // 5 - if (!getPoints().contains(doubles.getAllIntersectionPoints())) { + if (!new PointSet(polygon.getVertices()).contains(doubles.getAllIntersectionPoints())) { return false; } + // everything is fine return true; } Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2010-01-09 21:20:22 UTC (rev 25) @@ -84,7 +84,11 @@ public void setParent(Node parent) { this.parent = parent; } - + + @Override + public String toString() { + return value.toString(); + } } /** Root of the tree */ @@ -249,7 +253,7 @@ } @SuppressWarnings("unchecked") - private int compare(E e1, E e2) { + protected int compare(E e1, E e2) { if (comparator == null) return ((Comparable<? super E>) e1).compareTo(e2); else Modified: trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2010-01-09 21:20:22 UTC (rev 25) @@ -16,6 +16,8 @@ package net.sourceforge.geom4j.util; import java.util.Comparator; +import java.util.LinkedList; +import java.util.List; /** * "Smarter" implementation of SmartQueue based on a self-balancing @@ -56,6 +58,31 @@ n2.value = e1; } } + + @Override + public void revert(E e1, E e2) { + List<Node> nodes = new LinkedList<Node>(); + Node n = findNode(e1); + nodes.add(n); + do { + n = nextNode(n); + nodes.add(n); + } while (!n.value.equals(e2)); + int s = nodes.size(); + for (int i = 0; i < s/2; i++) { + Node n1 = nodes.get(i); + Node n2 = nodes.get(s-i-1); + E t = n1.value; + n1.value = n2.value; + n2.value = t; + } + } + + @Override + public E find(E e) { + Node n = findNode(e); + return n == null ? null : n.value; + } } Modified: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2010-01-09 21:20:22 UTC (rev 25) @@ -125,6 +125,36 @@ return comparator.compare(e1, e2); } } + + @Override + public void revert(E e1, E e2) { + // TODO change: to real implementation + int i1 = list.indexOf(e1); + int i2 = list.indexOf(e2); + if (i1 != -1 && i2 != -1 && i1 != i2) { + for (int i = 0; i < (i2-i1-1)/2+1; i++) { + swap(list.get(i1+i), list.get(i2-i)); + } + } + } + + @Override + public E find(E e) { + int i = 0; + while (i < list.size()) { + if (compare(list.get(i), e) > 0) { + break; + } else if (compare(list.get(i), e) == 0) { + if (list.get(i).equals(e)) { + return list.get(i); + } else { + break; + } + } + i++; + } + return null; + } } Modified: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java 2010-01-09 21:20:22 UTC (rev 25) @@ -16,6 +16,7 @@ package net.sourceforge.geom4j.util; import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; import org.junit.Test; @@ -54,4 +55,20 @@ assertTrue(q.isEmpty()); } + @Test + public void testRevert() { + SmartQueue<String> q = createQueue(); + q.revert("New York", "Toronto"); + assertFalse(q.isEmpty()); + assertEquals("Brussels", q.poll()); + assertEquals("London", q.poll()); + assertEquals("Toronto", q.poll()); + assertEquals("Tel Aviv", q.poll()); + assertEquals("Sydney", q.poll()); + assertEquals("San Francisco", q.poll()); + assertEquals("Paris", q.poll()); + assertEquals("New York", q.poll()); + assertEquals("Zurich", q.poll()); + assertTrue(q.isEmpty()); + } } Modified: trunk/src/net/sourceforge/geom4j/util/SmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2009-12-25 22:05:23 UTC (rev 24) +++ trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2010-01-09 21:20:22 UTC (rev 25) @@ -20,11 +20,13 @@ * <ul> * <li>only unique elements are stored;</li> * <li>elements are kept sorted according to some order;</li> - * <li>elements can be inserted and removed efficiently;</li> + * <li>elements can be searched, inserted and removed efficiently;</li> * <li>first element (smallest) can be extracted from the queue;</li> * <li>for any element immediately previous and immediately next * elements can be obtained;</li> - * <li>any pair of elements can be swapped.</li> + * <li>any pair of elements can be swapped;</li> + * <li>an order of a set of elements between the given pair of elements + * can be inverted.</li> * </ul> * All these actions should be performed efficiently. * @@ -46,5 +48,9 @@ boolean isEmpty(); /** Swap 2 elements */ void swap(E e1, E e2); + /** Invert the order of elements between e1 and e2 */ + void revert(E e1, E e2); + /** Find an element and return it */ + E find(E e); } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-25 22:05:33
|
Revision: 24 http://geom4j.svn.sourceforge.net/geom4j/?rev=24&view=rev Author: skhenkin Date: 2009-12-25 22:05:23 +0000 (Fri, 25 Dec 2009) Log Message: ----------- Javadocs improved. Build script supports building binary and source distributions. System properties supported. Modified Paths: -------------- trunk/build.xml trunk/src/net/sourceforge/geom4j/BasicFigure.java trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithm.java trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithmTest.java trunk/src/net/sourceforge/geom4j/CompoundFigure.java trunk/src/net/sourceforge/geom4j/Config.java trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java trunk/src/net/sourceforge/geom4j/DistanceTest.java trunk/src/net/sourceforge/geom4j/EmptyFigure.java trunk/src/net/sourceforge/geom4j/EmptyFigureTest.java trunk/src/net/sourceforge/geom4j/Figure.java trunk/src/net/sourceforge/geom4j/IntersectionTest.java trunk/src/net/sourceforge/geom4j/Line.java trunk/src/net/sourceforge/geom4j/LineTest.java trunk/src/net/sourceforge/geom4j/Point.java trunk/src/net/sourceforge/geom4j/PointPair.java trunk/src/net/sourceforge/geom4j/PointPairTest.java trunk/src/net/sourceforge/geom4j/PointSet.java trunk/src/net/sourceforge/geom4j/PointTest.java trunk/src/net/sourceforge/geom4j/Polygon.java trunk/src/net/sourceforge/geom4j/PolygonTest.java trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 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/Triangle.java trunk/src/net/sourceforge/geom4j/TriangleTest.java trunk/src/net/sourceforge/geom4j/Triangulation.java trunk/src/net/sourceforge/geom4j/TriangulationTest.java trunk/src/net/sourceforge/geom4j/Vector.java trunk/src/net/sourceforge/geom4j/VectorTest.java trunk/src/net/sourceforge/geom4j/demo/Demo.java trunk/src/net/sourceforge/geom4j/util/AVLTree.java trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueueTest.java trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java trunk/src/net/sourceforge/geom4j/util/SearchTree.java trunk/src/net/sourceforge/geom4j/util/SmartQueue.java trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java Modified: trunk/build.xml =================================================================== --- trunk/build.xml 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/build.xml 2009-12-25 22:05:23 UTC (rev 24) @@ -1,12 +1,13 @@ <project name="geom4j" basedir="." default="all"> + <property name="app.version" value="1.0.0"/> <property name="src.dir" value="${basedir}/src"/> <property name="lib.dir" value="${basedir}/lib"/> <property name="build.dir" value="${basedir}/build"/> <property name="classes.dir" value="${build.dir}/classes"/> <property name="debug.classes.dir" value="${build.dir}/classes-debug"/> - <property name="app.jar" value="${build.dir}/${ant.project.name}.jar"/> - <property name="app.tests.jar" value="${build.dir}/${ant.project.name}-tests.jar"/> + <property name="app.jar" value="${build.dir}/${ant.project.name}-${app.version}.jar"/> + <property name="app.tests.jar" value="${build.dir}/${ant.project.name}-${app.version}-tests.jar"/> <property name="demo.main.class" value="net.sourceforge.geom4j.demo.Demo"/> <property name="test.reports.dir" value="${build.dir}/test-reports"/> <property name="junit.dir" value="${lib.dir}/junit"/> @@ -14,6 +15,10 @@ <property name="instrumented.classes.dir" value="${build.dir}/instrumented-classes"/> <property name="coverage.file" value="${build.dir}/cobertura.ser"/> <property name="coverage.report.dir" value="${build.dir}/coverage-report"/> + <property name="app.bin.zip" value="${build.dir}/${ant.project.name}-${app.version}-bin.zip"/> + <property name="app.bin.tgz" value="${build.dir}/${ant.project.name}-${app.version}-bin.tar.gz"/> + <property name="app.src.zip" value="${build.dir}/${ant.project.name}-${app.version}-src.zip"/> + <property name="app.src.tgz" value="${build.dir}/${ant.project.name}-${app.version}-src.tar.gz"/> <path id="junit.classpath"> <fileset dir="${junit.dir}" includes="**/*.jar"/> @@ -52,6 +57,31 @@ includes="**/*Test.class" /> </target> + <target name="package-binaries" depends="package-application, package-tests"> + <zip destfile="${app.bin.zip}"> + <fileset dir="${build.dir}" + includes="*.jar" /> + <fileset dir="${basedir}" + includes="LICENSE.txt"/> + </zip> + <tar destfile="${app.bin.tgz}" + compression="gzip"> + <zipfileset src="${app.bin.zip}" /> + </tar> + </target> + + <target name="package-sources" depends="package-application"> + <zip destfile="${app.src.zip}"> + <fileset dir="${src.dir}" /> + <fileset dir="${basedir}" + includes="LICENSE.txt"/> + </zip> + <tar destfile="${app.src.tgz}" + compression="gzip"> + <zipfileset src="${app.src.zip}" /> + </tar> + </target> + <target name="unit-test" depends="package-application, package-tests"> <mkdir dir="${test.reports.dir}"/> <junit printsummary="yes" fork="yes" haltonfailure="yes"> @@ -77,7 +107,8 @@ classpath="${app.jar}" /> </target> - <target name="all" depends="package-application, package-tests, unit-test, run-demo"/> + <target name="all" depends="package-application, package-binaries, + package-sources, package-tests, unit-test, run-demo" /> <target name="compile-debug"> <mkdir dir="${debug.classes.dir}"/> Modified: trunk/src/net/sourceforge/geom4j/BasicFigure.java =================================================================== --- trunk/src/net/sourceforge/geom4j/BasicFigure.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/BasicFigure.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,7 @@ * A basic or primitive figure like point, line, etc. * * @author Sergey Khenkin + * @since 1.0.0 */ public abstract class BasicFigure extends Figure { Modified: trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithm.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithm.java 2009-12-25 22:05:23 UTC (rev 24) @@ -27,6 +27,7 @@ * with the smallest distance between them. * * @author Sergey Khenkin + * @since 1.0.0 */ public interface ClosestPairOfPointsAlgorithm { Modified: trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithmTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithmTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -22,6 +22,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for finding closest pair of points algorithm + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class ClosestPairOfPointsAlgorithmTest { private PointSet ps; Modified: trunk/src/net/sourceforge/geom4j/CompoundFigure.java =================================================================== --- trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-25 22:05:23 UTC (rev 24) @@ -26,6 +26,7 @@ * Can use CompoundFigure<? extends Figure> for arbitrary figures. * * @author Sergey Khenkin + * @since 1.0.0 */ public class CompoundFigure<F extends Figure> extends Figure implements Iterable<F> { protected Set<F> figures = new HashSet<F>(); Modified: trunk/src/net/sourceforge/geom4j/Config.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Config.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/Config.java 2009-12-25 22:05:23 UTC (rev 24) @@ -15,10 +15,28 @@ package net.sourceforge.geom4j; +/** + * Global configuration parameters. + * You can specify the following parameters: + * <ul> + * <li>geom4j.precision - precision of the floating point calculations, + * e.g. 0.000001, 1E-6</li> + * </ul> + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class Config { - private static double DEFAULT_PRECISION = 1E-6; - private static double precision = DEFAULT_PRECISION; + private static final String PRECISION_PARAMETER_NAME = "geom4j.precision"; + private static final double DEFAULT_PRECISION = 1E-6; + private static double precision; + static { + // initialize configuration parameters + precision = getSystemPropertyAsDouble(PRECISION_PARAMETER_NAME, + DEFAULT_PRECISION); + } + public static double getPrecision() { return precision; } @@ -72,4 +90,14 @@ public static boolean isZero(double x) { return x < precision && x > -precision; } + + private static double getSystemPropertyAsDouble( + String propertyName, double defaultValue) { + String parameterString = System.getProperty(propertyName); + if (parameterString == null) { + return defaultValue; + } else { + return Double.parseDouble(parameterString); + } + } } Modified: trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2009-12-25 22:05:23 UTC (rev 24) @@ -25,6 +25,7 @@ * The convex hull is represented as a polygon. * * @author Sergey Khenkin + * @since 1.0.0 */ public interface ConvexHullAlgorithm { /** Execute the algorithm and find the convex hull for a given point set */ Modified: trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -22,6 +22,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for convex hull algorithms + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class ConvexHullAlgorithmTest { private PointSet ps; private Polygon ch; Modified: trunk/src/net/sourceforge/geom4j/DistanceTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/DistanceTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/DistanceTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for distance calculation + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class DistanceTest { @Before @@ -86,7 +92,6 @@ @Test public void testPolygonDistance() { - // TODO: refactor this and other tests using varargs Figure p = new Point(10, 20); Figure square = new Polygon( new Point(0, 0), Modified: trunk/src/net/sourceforge/geom4j/EmptyFigure.java =================================================================== --- trunk/src/net/sourceforge/geom4j/EmptyFigure.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/EmptyFigure.java 2009-12-25 22:05:23 UTC (rev 24) @@ -21,6 +21,7 @@ * Only one instance of this class is actually instantiated via the singleton pattern. * * @author Sergey Khenkin + * @since 1.0.0 */ public final class EmptyFigure extends BasicFigure { private static final EmptyFigure emptyFigure = new EmptyFigure(); Modified: trunk/src/net/sourceforge/geom4j/EmptyFigureTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/EmptyFigureTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/EmptyFigureTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for empty figure + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class EmptyFigureTest { @Before Modified: trunk/src/net/sourceforge/geom4j/Figure.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Figure.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/Figure.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,7 @@ * Examples of figures: a point, a set of points, a line, a polygon, etc. * * @author Sergey Khenkin + * @since 1.0.0 */ public abstract class Figure { /** An empty figure, i.e. a figure containing no points */ Modified: trunk/src/net/sourceforge/geom4j/IntersectionTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/IntersectionTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/IntersectionTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -21,6 +21,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for figure intersections + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class IntersectionTest { @Before Modified: trunk/src/net/sourceforge/geom4j/Line.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Line.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/Line.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,7 @@ * Passes through two points and goes infinitely in both directions. * * @author Sergey Khenkin + * @since 1.0.0 */ public final class Line extends BasicFigure { private Point p1; Modified: trunk/src/net/sourceforge/geom4j/LineTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/LineTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/LineTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,12 @@ import org.junit.Test; +/** + * Tests for straight line figure + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class LineTest { @Test Modified: trunk/src/net/sourceforge/geom4j/Point.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Point.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/Point.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,7 @@ * Has two double coordinates (x,y). * * @author Sergey Khenkin + * @since 1.0.0 */ public final class Point extends BasicFigure { private double x; Modified: trunk/src/net/sourceforge/geom4j/PointPair.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointPair.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/PointPair.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,7 @@ * A pair of points in a plane * * @author Sergey Khenkin + * @since 1.0.0 */ public class PointPair { private Point firstPoint; Modified: trunk/src/net/sourceforge/geom4j/PointPairTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointPairTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/PointPairTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,12 @@ import org.junit.Test; +/** + * Tests for point pair figure + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class PointPairTest { @Test Modified: trunk/src/net/sourceforge/geom4j/PointSet.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointSet.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/PointSet.java 2009-12-25 22:05:23 UTC (rev 24) @@ -18,6 +18,12 @@ import java.util.Arrays; import java.util.Collection; +/** + * Set of points + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class PointSet extends CompoundFigure<Point> { /** An empty point set */ public static final PointSet EMPTY = new PointSet(); Modified: trunk/src/net/sourceforge/geom4j/PointTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/PointTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -18,6 +18,12 @@ import static org.junit.Assert.*; import org.junit.Test; +/** + * Tests for point figure + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class PointTest { @Test Modified: trunk/src/net/sourceforge/geom4j/Polygon.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-25 22:05:23 UTC (rev 24) @@ -23,6 +23,7 @@ * A polygon is a closed shape in a plane. * * @author Sergey Khenkin + * @since 1.0.0 */ public class Polygon extends BasicFigure { // TODO: think of making this class also immutable @@ -257,7 +258,7 @@ * Create polygon triangulation */ public Triangulation triangulate() { - return triangulate(PolygonTriangulationAlgorithm.NAIVE); + return triangulate(PolygonTriangulationAlgorithm.CONVEX); } /** Modified: trunk/src/net/sourceforge/geom4j/PolygonTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/PolygonTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for polygon figure + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class PolygonTest { Polygon p = new Polygon(); Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,7 @@ * A polygon triangulation algorithm. * * @author Sergey Khenkin + * @since 1.0.0 */ public interface PolygonTriangulationAlgorithm { @@ -31,9 +32,9 @@ /** - * Naive algorithm + * Straightforward algorithm for convex polygon triangulation */ - static PolygonTriangulationAlgorithm NAIVE = new PolygonTriangulationAlgorithm() { + static PolygonTriangulationAlgorithm CONVEX = new PolygonTriangulationAlgorithm() { @Override public Triangulation run(Polygon polygon) { Triangulation triangulation = new Triangulation(); Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,12 @@ import org.junit.Test; +/** + * Tests for polygon triangulation algorithms + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class PolygonTriangulationAlgorithmTest { @Test Modified: trunk/src/net/sourceforge/geom4j/Segment.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,7 @@ * A set of points of the line lying between start point and end point. * * @author Sergey Khenkin + * @since 1.0.0 */ public final class Segment extends BasicFigure { private Point startPoint; Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2009-12-25 22:05:23 UTC (rev 24) @@ -25,6 +25,7 @@ * segments. * * @author Sergey Khenkin + * @since 1.0.0 */ public interface SegmentIntersectionAlgorithm { Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -7,6 +7,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for segment intersection algorithms + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class SegmentIntersectionAlgorithmTest { SegmentSet ss1; PointSet ps1; Modified: trunk/src/net/sourceforge/geom4j/SegmentSet.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentSet.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/SegmentSet.java 2009-12-25 22:05:23 UTC (rev 24) @@ -21,6 +21,7 @@ * A set of segments * * @author Sergey Khenkin + * @since 1.0.0 */ public class SegmentSet extends CompoundFigure<Segment> { Modified: trunk/src/net/sourceforge/geom4j/SegmentTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/SegmentTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,12 @@ import org.junit.Test; +/** + * Tests for segment figure + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class SegmentTest { @Test public void testLength() { Modified: trunk/src/net/sourceforge/geom4j/Triangle.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Triangle.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/Triangle.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,7 @@ * Implemented as a specialized variation of a polygon. * * @author Sergey Khenkin + * @since 1.0.0 */ public class Triangle extends Polygon { public Triangle(Point a, Point b, Point c) { Modified: trunk/src/net/sourceforge/geom4j/TriangleTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/TriangleTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/TriangleTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,12 @@ import org.junit.Test; +/** + * Tests for triangle figure + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class TriangleTest { @Test public void testTriangleConstruction() { Modified: trunk/src/net/sourceforge/geom4j/Triangulation.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Triangulation.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/Triangulation.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,7 @@ * A polygon triangulation, actually a set of triangles. * * @author Sergey Khenkin + * @since 1.0.0 */ public class Triangulation extends CompoundFigure<Triangle> { /** Modified: trunk/src/net/sourceforge/geom4j/TriangulationTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,12 @@ import org.junit.Test; +/** + * Tests for triangulation figure + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class TriangulationTest { @Test public void testTriangulationVertices() { Modified: trunk/src/net/sourceforge/geom4j/Vector.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Vector.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/Vector.java 2009-12-25 22:05:23 UTC (rev 24) @@ -21,6 +21,7 @@ * Actually this is a 2-component vector of double values. * * @author Sergey Khenkin + * @since 1.0.0 */ public class Vector { private double x; Modified: trunk/src/net/sourceforge/geom4j/VectorTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/VectorTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/VectorTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for vectors + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class VectorTest { @Before Modified: trunk/src/net/sourceforge/geom4j/demo/Demo.java =================================================================== --- trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-25 22:05:23 UTC (rev 24) @@ -34,6 +34,7 @@ * Most probably will be a part of documentation later on. * * @author Sergey Khenkin + * @since 1.0.0 */ public class Demo { Modified: trunk/src/net/sourceforge/geom4j/util/AVLTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-25 22:05:23 UTC (rev 24) @@ -37,6 +37,7 @@ * @param <E> type of values stored in the tree * * @author Sergey Khenkin + * @since 1.0.0 */ public class AVLTree<E> extends BinarySearchTree<E> { Modified: trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -23,6 +23,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for AVL self-balancing tree + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class AVLTreeTest extends BinarySearchTreeTestBase { @Before Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-25 22:05:23 UTC (rev 24) @@ -33,6 +33,7 @@ * @param <E> type of values stored in the tree * * @author Sergey Khenkin + * @since 1.0.0 */ public class BinarySearchTree<E> implements SearchTree<E> { Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,12 @@ import org.junit.Before; import org.junit.Test; +/** + * Tests for binary tree + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class BinarySearchTreeTest extends BinarySearchTreeTestBase { @Before Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java 2009-12-25 22:05:23 UTC (rev 24) @@ -36,6 +36,7 @@ * subclasses. * * @author Sergey Khenkin + * @since 1.0.0 */ public abstract class BinarySearchTreeTestBase { Modified: trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2009-12-25 22:05:23 UTC (rev 24) @@ -27,6 +27,7 @@ * swap() - for swapping two elements present in the tree. * * @author Sergey Khenkin + * @since 1.0.0 */ public class BinaryTreeBasedSmartQueue<E> extends AVLTree<E> implements SmartQueue<E> { Modified: trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueueTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueueTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueueTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,12 @@ import org.junit.Test; +/** + * Tests for smart queue implementation based on a binary tree + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class BinaryTreeBasedSmartQueueTest extends SmartQueueTestBase { @Override protected SmartQueue<String> getQueueInstance() { Modified: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2009-12-25 22:05:23 UTC (rev 24) @@ -28,6 +28,7 @@ * efficient one of time O(log n) is ready. * * @author Sergey Khenkin + * @since 1.0.0 */ public class ListBasedSmartQueue<E> implements SmartQueue<E> { /** List that stores queue elements */ Modified: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java 2009-12-25 22:05:23 UTC (rev 24) @@ -20,6 +20,12 @@ import org.junit.Test; +/** + * Tests for smart queue implementation based on a list + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public class ListBasedSmartQueueTest extends SmartQueueTestBase { @Override protected SmartQueue<String> getQueueInstance() { Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-25 22:05:23 UTC (rev 24) @@ -25,6 +25,7 @@ * Tree stores only unique elements. * * @author Sergey Khenkin + * @since 1.0.0 */ public interface SearchTree<E> extends Iterable<E> { /** Modified: trunk/src/net/sourceforge/geom4j/util/SmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2009-12-25 22:05:23 UTC (rev 24) @@ -17,16 +17,19 @@ /** * SmartQueue is a priority queue which with the following properties: - * - only unique elements are stored; - * - elements are kept sorted according to some order; - * - elements can be inserted and removed efficiently; - * - first element (smallest) can be extracted from the queue; - * - for any element immediately previous and immediately next - * elements can be obtained; - * - any pair of elements can be swapped. + * <ul> + * <li>only unique elements are stored;</li> + * <li>elements are kept sorted according to some order;</li> + * <li>elements can be inserted and removed efficiently;</li> + * <li>first element (smallest) can be extracted from the queue;</li> + * <li>for any element immediately previous and immediately next + * elements can be obtained;</li> + * <li>any pair of elements can be swapped.</li> + * </ul> * All these actions should be performed efficiently. * * @author Sergey Khenkin + * @since 1.0.0 */ public interface SmartQueue<E> { /** Insert an element */ Modified: trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java 2009-12-18 22:27:28 UTC (rev 23) +++ trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java 2009-12-25 22:05:23 UTC (rev 24) @@ -19,6 +19,13 @@ import org.junit.Test; +/** + * Base class for smart queue tests. + * All implementation-specific details should be tested in subclasses. + * + * @author Sergey Khenkin + * @since 1.0.0 + */ public abstract class SmartQueueTestBase { protected SmartQueue<String> createQueue() { This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-18 22:27:36
|
Revision: 23 http://geom4j.svn.sourceforge.net/geom4j/?rev=23&view=rev Author: skhenkin Date: 2009-12-18 22:27:28 +0000 (Fri, 18 Dec 2009) Log Message: ----------- Tests refactored to use varargs constructors. Line equality and hashCode tests fixed. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithmTest.java trunk/src/net/sourceforge/geom4j/Config.java trunk/src/net/sourceforge/geom4j/DistanceTest.java trunk/src/net/sourceforge/geom4j/IntersectionTest.java trunk/src/net/sourceforge/geom4j/Line.java trunk/src/net/sourceforge/geom4j/LineTest.java trunk/src/net/sourceforge/geom4j/PointPairTest.java trunk/src/net/sourceforge/geom4j/PolygonTest.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/TriangulationTest.java trunk/src/net/sourceforge/geom4j/Vector.java trunk/src/net/sourceforge/geom4j/VectorTest.java Modified: trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithmTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/ClosestPairOfPointsAlgorithmTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -43,7 +43,8 @@ ps.add(new Point(2, 2)); ps.add(new Point(5, 3)); ps.add(new Point(11, 4)); - ps.add(new Point(9, 2)); } + ps.add(new Point(9, 2)); + } @Test public void testNaive() { Modified: trunk/src/net/sourceforge/geom4j/Config.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Config.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/Config.java 2009-12-18 22:27:28 UTC (rev 23) @@ -68,4 +68,8 @@ public static double roundValue(double x) { return Math.round(x / precision) * precision; } + + public static boolean isZero(double x) { + return x < precision && x > -precision; + } } Modified: trunk/src/net/sourceforge/geom4j/DistanceTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/DistanceTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/DistanceTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -88,15 +88,15 @@ public void testPolygonDistance() { // TODO: refactor this and other tests using varargs Figure p = new Point(10, 20); - Figure square = new Polygon() - .addVertex(new Point(0, 0)) - .addVertex(new Point(0, 25)) - .addVertex(new Point(25, 25)) - .addVertex(new Point(25, 0)); - Figure triangle = new Polygon() - .addVertex(new Point(5, 10)) - .addVertex(new Point(10, 15)) - .addVertex(new Point(15, 15)); + Figure square = new Polygon( + new Point(0, 0), + new Point(0, 25), + new Point(25, 25), + new Point(25, 0)); + Figure triangle = new Polygon( + new Point(5, 10), + new Point(10, 15), + new Point(15, 15)); assertTrue(Config.equal(5, p.distanceTo(square))); assertTrue(Config.equal(5, p.distanceTo(triangle))); assertTrue(Config.equal(5, triangle.distanceTo(square))); Modified: trunk/src/net/sourceforge/geom4j/IntersectionTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/IntersectionTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/IntersectionTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -92,30 +92,30 @@ @Test public void testLineAndPolygonIntersection() { Figure line = new Line(new Point(0, 0), new Point(1, 1)); - Figure poly = new Polygon().addVertex(new Point(0, 0)) - .addVertex(new Point(10, 20)) - .addVertex(new Point(100, 20)) - .addVertex(new Point(90, 0)); - assertEquals(new PointSet().add(new Point(0, 0)) - .add(new Point(20, 20)), + Figure poly = new Polygon(new Point(0, 0), + new Point(10, 20), + new Point(100, 20), + new Point(90, 0)); + assertEquals(new PointSet(new Point(0, 0), + new Point(20, 20)), line.intersects(poly)); } @Test public void testPolygonIntersection() { - Figure square = new Polygon().addVertex(new Point( 0, 0)) - .addVertex(new Point(100, 0)) - .addVertex(new Point(100, 100)) - .addVertex(new Point( 0, 100)); - Figure trapezoid = new Polygon().addVertex(new Point(-20, 40)) - .addVertex(new Point(120, 40)) - .addVertex(new Point( 90, 130)) - .addVertex(new Point( 40, 130)); - assertEquals(new PointSet().add(new Point( 0, 40)) - .add(new Point( 0, 70)) - .add(new Point( 20, 100)) - .add(new Point(100, 100)) - .add(new Point(100, 40)), + Figure square = new Polygon(new Point( 0, 0), + new Point(100, 0), + new Point(100, 100), + new Point( 0, 100)); + Figure trapezoid = new Polygon(new Point(-20, 40), + new Point(120, 40), + new Point( 90, 130), + new Point( 40, 130)); + assertEquals(new PointSet(new Point( 0, 40), + new Point( 0, 70), + new Point( 20, 100), + new Point(100, 100), + new Point(100, 40)), square.intersects(trapezoid)); } } Modified: trunk/src/net/sourceforge/geom4j/Line.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Line.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/Line.java 2009-12-18 22:27:28 UTC (rev 23) @@ -41,13 +41,41 @@ @Override public int hashCode() { final int prime = 31; - int result = 1; - // TODO: !!! this is completely wrong - result = prime * result + p1.hashCode(); - result = prime * result + p2.hashCode(); - return result; + long result = 1; + result = prime * result + Double.doubleToLongBits(getSlope()); + result = prime * result + Double.doubleToLongBits(getIntercept()); + return (int) result; } + /** + * A slope quotient of the straight line equation in the "slope-intercept" form. + * It is K in the equation y = Kx + B. + * @return slope quotient value (Double.POSITIVE_INFINITY if the line is vertical) + */ + public double getSlope() { + double dx = p2.getX() - p1.getX(); + double dy = p2.getY() - p1.getY(); + if (Config.isZero(dx)) { + return Double.POSITIVE_INFINITY; + } else { + return dy / dx; + } + } + + /** + * A y-intercept of the straight line equation in the "slope-intercept" form. + * It is B in the equation y = Kx + B. + * @return y-intercept value (Double.NaN if the line is vertical) + */ + public double getIntercept() { + double dx = p2.getX() - p1.getX(); + if (Config.isZero(dx)) { + return Double.NaN; + } else { + return (p2.getX()*p1.getY() - p1.getX()*p2.getY()) / dx; + } + } + @Override public boolean equals(Object obj) { if (obj instanceof Line) { Modified: trunk/src/net/sourceforge/geom4j/LineTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/LineTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/LineTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -16,6 +16,7 @@ package net.sourceforge.geom4j; import static org.junit.Assert.*; + import org.junit.Test; public class LineTest { @@ -105,4 +106,37 @@ assertFalse(l1.parallelTo(l3)); } + + @Test + public void testCorrectHashCode() { + Point p1 = new Point(10, 10); + Point p2 = new Point(20, 20); + Point p3 = new Point(30, 30); + Point p4 = new Point(40, 40); + Line line1 = new Line(p1, p2); + Line line2 = new Line(p2, p1); + Line line3 = new Line(p3, p4); + assertEquals(line1.hashCode(), line2.hashCode()); + assertEquals(line1.hashCode(), line3.hashCode()); + } + + @Test + public void testSlopeAndIntercept() { + assertSlopeIntercept(new Point(8, 2), new Point(12, 4), 0.5, -2); + assertSlopeIntercept(new Point(3, 2), new Point(-3, 10), -4.0/3, 6); + assertSlopeIntercept(new Point(2, -5), new Point(5, -5), 0, -5); + assertVertical(new Point(3, 1), new Point(3, 2)); + } + + private void assertSlopeIntercept(Point p1, Point p2, double k, double b) { + Line line = new Line(p1, p2); + assertEquals(0, Double.compare(k, line.getSlope())); + assertEquals(0, Double.compare(b, line.getIntercept())); + } + + private void assertVertical(Point p1, Point p2) { + Line line = new Line(p1, p2); + assertTrue(Double.isInfinite(line.getSlope())); + assertTrue(Double.isNaN(line.getIntercept())); + } } Modified: trunk/src/net/sourceforge/geom4j/PointPairTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointPairTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/PointPairTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -29,5 +29,14 @@ assertEquals(new PointPair(p1, p2), new PointPair(p2, p1)); assertFalse(new PointPair(p1, p2).equals(new PointPair(p2, new Point(40, 20)))); } + + @Test + public void testCorrectHashCode() { + Point p1 = new Point(10, 10); + Point p2 = new Point(30, 5); + PointPair pp1 = new PointPair(p1, p2); + PointPair pp2 = new PointPair(p2, p1); + assertEquals(pp1.hashCode(), pp2.hashCode()); + } } Modified: trunk/src/net/sourceforge/geom4j/PolygonTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/PolygonTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -47,11 +47,11 @@ @Test public void testContains() { - Polygon p = new Polygon().addVertex(new Point(0, 0)) - .addVertex(new Point(100, 0)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(50, 100)) - .addVertex(new Point(0, 50)); + Polygon p = new Polygon(new Point(0, 0), + new Point(100, 0), + new Point(100, 100), + new Point(50, 100), + new Point(0, 50)); assertTrue(p.contains(p)); assertEquals(p, p); assertTrue(p.contains(new Point(50, 100))); @@ -63,92 +63,92 @@ @Test public void testConvex() { - Polygon convex1 = new Polygon() - .addVertex(new Point(0, 0)) - .addVertex(new Point(100, 0)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(50, 100)) - .addVertex(new Point(0, 50)); + Polygon convex1 = new Polygon( + new Point(0, 0), + new Point(100, 0), + new Point(100, 100), + new Point(50, 100), + new Point(0, 50)); assertTrue(convex1.isConvex()); - Polygon convex2 = new Polygon() - .addVertex(new Point(0, 50)) - .addVertex(new Point(50, 100)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(100, 0)) - .addVertex(new Point(0, 0)); + Polygon convex2 = new Polygon( + new Point(0, 50), + new Point(50, 100), + new Point(100, 100), + new Point(100, 0), + new Point(0, 0)); assertTrue(convex2.isConvex()); - Polygon convex3 = new Polygon() - .addVertex(new Point(0, 50)) - .addVertex(new Point(0, 100)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(50, 50)) - .addVertex(new Point(0, 0)); + Polygon convex3 = new Polygon( + new Point(0, 50), + new Point(0, 100), + new Point(100, 100), + new Point(50, 50), + new Point(0, 0)); assertTrue(convex3.isConvex()); - Polygon nonConvex1 = new Polygon() - .addVertex(new Point(0, 0)) - .addVertex(new Point(100, 50)) - .addVertex(new Point(50, 50)) - .addVertex(new Point(50, 100)); + Polygon nonConvex1 = new Polygon( + new Point(0, 0), + new Point(100, 50), + new Point(50, 50), + new Point(50, 100)); assertFalse(nonConvex1.isConvex()); - Polygon nonConvex2 = new Polygon() - .addVertex(new Point(100, 50)) - .addVertex(new Point(0, 0)) - .addVertex(new Point(50, 100)) - .addVertex(new Point(50, 50)); + Polygon nonConvex2 = new Polygon( + new Point(100, 50), + new Point(0, 0), + new Point(50, 100), + new Point(50, 50)); assertFalse(nonConvex2.isConvex()); - Polygon nonConvex3 = new Polygon() - .addVertex(new Point(0, 50)) - .addVertex(new Point(0, 100)) - .addVertex(new Point(100, 100)) - .addVertex(new Point(50, 51)) - .addVertex(new Point(0, 0)); + Polygon nonConvex3 = new Polygon( + new Point(0, 50), + new Point(0, 100), + new Point(100, 100), + new Point(50, 51), + new Point(0, 0)); assertFalse(nonConvex3.isConvex()); } @Test public void testArea() { - Polygon square = new Polygon() - .addVertex(new Point(10, 10)) - .addVertex(new Point(10, 20)) - .addVertex(new Point(20, 20)) - .addVertex(new Point(20, 10)); + Polygon square = new Polygon( + new Point(10, 10), + new Point(10, 20), + new Point(20, 20), + new Point(20, 10)); assertTrue(Config.equal(100, square.getArea())); - Polygon romb = new Polygon() - .addVertex(new Point(10, 10)) - .addVertex(new Point(50, 40)) - .addVertex(new Point(20, 80)) - .addVertex(new Point(-20, 50)); + Polygon romb = new Polygon( + new Point(10, 10), + new Point(50, 40), + new Point(20, 80), + new Point(-20, 50)); assertTrue(Config.equal(2500, romb.getArea())); assertTrue(Config.equal(4+8+6+6+6, p.getArea())); - Polygon mess = new Polygon() - .addVertex(new Point(1, 2)) - .addVertex(new Point(5, 2)) - .addVertex(new Point(2, 3)) - .addVertex(new Point(5, 3)) - .addVertex(new Point(2, 4)) - .addVertex(new Point(5, 6)) - .addVertex(new Point(3, 5)) - .addVertex(new Point(4, 7)) - .addVertex(new Point(4, 6)) - .addVertex(new Point(5, 7)) - .addVertex(new Point(1, 8)); + Polygon mess = new Polygon( + new Point(1, 2), + new Point(5, 2), + new Point(2, 3), + new Point(5, 3), + new Point(2, 4), + new Point(5, 6), + new Point(3, 5), + new Point(4, 7), + new Point(4, 6), + new Point(5, 7), + new Point(1, 8)); assertTrue(Config.equal(24-2-1.5-4.5-1.5, mess.getArea())); } @Test public void testSimplicity() { assertTrue(p.isSimple()); - assertTrue(new Polygon() - .addVertex(new Point(10, 10)) - .addVertex(new Point(10, 20)) - .addVertex(new Point(20, 20)) - .addVertex(new Point(20, 10)) + assertTrue(new Polygon( + new Point(10, 10), + new Point(10, 20), + new Point(20, 20), + new Point(20, 10)) .isSimple()); - assertFalse(new Polygon() - .addVertex(new Point(10, 10)) - .addVertex(new Point(10, 20)) - .addVertex(new Point(20, 10)) - .addVertex(new Point(20, 20)) + assertFalse(new Polygon( + new Point(10, 10), + new Point(10, 20), + new Point(20, 10), + new Point(20, 20)) .isSimple()); } } Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -19,18 +19,18 @@ @Before public void setUp() throws Exception { - ss1 = new SegmentSet() - .add(new Segment(new Point(1, 1), new Point(10, 10))) - .add(new Segment(new Point(10, 1), new Point(1, 10))) - .add(new Segment(new Point(1, 4), new Point(5, 2))); - ps1 = new PointSet().add(new Point(5.5, 5.5)).add(new Point(3, 3)); + ss1 = new SegmentSet( + new Segment(new Point(1, 1), new Point(10, 10)), + new Segment(new Point(10, 1), new Point(1, 10)), + new Segment(new Point(1, 4), new Point(5, 2))); + ps1 = new PointSet(new Point(5.5, 5.5), new Point(3, 3)); - Polygon p = new Polygon() - .addVertex(new Point(1, 1)) - .addVertex(new Point(1, 2)) - .addVertex(new Point(2, 3)) - .addVertex(new Point(3, 2)) - .addVertex(new Point(3, 1)); + Polygon p = new Polygon( + new Point(1, 1), + new Point(1, 2), + new Point(2, 3), + new Point(3, 2), + new Point(3, 1)); ss2 = p.getSegmentSet(); ps2 = new PointSet(p.getVertices()); @@ -115,10 +115,10 @@ @Test public void testBentleyOttmanSpecialCase1() { - SegmentSet ss = new SegmentSet() - .add(new Segment(new Point(7.288243310311859, 165.47985174930534), new Point(687.1335778157106, 878.6923172710824))) - .add(new Segment(new Point(189.62978423631606, 843.6858467771974), new Point(997.5303220302917, 900.134939913248))) - .add(new Segment(new Point(89.01407073223055, 331.76634850487164), new Point(967.7067870144189, 441.51160041074144))); + SegmentSet ss = new SegmentSet( + new Segment(new Point(7.288243310311859, 165.47985174930534), new Point(687.1335778157106, 878.6923172710824)), + new Segment(new Point(189.62978423631606, 843.6858467771974), new Point(997.5303220302917, 900.134939913248)), + new Segment(new Point(89.01407073223055, 331.76634850487164), new Point(967.7067870144189, 441.51160041074144))); 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 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/SegmentSet.java 2009-12-18 22:27:28 UTC (rev 23) @@ -15,6 +15,8 @@ package net.sourceforge.geom4j; +import java.util.Arrays; + /** * A set of segments * @@ -22,6 +24,13 @@ */ public class SegmentSet extends CompoundFigure<Segment> { + public SegmentSet() { + } + + public SegmentSet(Segment... segments) { + super(Arrays.asList(segments)); + } + @Override public SegmentSet add(Segment f) { return (SegmentSet) super.add(f); Modified: trunk/src/net/sourceforge/geom4j/SegmentTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/SegmentTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -16,6 +16,7 @@ package net.sourceforge.geom4j; import static org.junit.Assert.*; + import org.junit.Test; public class SegmentTest { @@ -101,4 +102,13 @@ assertEquals(topLeft, topHorizontal.getLeftPoint()); assertEquals(topRight, topHorizontal.getRightPoint()); } + + @Test + public void testCorrectHashCode() { + Point p1 = new Point(10, 10); + Point p2 = new Point(30, 5); + Segment s1 = new Segment(p1, p2); + Segment s2 = new Segment(p2, p1); + assertEquals(s1.hashCode(), s2.hashCode()); + } } Modified: trunk/src/net/sourceforge/geom4j/TriangulationTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -38,12 +38,11 @@ @Test public void testFitting() { - Polygon polygon = new Polygon(new Point[] { + Polygon polygon = new Polygon( new Point(10, 0), new Point(0, 40), new Point(60, 70), - new Point(30, 10) - }); + new Point(30, 10)); Triangulation triangulation = new Triangulation(); triangulation.add(new Triangle(new Point(0, 40), new Point(30, 10), new Point(10, 0))) .add(new Triangle(new Point(30, 10), new Point(0, 40), new Point(60, 70))); Modified: trunk/src/net/sourceforge/geom4j/Vector.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Vector.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/Vector.java 2009-12-18 22:27:28 UTC (rev 23) @@ -63,6 +63,21 @@ @Override + public boolean equals(Object obj) { + if (obj instanceof Vector) { + Vector v = (Vector) obj; + return x == v.x && y == v.y; + } + return false; + } + + @Override + public int hashCode() { + final int prime = 31; + return (int) (Double.doubleToLongBits(x) + prime * Double.doubleToLongBits(y)); + } + + @Override public String toString() { return "(" + x + ", " + y + ")"; } Modified: trunk/src/net/sourceforge/geom4j/VectorTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/VectorTest.java 2009-12-18 18:16:58 UTC (rev 22) +++ trunk/src/net/sourceforge/geom4j/VectorTest.java 2009-12-18 22:27:28 UTC (rev 23) @@ -51,4 +51,14 @@ assertTrue(Config.equal(Math.sqrt(2), new Vector(1.0, -1.0).length())); assertTrue(Config.equal(10, new Vector(0, -10).length())); } + + @Test + public void testCorrectHashCode() { + Vector v1 = new Vector(2, 1); + Vector v2 = new Vector(1, 2); + Vector v3 = new Vector(new Point(5, 6), new Point(7, 7)); + assertEquals(v1, v3); + assertFalse(v1.equals(v2)); + assertEquals(v1.hashCode(), v3.hashCode()); + } } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-18 18:17:04
|
Revision: 22 http://geom4j.svn.sourceforge.net/geom4j/?rev=22&view=rev Author: skhenkin Date: 2009-12-18 18:16:58 +0000 (Fri, 18 Dec 2009) Log Message: ----------- Triangle class added. Triangulation algorithm infrastructure created. Annoying bug in hashCode() for Segment and PointPair fixed. Bug in Line.hashCode() to be fixed. Varargs introduced in Polygon and PointSet constructors. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/CompoundFigure.java trunk/src/net/sourceforge/geom4j/DistanceTest.java trunk/src/net/sourceforge/geom4j/Line.java trunk/src/net/sourceforge/geom4j/PointPair.java trunk/src/net/sourceforge/geom4j/PointSet.java trunk/src/net/sourceforge/geom4j/Polygon.java trunk/src/net/sourceforge/geom4j/Segment.java trunk/src/net/sourceforge/geom4j/SegmentSet.java trunk/src/net/sourceforge/geom4j/demo/Demo.java Added Paths: ----------- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java trunk/src/net/sourceforge/geom4j/Triangle.java trunk/src/net/sourceforge/geom4j/TriangleTest.java trunk/src/net/sourceforge/geom4j/Triangulation.java trunk/src/net/sourceforge/geom4j/TriangulationTest.java Modified: trunk/src/net/sourceforge/geom4j/CompoundFigure.java =================================================================== --- trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-18 15:30:14 UTC (rev 21) +++ trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-18 18:16:58 UTC (rev 22) @@ -44,6 +44,10 @@ } return this; } + + public boolean remove(F f) { + return figures.remove(f); + } public CompoundFigure<F> add(CompoundFigure<F> f) { // TODO: think of avoiding duplicate sets of points @@ -51,6 +55,11 @@ return this; } + public CompoundFigure<F> addAll(Collection<F> figures) { + this.figures.addAll(figures); + return this; + } + public int size() { return figures.size(); } Modified: trunk/src/net/sourceforge/geom4j/DistanceTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/DistanceTest.java 2009-12-18 15:30:14 UTC (rev 21) +++ trunk/src/net/sourceforge/geom4j/DistanceTest.java 2009-12-18 18:16:58 UTC (rev 22) @@ -86,6 +86,7 @@ @Test public void testPolygonDistance() { + // TODO: refactor this and other tests using varargs Figure p = new Point(10, 20); Figure square = new Polygon() .addVertex(new Point(0, 0)) Modified: trunk/src/net/sourceforge/geom4j/Line.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Line.java 2009-12-18 15:30:14 UTC (rev 21) +++ trunk/src/net/sourceforge/geom4j/Line.java 2009-12-18 18:16:58 UTC (rev 22) @@ -42,6 +42,7 @@ public int hashCode() { final int prime = 31; int result = 1; + // TODO: !!! this is completely wrong result = prime * result + p1.hashCode(); result = prime * result + p2.hashCode(); return result; Modified: trunk/src/net/sourceforge/geom4j/PointPair.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointPair.java 2009-12-18 15:30:14 UTC (rev 21) +++ trunk/src/net/sourceforge/geom4j/PointPair.java 2009-12-18 18:16:58 UTC (rev 22) @@ -39,11 +39,7 @@ @Override public int hashCode() { - final int prime = 31; - int result = 1; - result = prime * result + firstPoint.hashCode(); - result = prime * result + secondPoint.hashCode(); - return result; + return firstPoint.hashCode() + secondPoint.hashCode(); } @Override Modified: trunk/src/net/sourceforge/geom4j/PointSet.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointSet.java 2009-12-18 15:30:14 UTC (rev 21) +++ trunk/src/net/sourceforge/geom4j/PointSet.java 2009-12-18 18:16:58 UTC (rev 22) @@ -15,6 +15,7 @@ package net.sourceforge.geom4j; +import java.util.Arrays; import java.util.Collection; public class PointSet extends CompoundFigure<Point> { @@ -28,6 +29,10 @@ super(points); } + public PointSet(Point... points) { + this(Arrays.asList(points)); + } + /** * CompoundFigure's equality is overridden for better performance. */ @@ -47,8 +52,6 @@ return (PointSet) super.add(f); } - - /** * Get a convex hull (convex envelope) for a point set using some algorithm. * Different algorithms can be used for convex hull construction. Modified: trunk/src/net/sourceforge/geom4j/Polygon.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-18 15:30:14 UTC (rev 21) +++ trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-18 18:16:58 UTC (rev 22) @@ -27,11 +27,19 @@ public class Polygon extends BasicFigure { // TODO: think of making this class also immutable - private List<Point> vertices = new ArrayList<Point>(); + protected List<Point> vertices; public Polygon() { + this.vertices = new ArrayList<Point>(); } + public Polygon(Point... vertices) { + this.vertices = new ArrayList<Point>(vertices.length); + for (Point vertex: vertices) { + this.vertices.add(vertex); + } + } + public Polygon addVertex(Point p) { vertices.add(p); return this; @@ -58,6 +66,12 @@ return perimeter; } + /** + * Hash code of a polygon is defined as the hash code + * of the segment set of which it consists. + * This implies equal hash codes for equal polygons. + * Hash code based on vertices only is not enough! + */ @Override public int hashCode() { return getSegmentSet().hashCode(); @@ -238,4 +252,18 @@ intersections.remove(getVertices()); // we don't count vertices return intersections.isEmpty(); } + + /** + * Create polygon triangulation + */ + public Triangulation triangulate() { + return triangulate(PolygonTriangulationAlgorithm.NAIVE); + } + + /** + * Create polygon triangulation using the specified algorithm + */ + public Triangulation triangulate(PolygonTriangulationAlgorithm alg) { + return alg.run(this); + } } Added: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2009-12-18 18:16:58 UTC (rev 22) @@ -0,0 +1,50 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j; + +/** + * A polygon triangulation algorithm. + * + * @author Sergey Khenkin + */ + +public interface PolygonTriangulationAlgorithm { + + /** + * Execute the algorithm and find the triangulation, + * i.e. a set of triangles + */ + Triangulation run(Polygon polygon); + + + /** + * Naive algorithm + */ + static PolygonTriangulationAlgorithm NAIVE = new PolygonTriangulationAlgorithm() { + @Override + public Triangulation run(Polygon polygon) { + Triangulation triangulation = new Triangulation(); + int n = polygon.getVertexCount(); + for (int i = 1; i < n-1; i++) { + triangulation.add(new Triangle(polygon.getVertex(0), + polygon.getVertex(i), + polygon.getVertex(i+1))); + } + return triangulation; + } + }; + +} Added: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2009-12-18 18:16:58 UTC (rev 22) @@ -0,0 +1,32 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j; + +import static org.junit.Assert.*; + +import org.junit.Test; + +public class PolygonTriangulationAlgorithmTest { + + @Test + public void testNaive() { + Polygon polygon = new Polygon(new Point(0, 0), new Point(100, 0), + new Point(100, 100), new Point(0, 100)); + Triangulation triangulation = polygon.triangulate(); + assertTrue(triangulation.fits(polygon)); + } + +} Modified: trunk/src/net/sourceforge/geom4j/Segment.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-18 15:30:14 UTC (rev 21) +++ trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-18 18:16:58 UTC (rev 22) @@ -55,8 +55,8 @@ public int hashCode() { final int prime = 31; int result = 1; - result = prime * result + endPoint.hashCode(); - result = prime * result + startPoint.hashCode(); + result = prime * result + getLeftPoint().hashCode(); + result = prime * result + getRightPoint().hashCode(); return result; } Modified: trunk/src/net/sourceforge/geom4j/SegmentSet.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentSet.java 2009-12-18 15:30:14 UTC (rev 21) +++ trunk/src/net/sourceforge/geom4j/SegmentSet.java 2009-12-18 18:16:58 UTC (rev 22) @@ -15,6 +15,11 @@ package net.sourceforge.geom4j; +/** + * A set of segments + * + * @author Sergey Khenkin + */ public class SegmentSet extends CompoundFigure<Segment> { @Override Added: trunk/src/net/sourceforge/geom4j/Triangle.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Triangle.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/Triangle.java 2009-12-18 18:16:58 UTC (rev 22) @@ -0,0 +1,32 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j; + +/** + * Triangle figure. + * Implemented as a specialized variation of a polygon. + * + * @author Sergey Khenkin + */ +public class Triangle extends Polygon { + public Triangle(Point a, Point b, Point c) { + vertices.add(a); + vertices.add(b); + vertices.add(c); + } + + +} Added: trunk/src/net/sourceforge/geom4j/TriangleTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/TriangleTest.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/TriangleTest.java 2009-12-18 18:16:58 UTC (rev 22) @@ -0,0 +1,32 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j; + +import static org.junit.Assert.*; + +import org.junit.Test; + +public class TriangleTest { + @Test + public void testTriangleConstruction() { + Point p1 = new Point(50, 30); + Point p2 = new Point(-17, 45); + Point p3 = new Point(93, -41); + Polygon p = new Polygon(p1, p2, p3); + Triangle t = new Triangle(p1, p2, p3); + assertEquals(p, t); + } +} Added: trunk/src/net/sourceforge/geom4j/Triangulation.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Triangulation.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/Triangulation.java 2009-12-18 18:16:58 UTC (rev 22) @@ -0,0 +1,81 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j; + +/** + * A polygon triangulation, actually a set of triangles. + * + * @author Sergey Khenkin + */ +public class Triangulation extends CompoundFigure<Triangle> { + /** + * Test if this triangulation fits the polygon specified, + * i.e. if this is a valid triangulation for this polygon + */ + public boolean fits(Polygon polygon) { + /* + * We use a sequence of tests to check validity: + * 1. Number of triangles is less than number of polygon vertices by 2. + * 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. + */ + // 1 + if (size() != polygon.getVertexCount() - 2) { + return false; + } + // 2 + if (!getVertices().equals(new PointSet(polygon.getVertices()))) { + return false; + } + SegmentSet singles = new SegmentSet(); + SegmentSet doubles = new SegmentSet(); + for (Triangle triangle: figures) { + for (Segment segment: triangle.getSegmentSet()) { + // 3 + if (doubles.contains(segment)) { + return false; // a segment comes for the third time + } + if (singles.contains(segment)) { + singles.remove(segment); + doubles.add(segment); + } else { + singles.add(segment); + } + } + } + // 4 + if (!singles.equals(polygon.getSegmentSet())) { + return false; + } + // 5 + if (!getPoints().contains(doubles.getAllIntersectionPoints())) { + return false; + } + return true; + } + + public PointSet getVertices() { + PointSet vertices = new PointSet(); + for (Triangle triangle: figures) { + vertices.addAll(triangle.getVertices()); + } + return vertices; + } + + +} Added: trunk/src/net/sourceforge/geom4j/TriangulationTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/TriangulationTest.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2009-12-18 18:16:58 UTC (rev 22) @@ -0,0 +1,52 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j; + +import static org.junit.Assert.*; + +import org.junit.Test; + +public class TriangulationTest { + @Test + public void testTriangulationVertices() { + Point[] points = new Point[] { + new Point(10, 0), + new Point(0, 40), + new Point(60, 70), + new Point(30, 10) + }; + Polygon polygon = new Polygon(); + for (Point point: points) { + polygon.addVertex(point); + } + assertEquals(new PointSet(points), + polygon.triangulate().getVertices()); + } + + @Test + public void testFitting() { + Polygon polygon = new Polygon(new Point[] { + new Point(10, 0), + new Point(0, 40), + new Point(60, 70), + new Point(30, 10) + }); + Triangulation triangulation = new Triangulation(); + triangulation.add(new Triangle(new Point(0, 40), new Point(30, 10), new Point(10, 0))) + .add(new Triangle(new Point(30, 10), new Point(0, 40), new Point(60, 70))); + assertTrue(triangulation.fits(polygon)); + } +} Modified: trunk/src/net/sourceforge/geom4j/demo/Demo.java =================================================================== --- trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-18 15:30:14 UTC (rev 21) +++ trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-18 18:16:58 UTC (rev 22) @@ -26,6 +26,7 @@ import net.sourceforge.geom4j.Segment; import net.sourceforge.geom4j.SegmentIntersectionAlgorithm; import net.sourceforge.geom4j.SegmentSet; +import net.sourceforge.geom4j.Triangulation; /** * Demo class for the library. @@ -47,6 +48,7 @@ segmentIntersectionDemo(); simplePolygonDemo(); contentDemo(); + triangulationDemo(); } /** @@ -213,4 +215,20 @@ System.out.println("Square " + square + " contains segment " + segment); } } + + /** + * Demonstrate polygon triangulation + */ + private static void triangulationDemo() { + Polygon polygon = new Polygon() + .addVertex(new Point(0, 0)) + .addVertex(new Point(100, 0)) + .addVertex(new Point(100, 100)) + .addVertex(new Point(50, 100)) + .addVertex(new Point(0, 50)); + Triangulation triangulation = polygon.triangulate(); + System.out.println(String.format("Triangulation of the polygon %s is %s", + polygon, triangulation)); + } + } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-18 15:30:23
|
Revision: 21 http://geom4j.svn.sourceforge.net/geom4j/?rev=21&view=rev Author: skhenkin Date: 2009-12-18 15:30:14 +0000 (Fri, 18 Dec 2009) Log Message: ----------- Equality performance check improved Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/CompoundFigure.java trunk/src/net/sourceforge/geom4j/EmptyFigure.java trunk/src/net/sourceforge/geom4j/Line.java trunk/src/net/sourceforge/geom4j/Point.java trunk/src/net/sourceforge/geom4j/PointPair.java trunk/src/net/sourceforge/geom4j/PointSet.java trunk/src/net/sourceforge/geom4j/Polygon.java trunk/src/net/sourceforge/geom4j/Segment.java Modified: trunk/src/net/sourceforge/geom4j/CompoundFigure.java =================================================================== --- trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-14 23:44:34 UTC (rev 20) +++ trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-18 15:30:14 UTC (rev 21) @@ -79,11 +79,14 @@ @Override public boolean equals(Object obj) { + if (this == obj) { + return true; + } if (obj instanceof CompoundFigure) { CompoundFigure<?> cf = (CompoundFigure<?>) obj; return contains(cf) && cf.contains(this); } - return super.equals(obj); + return false; } Modified: trunk/src/net/sourceforge/geom4j/EmptyFigure.java =================================================================== --- trunk/src/net/sourceforge/geom4j/EmptyFigure.java 2009-12-14 23:44:34 UTC (rev 20) +++ trunk/src/net/sourceforge/geom4j/EmptyFigure.java 2009-12-18 15:30:14 UTC (rev 21) @@ -34,10 +34,7 @@ @Override public boolean equals(Object obj) { - if (obj instanceof EmptyFigure) { - return true; - } - return false; + return obj instanceof EmptyFigure; } @Override Modified: trunk/src/net/sourceforge/geom4j/Line.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Line.java 2009-12-14 23:44:34 UTC (rev 20) +++ trunk/src/net/sourceforge/geom4j/Line.java 2009-12-18 15:30:14 UTC (rev 21) @@ -53,7 +53,7 @@ Line line = (Line) obj; return contains(line.getP1()) && contains(line.getP2()); } - return super.equals(obj); + return false; } @Override Modified: trunk/src/net/sourceforge/geom4j/Point.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Point.java 2009-12-14 23:44:34 UTC (rev 20) +++ trunk/src/net/sourceforge/geom4j/Point.java 2009-12-18 15:30:14 UTC (rev 21) @@ -46,7 +46,7 @@ Point p = (Point) obj; return Config.equal(x, p.x) && Config.equal(y, p.y); } - return super.equals(obj); + return false; } @Override Modified: trunk/src/net/sourceforge/geom4j/PointPair.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointPair.java 2009-12-14 23:44:34 UTC (rev 20) +++ trunk/src/net/sourceforge/geom4j/PointPair.java 2009-12-18 15:30:14 UTC (rev 21) @@ -53,7 +53,7 @@ return firstPoint.equals(pp.firstPoint) && secondPoint.equals(pp.secondPoint) || firstPoint.equals(pp.secondPoint) && secondPoint.equals(pp.firstPoint); } - return super.equals(obj); + return false; } public double distance() { Modified: trunk/src/net/sourceforge/geom4j/PointSet.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PointSet.java 2009-12-14 23:44:34 UTC (rev 20) +++ trunk/src/net/sourceforge/geom4j/PointSet.java 2009-12-18 15:30:14 UTC (rev 21) @@ -33,6 +33,9 @@ */ @Override public boolean equals(Object obj) { + if (this == obj) { + return true; + } if (obj instanceof PointSet) { return figures.equals(((PointSet) obj).figures); } Modified: trunk/src/net/sourceforge/geom4j/Polygon.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-14 23:44:34 UTC (rev 20) +++ trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-18 15:30:14 UTC (rev 21) @@ -65,11 +65,14 @@ @Override public boolean equals(Object obj) { + if (this == obj) { + return true; + } if (obj instanceof Polygon) { Polygon p = (Polygon) obj; return getSegmentSet().equals(p.getSegmentSet()); } - return super.equals(obj); + return false; } @Override Modified: trunk/src/net/sourceforge/geom4j/Segment.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-14 23:44:34 UTC (rev 20) +++ trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-18 15:30:14 UTC (rev 21) @@ -40,12 +40,15 @@ @Override public boolean equals(Object obj) { + if (this == obj) { + return true; + } if (obj instanceof Segment) { Segment s = (Segment) obj; return startPoint.equals(s.startPoint) && endPoint.equals(s.endPoint) || startPoint.equals(s.endPoint) && endPoint.equals(s.startPoint); } - return super.equals(obj); + return false; } @Override This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-14 23:44:49
|
Revision: 20 http://geom4j.svn.sourceforge.net/geom4j/?rev=20&view=rev Author: skhenkin Date: 2009-12-14 23:44:34 +0000 (Mon, 14 Dec 2009) Log Message: ----------- BinaryTreeBasedSmartQueue switched to AVLTree instead of a simple BinarySearchTree Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java trunk/src/net/sourceforge/geom4j/util/AVLTree.java trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-14 22:57:47 UTC (rev 19) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-14 23:44:34 UTC (rev 20) @@ -97,7 +97,7 @@ double X1 = 0, X2 = 1000, Y1 = 0, Y2 = 1000; SegmentSet ss = new SegmentSet(); Random r = new Random(); - for (int i = 0; i < 100; i++) { + for (int i = 0; i < 300; i++) { double x1 = r.nextDouble()*(X2-X1)+X1; double y1 = r.nextDouble()*(Y2-Y1)+Y1; double x2 = r.nextDouble()*(X2-X1)+X1; Modified: trunk/src/net/sourceforge/geom4j/util/AVLTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-14 22:57:47 UTC (rev 19) +++ trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-14 23:44:34 UTC (rev 20) @@ -28,7 +28,11 @@ * are performed with the complexity of O(log n), * where n is the number of elements in the tree. * This is achieved by keeping the tree balanced (for each node - * heights of its left and right subtrees differ at most by 1). + * heights of its left and right subtrees differ at most by 1). + * This balance is restored when needed using tree transformations + * called "rotations". + * See http://sky.fit.qut.edu.au/~maire/avl/System/AVLTree.html for more + * information and nice graphical explanation of rotations. * * @param <E> type of values stored in the tree * Modified: trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2009-12-14 22:57:47 UTC (rev 19) +++ trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2009-12-14 23:44:34 UTC (rev 20) @@ -18,11 +18,9 @@ import java.util.Comparator; /** - * "Smarter" implementation of SmartQueue based on a binary search tree. - * It takes on average O(log n) time to insert/remove/swap - * or get prev/next elements. - * There's still a room for performance improvements using some kind - * of self-balancing trees (like AVL-trees or Red-Black trees). + * "Smarter" implementation of SmartQueue based on a self-balancing + * binary search tree (AVL tree). + * It takes O(log n) time to insert/remove/swap or get prev/next elements. * * Actually this is a binary search tree with two added operations: * poll() - for extracting the first tree element; @@ -30,7 +28,7 @@ * * @author Sergey Khenkin */ -public class BinaryTreeBasedSmartQueue<E> extends BinarySearchTree<E> +public class BinaryTreeBasedSmartQueue<E> extends AVLTree<E> implements SmartQueue<E> { public BinaryTreeBasedSmartQueue() { This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-14 22:57:56
|
Revision: 19 http://geom4j.svn.sourceforge.net/geom4j/?rev=19&view=rev Author: skhenkin Date: 2009-12-14 22:57:47 +0000 (Mon, 14 Dec 2009) Log Message: ----------- AVL tree implementation completed Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/util/AVLTree.java trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java trunk/src/net/sourceforge/geom4j/util/SearchTree.java Modified: trunk/src/net/sourceforge/geom4j/util/AVLTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-10 21:16:10 UTC (rev 18) +++ trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-14 22:57:47 UTC (rev 19) @@ -41,6 +41,21 @@ * Contains balance factor for each node. */ protected class AVLNode extends Node { + + public int height = 1; + + public AVLNode(E value, AVLNode parent) { + super(value, parent); + } + + public final int getLeftHeight() { + return left == null ? 0 : getLeft().height; + } + + public final int getRightHeight() { + return right == null ? 0 : getRight().height; + } + /** * Each node can have one of the following balance factors * @@ -58,12 +73,34 @@ * was lost from the right sub-tree) it will require re-balancing. * This is achieved by performing a rotation about this node. */ - public int balanceFactor = 0; - - public AVLNode(E value, Node parent) { - super(value, parent); + public final int getBalanceFactor() { + return getRightHeight() - getLeftHeight(); } - + + @Override + public AVLNode getLeft() { + return (AVLNode) super.getLeft(); + } + + @Override + public AVLNode getParent() { + return (AVLNode) super.getParent(); + } + + @Override + public AVLNode getRight() { + return (AVLNode) super.getRight(); + } + + public boolean isUnbalanced() { + int balanceFactor = getBalanceFactor(); + return balanceFactor < -1 || balanceFactor > 1; + } + + /** Recalculate height for the node */ + public void recalculateHeight() { + height = Math.max(getLeftHeight(), getRightHeight()) + 1; + } } /** Create an empty tree of comparable elements */ @@ -77,15 +114,139 @@ } @Override - protected Node insertNode(E e, Node parent) { - // TODO add code for balancing - return super.insertNode(e, parent); + protected AVLNode insertChildNode(E e, Node parent, int c) { + AVLNode insertedNode = (AVLNode) super.insertChildNode(e, parent, c); + updateBalance(insertedNode); + return insertedNode; } @Override - protected void removeNode(Node node) { - // TODO add code for balancing - super.removeNode(node); + protected AVLNode createNode(E e, Node parent) { + return new AVLNode(e, (AVLNode) parent); } + /** Update balance node and all nodes above it */ + private void updateBalance(AVLNode node) { + while (node != null) { + node.recalculateHeight(); + AVLNode parentNode = node.getParent(); + if (node.isUnbalanced()) { + balanceNode(node); + } + node = parentNode; + } + } + + private void balanceNode(AVLNode node) { + int balanceFactor = node.getBalanceFactor(); + assert balanceFactor == -2 || balanceFactor == 2 : balanceFactor; + if (balanceFactor < 0) { + assert balanceFactor == -2 : balanceFactor; + AVLNode leftNode = node.getLeft(); + if (leftNode.getBalanceFactor() <= 0) { // LL rotation + rotateLL(node, leftNode); + } else { // LR rotation + assert leftNode.getBalanceFactor() == 1 : leftNode.getBalanceFactor(); + rotateLR(node, leftNode, leftNode.getRight()); + } + } else { + assert balanceFactor == 2 : balanceFactor; + AVLNode rightNode = node.getRight(); + if (rightNode.getBalanceFactor() >= 0) { // RR rotation + rotateRR(node, rightNode); + } else { // RL rotation + assert rightNode.getBalanceFactor() == -1 : rightNode.getBalanceFactor(); + rotateRL(node, rightNode, rightNode.getLeft()); + } + } + } + + /** LL-rotation */ + private void rotateLL(AVLNode node, AVLNode leftNode) { + node.left = leftNode.right; + if (node.left != null) { + node.left.parent = node; + } + node.recalculateHeight(); + updateParent(leftNode, node); + leftNode.right = node; + node.parent = leftNode; + leftNode.recalculateHeight(); + } + + /** RR-rotation */ + private void rotateRR(AVLNode node, AVLNode rightNode) { + node.right = rightNode.left; + if (node.right != null) { + node.right.parent = node; + } + node.recalculateHeight(); + updateParent(rightNode, node); + rightNode.left = node; + node.parent = rightNode; + rightNode.recalculateHeight(); + } + + /** LR-rotation */ + private void rotateLR(AVLNode node, AVLNode leftNode, AVLNode rightLeftNode) { + node.left = rightLeftNode.right; + if (node.left != null) { + node.left.parent = node; + } + node.recalculateHeight(); + leftNode.right = rightLeftNode.left; + if (leftNode.right != null) { + leftNode.right.parent = leftNode; + } + leftNode.recalculateHeight(); + updateParent(rightLeftNode, node); + rightLeftNode.left = leftNode; + leftNode.parent = rightLeftNode; + rightLeftNode.right = node; + node.parent = rightLeftNode; + rightLeftNode.recalculateHeight(); + } + + /** RL-rotation */ + private void rotateRL(AVLNode node, AVLNode rightNode, AVLNode leftRightNode) { + node.right = leftRightNode.left; + if (node.right != null) { + node.right.parent = node; + } + node.recalculateHeight(); + rightNode.left = leftRightNode.right; + if (rightNode.left != null) { + rightNode.left.parent = rightNode; + } + rightNode.recalculateHeight(); + updateParent(leftRightNode, node); + leftRightNode.right = rightNode; + rightNode.parent = leftRightNode; + leftRightNode.left = node; + node.parent = leftRightNode; + leftRightNode.recalculateHeight(); + } + + /** Update two-way parent-child reference to a new child */ + private void updateParent(AVLNode newChild, AVLNode oldChild) { + newChild.parent = oldChild.parent; + if (oldChild.parent != null) { + if (oldChild.parent.left == oldChild) { + oldChild.parent.left = newChild; + } else { + oldChild.parent.right = newChild; + } + } else { + root = newChild; + } + } + + @Override + protected AVLNode removeNode(Node node) { + AVLNode removedNode = (AVLNode) super.removeNode(node); + updateBalance(removedNode.getParent()); + return removedNode; + } + + } Modified: trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java 2009-12-10 21:16:10 UTC (rev 18) +++ trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java 2009-12-14 22:57:47 UTC (rev 19) @@ -16,7 +16,10 @@ package net.sourceforge.geom4j.util; import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; +import java.util.Random; + import org.junit.Before; import org.junit.Test; @@ -31,7 +34,6 @@ return new AVLTree<Integer>(); } - @Test public void testHeight() { SearchTree<Integer> t = createBinaryTree( @@ -39,10 +41,70 @@ assertEquals(4, t.height()); t = createBinaryTree( + new Integer[] {1, 2, 3}); + assertEquals(2, t.height()); + + t = createBinaryTree( new Integer[] {7, 11, 17, 23, 15, 35}); assertEquals(3, t.height()); t = createEmptyBinaryTree(); assertEquals(0, t.height()); } + + @Test + public void testRandomTreeInBalance() { + Integer[] values = createRandomUniqueArray(3000, 10000); + AVLTree<Integer> t = (AVLTree<Integer>) createBinaryTree(values); + assertTrue(t.isBalanced()); + } + + @Test + public void testRandomTreeHeight() { + Integer[] values = createRandomUniqueArray(3000, 10000); + SearchTree<Integer> simple = new BinarySearchTree<Integer>(); + SearchTree<Integer> balanced = new AVLTree<Integer>(); + populateTree(simple, values); + populateTree(balanced, values); + assertTrue(balanced.height() < simple.height()); + } + + @Test + public void testRemoval() { + SearchTree<Integer> t = createBinaryTree( + new Integer[] {8, + 4, 12, + 2, 6, 10, 14, + 1, 3, 5, 7, 9, 11, 13, 15}); + for (Integer i: new Integer[] {6, 5, 7, 1, 2, 4, 3, 13, + 15, 14, 9, 8, 11, 10, 12}) { + t.remove(i); + assertTrue("Became unbalanced after removing " + i, t.isBalanced()); + } + assertEquals(0, t.size()); + assertEquals(0, t.height()); + } + + @Test + public void testBalanceInvariantOnRandomOperations() { + int maxN = 1000; // values picked from [0..maxN) interval + int n = 10000; // number of insertions/deletions + int k = 100; // bulk size + SearchTree<Integer> t = createEmptyBinaryTree(); + Random r = new Random(); + for (int i = 0; i < n/k; i++) { + if (r.nextBoolean()) { + for (int j = 0; j < k; j++) { + t.insert(r.nextInt(maxN)); + assertTrue(t.isBalanced()); + } + } else { + for (int j = 0; j < k; j++) { + t.remove(r.nextInt(maxN)); + assertTrue(t.isBalanced()); + } + } + //System.out.println(t.size() + ", " + t.height()); + } + } } Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-10 21:16:10 UTC (rev 18) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-14 22:57:47 UTC (rev 19) @@ -51,6 +51,39 @@ this.value = value; this.parent = parent; } + + public E getValue() { + return value; + } + + public void setValue(E value) { + this.value = value; + } + + public Node getLeft() { + return left; + } + + public void setLeft(Node left) { + this.left = left; + } + + public Node getRight() { + return right; + } + + public void setRight(Node right) { + this.right = right; + } + + public Node getParent() { + return parent; + } + + public void setParent(Node parent) { + this.parent = parent; + } + } /** Root of the tree */ @@ -98,7 +131,7 @@ */ public boolean insert(E e) { if (root == null) { - root = new Node(e, null); + root = createNode(e, null); return true; } Node node = root; @@ -115,15 +148,21 @@ node = node.right; } } while (node != null); + insertChildNode(e, parent, c); + return true; + } + + protected Node insertChildNode(E e, Node parent, int c) { + Node childNode = createNode(e, parent); if (c < 0) { - parent.left = insertNode(e, parent); + parent.left = childNode; } else { - parent.right = insertNode(e, parent); + parent.right = childNode; } - return true; + return childNode; } - protected Node insertNode(E e, Node parent) { + protected Node createNode(E e, Node parent) { return new Node(e, parent); } @@ -151,14 +190,10 @@ return false; } - protected void removeNode(Node node) { - if (node.left == null && node.right == null) { // remove node - updateNodeReferences(node, null); - } else if (node.left == null){ // replace node with its single right child - updateNodeReferences(node, node.right); - } else if (node.right == null){ // replace node with its single left child - updateNodeReferences(node, node.left); - } else { + /** Return the node which was actually removed */ + protected Node removeNode(Node node) { + Node removed = removeNodeInPlace(node); + if (removed == null) { /* We can either replace the node with the biggest element of its * left subtree or with the smallest element of its right subtree. * We randomize the selection of this element to prevent tree @@ -170,17 +205,33 @@ Node predecessor = previousNode(node); node.value = predecessor.value; // remove predecessor (it can have at most one child) - removeNode(predecessor); + removed = removeNodeInPlace(predecessor); } else { // replace node value with its in-order successor's value Node successor = nextNode(node); node.value = successor.value; // remove successor (it can have at most one child) - removeNode(successor); + removed = removeNodeInPlace(successor); } } + return removed; } + /** Tries to remove the node specified if it doesn't have one of the children */ + protected Node removeNodeInPlace(Node node) { + if (node.left != null && node.right != null) { + return null; + } + if (node.left == null && node.right == null) { // remove node + updateNodeReferences(node, null); + } else if (node.left == null){ // replace node with its single right child + updateNodeReferences(node, node.right); + } else if (node.right == null){ // replace node with its single left child + updateNodeReferences(node, node.left); + } + return node; + } + private void updateNodeReferences(Node node, Node replacement) { if (node.parent == null) { // node == root root = replacement; @@ -374,4 +425,22 @@ public boolean isEmpty() { return root == null; } + + /** + * Check if the tree is balanced, + * i.e. balance factor of each node is between -1 and +1. + */ + @Override + public boolean isBalanced() { + return isNodeBalanced(root); + } + + private boolean isNodeBalanced(Node node) { + if (node == null) { + return true; + } + return isNodeBalanced(node.left) && isNodeBalanced(node.right) + && Math.abs(heightNode(node.left) - heightNode(node.right)) <= 1; + } + } Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java 2009-12-10 21:16:10 UTC (rev 18) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java 2009-12-14 22:57:47 UTC (rev 19) @@ -17,7 +17,9 @@ import static org.junit.Assert.*; +import java.util.ArrayList; import java.util.Arrays; +import java.util.Collections; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedList; @@ -74,13 +76,33 @@ } @Test - public void testRandomTree() { + public void testRandomTreeInsertion() { Integer[] values = createRandomUniqueArray(3000, 10000); SearchTree<Integer> t = createBinaryTree(values); Arrays.sort(values); assertTrue(listsEqual(values, t.toList())); assertEquals(values.length, t.size()); } + + @Test + public void testRandomTreeRemoval() { + int maxN = 10000; // values inserted from [0..maxN) interval + int n = 3000; // number of insertions + int k = 2500; // number of deletions + Integer[] ints = createRandomUniqueArray(n, maxN); + SearchTree<Integer> t = createBinaryTree(ints); + ArrayList<Integer> values = new ArrayList<Integer>(ints.length); + Collections.addAll(values, ints); + Collections.sort(values); + Random r = new Random(); + for (int i = 0; i < k; i++) { + int j = r.nextInt(values.size()); + t.remove(values.get(j)); + values.remove(j); + } + assertTrue(listsEqual(values.toArray(new Integer[0]), t.toList())); + assertEquals(values.size(), t.size()); + } @Test public void testSize() { @@ -131,7 +153,7 @@ return true; } - private Integer[] createRandomUniqueArray(int size, int maxValue) { + protected Integer[] createRandomUniqueArray(int size, int maxValue) { Random r = new Random(); Set<Integer> used = new HashSet<Integer>(); Integer[] values = new Integer[size]; @@ -158,7 +180,7 @@ */ protected abstract SearchTree<Integer> createEmptyBinaryTree(); - private void populateTree(SearchTree<Integer> tree, Integer[] values) { + protected void populateTree(SearchTree<Integer> tree, Integer[] values) { for (int i: values) { tree.insert(i); } Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-10 21:16:10 UTC (rev 18) +++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-14 22:57:47 UTC (rev 19) @@ -68,4 +68,7 @@ /** Check if tree contains elements */ boolean isEmpty(); + + /** Check if the tree is balanced */ + boolean isBalanced(); } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-10 21:16:17
|
Revision: 18 http://geom4j.svn.sourceforge.net/geom4j/?rev=18&view=rev Author: skhenkin Date: 2009-12-10 21:16:10 +0000 (Thu, 10 Dec 2009) Log Message: ----------- Preparations for adding AVL tree code. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java Added Paths: ----------- trunk/src/net/sourceforge/geom4j/util/AVLTree.java trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java Added: trunk/src/net/sourceforge/geom4j/util/AVLTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/AVLTree.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-10 21:16:10 UTC (rev 18) @@ -0,0 +1,91 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j.util; + +import java.util.Comparator; + +/** + * AVL tree is a kind of self-balancing binary tree. + * Stores elements of type E. + * Guarantees that all the following operations: + * insertion, + * removal, + * checking if element is in the tree, + * getting first or last element + * are performed with the complexity of O(log n), + * where n is the number of elements in the tree. + * This is achieved by keeping the tree balanced (for each node + * heights of its left and right subtrees differ at most by 1). + * + * @param <E> type of values stored in the tree + * + * @author Sergey Khenkin + */ +public class AVLTree<E> extends BinarySearchTree<E> { + + /** + * AVL tree node element. + * Contains balance factor for each node. + */ + protected class AVLNode extends Node { + /** + * Each node can have one of the following balance factors + * + * Left-High (balance factor -1) + * The left-sub tree is one level taller than the right-sub tree + * + * Balanced (balance factor 0) + * The left and right sub-trees are both the same heights + * + * Right-High (balance factor +1) + * The right sub-tree is one level taller than the left-sub tree. + * + * If the balance of a node becomes -2 (it was left high and a level + * was lost from the left sub-tree) or +2 (it was right high and a level + * was lost from the right sub-tree) it will require re-balancing. + * This is achieved by performing a rotation about this node. + */ + public int balanceFactor = 0; + + public AVLNode(E value, Node parent) { + super(value, parent); + } + + } + + /** Create an empty tree of comparable elements */ + public AVLTree() { + super(); + } + + /** Create an empty tree with comparator provided */ + public AVLTree(Comparator<? super E> comparator) { + super(comparator); + } + + @Override + protected Node insertNode(E e, Node parent) { + // TODO add code for balancing + return super.insertNode(e, parent); + } + + @Override + protected void removeNode(Node node) { + // TODO add code for balancing + super.removeNode(node); + } + +} Added: trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java 2009-12-10 21:16:10 UTC (rev 18) @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j.util; + +import static org.junit.Assert.assertEquals; + +import org.junit.Before; +import org.junit.Test; + +public class AVLTreeTest extends BinarySearchTreeTestBase { + + @Before + public void setUp() throws Exception { + } + + @Override + protected SearchTree<Integer> createEmptyBinaryTree() { + return new AVLTree<Integer>(); + } + + + @Test + public void testHeight() { + SearchTree<Integer> t = createBinaryTree( + new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}); + assertEquals(4, t.height()); + + t = createBinaryTree( + new Integer[] {7, 11, 17, 23, 15, 35}); + assertEquals(3, t.height()); + + t = createEmptyBinaryTree(); + assertEquals(0, t.height()); + } +} Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-05 21:31:07 UTC (rev 17) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-10 21:16:10 UTC (rev 18) @@ -116,12 +116,16 @@ } } while (node != null); if (c < 0) { - parent.left = new Node(e, parent); + parent.left = insertNode(e, parent); } else { - parent.right = new Node(e, parent); + parent.right = insertNode(e, parent); } return true; } + + protected Node insertNode(E e, Node parent) { + return new Node(e, parent); + } /** * Remove element e from the tree. Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-05 21:31:07 UTC (rev 17) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-10 21:16:10 UTC (rev 18) @@ -1,140 +1,47 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + package net.sourceforge.geom4j.util; -import static org.junit.Assert.*; +import static org.junit.Assert.assertEquals; -import java.util.Arrays; -import java.util.HashSet; -import java.util.Iterator; -import java.util.LinkedList; -import java.util.List; -import java.util.Random; -import java.util.Set; - import org.junit.Before; import org.junit.Test; -public class BinarySearchTreeTest { +public class BinarySearchTreeTest extends BinarySearchTreeTestBase { @Before public void setUp() throws Exception { } - @Test - public void testSmallTree() { - SearchTree<Integer> t = createBinaryTree( - new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}); - assertEquals(3, t.first()); - assertEquals(17, t.last()); - assertEquals(7, t.next(6)); - assertEquals(10, t.previous(11)); - assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 7, 9, 10, 11, 17}, - t.toList())); - assertTrue(t.contains(7)); - t.remove(7); - assertFalse(t.contains(7)); - assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 9, 10, 11, 17}, - t.toList())); - assertTrue(t.contains(9)); - t.remove(9); - assertFalse(t.contains(9)); - assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 10, 11, 17}, - t.toList())); - assertTrue(t.contains(5)); - t.remove(5); - assertFalse(t.contains(5)); - assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11, 17}, - t.toList())); - assertTrue(t.contains(17)); - t.remove(17); - assertFalse(t.contains(17)); - assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11}, - t.toList())); + @Override + protected SearchTree<Integer> createEmptyBinaryTree() { + return new BinarySearchTree<Integer>(); } - + @Test - public void testRandomTree() { - Integer[] values = createRandomUniqueArray(3000, 10000); - SearchTree<Integer> t = createBinaryTree(values); - Arrays.sort(values); - assertTrue(listsEqual(values, t.toList())); - assertEquals(values.length, t.size()); - } - - @Test - public void testSizeAndHeight() { + public void testHeight() { SearchTree<Integer> t = createBinaryTree( new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}); - assertEquals(9, t.size()); assertEquals(4, t.height()); - t = new BinarySearchTree<Integer>(); - assertEquals(0, t.size()); + t = createBinaryTree( + new Integer[] {7, 11, 17, 23, 15, 35}); + assertEquals(5, t.height()); + + t = createEmptyBinaryTree(); assertEquals(0, t.height()); } - - @Test - public void testIterator() { - Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}; - SearchTree<Integer> t = createBinaryTree(values); - Arrays.sort(values); - List<Integer> treeValues = new LinkedList<Integer>(); - for (Integer i: t) { - treeValues.add(i); - } - assertTrue(Arrays.equals(values, treeValues.toArray())); - } - - @Test - public void testIteratorRemoval() { - Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}; - SearchTree<Integer> t = createBinaryTree(values); - Arrays.sort(values); - List<Integer> treeValues = new LinkedList<Integer>(); - Iterator<Integer> i = t.iterator(); - while (i.hasNext()) { - Integer v = i.next(); - treeValues.add(v); - i.remove(); - } - assertTrue(Arrays.equals(values, treeValues.toArray())); - } - - - private boolean listsEqual(Integer[] values, List<Integer> list) { - if (values.length != list.size()) - return false; - int i = 0; - for (Integer v: list) { - if (!v.equals(values[i++])) - return false; - } - return true; - } - - private Integer[] createRandomUniqueArray(int size, int maxValue) { - Random r = new Random(); - Set<Integer> used = new HashSet<Integer>(); - Integer[] values = new Integer[size]; - for (int i = 0; i < size; i++) { - Integer v; - do { - v = r.nextInt(maxValue); - } while (used.contains(v)); - values[i] = v; - used.add(v); - } - return values; - } - - private SearchTree<Integer> createBinaryTree(Integer[] values) { - SearchTree<Integer> tree = new BinarySearchTree<Integer>(); - populateTree(tree, values); - return tree; - } - - private void populateTree(SearchTree<Integer> tree, Integer[] values) { - for (int i: values) { - tree.insert(i); - } - } } Added: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java 2009-12-10 21:16:10 UTC (rev 18) @@ -0,0 +1,166 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j.util; + +import static org.junit.Assert.*; + +import java.util.Arrays; +import java.util.HashSet; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.Random; +import java.util.Set; + +import org.junit.Before; +import org.junit.Test; + +/** + * Basic class for testing binary search tree functionality. + * All implementation-specific details should be tested in + * subclasses. + * + * @author Sergey Khenkin + */ +public abstract class BinarySearchTreeTestBase { + + @Before + public void setUp() throws Exception { + } + + @Test + public void testSmallTree() { + SearchTree<Integer> t = createBinaryTree( + new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}); + assertEquals(3, t.first()); + assertEquals(17, t.last()); + assertEquals(7, t.next(6)); + assertEquals(10, t.previous(11)); + assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 7, 9, 10, 11, 17}, + t.toList())); + assertTrue(t.contains(7)); + t.remove(7); + assertFalse(t.contains(7)); + assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 9, 10, 11, 17}, + t.toList())); + assertTrue(t.contains(9)); + t.remove(9); + assertFalse(t.contains(9)); + assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 10, 11, 17}, + t.toList())); + assertTrue(t.contains(5)); + t.remove(5); + assertFalse(t.contains(5)); + assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11, 17}, + t.toList())); + assertTrue(t.contains(17)); + t.remove(17); + assertFalse(t.contains(17)); + assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11}, + t.toList())); + } + + @Test + public void testRandomTree() { + Integer[] values = createRandomUniqueArray(3000, 10000); + SearchTree<Integer> t = createBinaryTree(values); + Arrays.sort(values); + assertTrue(listsEqual(values, t.toList())); + assertEquals(values.length, t.size()); + } + + @Test + public void testSize() { + SearchTree<Integer> t = createBinaryTree( + new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}); + assertEquals(9, t.size()); + + t = createEmptyBinaryTree(); + assertEquals(0, t.size()); + } + + @Test + public void testIterator() { + Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}; + SearchTree<Integer> t = createBinaryTree(values); + Arrays.sort(values); + List<Integer> treeValues = new LinkedList<Integer>(); + for (Integer i: t) { + treeValues.add(i); + } + assertTrue(Arrays.equals(values, treeValues.toArray())); + } + + @Test + public void testIteratorRemoval() { + Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}; + SearchTree<Integer> t = createBinaryTree(values); + Arrays.sort(values); + List<Integer> treeValues = new LinkedList<Integer>(); + Iterator<Integer> i = t.iterator(); + while (i.hasNext()) { + Integer v = i.next(); + treeValues.add(v); + i.remove(); + } + assertTrue(Arrays.equals(values, treeValues.toArray())); + } + + + private boolean listsEqual(Integer[] values, List<Integer> list) { + if (values.length != list.size()) + return false; + int i = 0; + for (Integer v: list) { + if (!v.equals(values[i++])) + return false; + } + return true; + } + + private Integer[] createRandomUniqueArray(int size, int maxValue) { + Random r = new Random(); + Set<Integer> used = new HashSet<Integer>(); + Integer[] values = new Integer[size]; + for (int i = 0; i < size; i++) { + Integer v; + do { + v = r.nextInt(maxValue); + } while (used.contains(v)); + values[i] = v; + used.add(v); + } + return values; + } + + protected SearchTree<Integer> createBinaryTree(Integer[] values) { + SearchTree<Integer> tree = createEmptyBinaryTree(); + populateTree(tree, values); + return tree; + } + + /** + * This method should be overridden in each subclass so that + * it creates and returns a tree of that subclass. + */ + protected abstract SearchTree<Integer> createEmptyBinaryTree(); + + private void populateTree(SearchTree<Integer> tree, Integer[] values) { + for (int i: values) { + tree.insert(i); + } + } +} This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-05 21:31:18
|
Revision: 17 http://geom4j.svn.sourceforge.net/geom4j/?rev=17&view=rev Author: skhenkin Date: 2009-12-05 21:31:07 +0000 (Sat, 05 Dec 2009) Log Message: ----------- Usage demo for figure contains() method added Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/demo/Demo.java Modified: trunk/src/net/sourceforge/geom4j/demo/Demo.java =================================================================== --- trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-05 17:47:30 UTC (rev 16) +++ trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-05 21:31:07 UTC (rev 17) @@ -45,7 +45,8 @@ closestPairOfPointsDemo(); pointInsidePolygonDemo(); segmentIntersectionDemo(); - simplePolygonDemo(); + simplePolygonDemo(); + contentDemo(); } /** @@ -197,4 +198,19 @@ System.out.println(String.format("Polygon %s is %ssimple", p2, p2.isSimple() ? "" : "not ")); } + + /** + * Demonstrate how to determine if one figure contains another + */ + private static void contentDemo() { + Figure square = new Polygon() + .addVertex(new Point(0, 0)) + .addVertex(new Point(100, 0)) + .addVertex(new Point(100, 100)) + .addVertex(new Point(0, 100)); + Figure segment = new Segment(new Point(100, 20), new Point(100, 40)); + if (square.contains(segment)) { + System.out.println("Square " + square + " contains segment " + segment); + } + } } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-05 17:47:39
|
Revision: 16 http://geom4j.svn.sourceforge.net/geom4j/?rev=16&view=rev Author: skhenkin Date: 2009-12-05 17:47:30 +0000 (Sat, 05 Dec 2009) Log Message: ----------- Polygon complexity test added. Interfaces and code cleaned up and refactored. Modified Paths: -------------- trunk/build.xml trunk/src/net/sourceforge/geom4j/CompoundFigure.java trunk/src/net/sourceforge/geom4j/Polygon.java trunk/src/net/sourceforge/geom4j/PolygonTest.java trunk/src/net/sourceforge/geom4j/Segment.java trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java trunk/src/net/sourceforge/geom4j/SegmentTest.java trunk/src/net/sourceforge/geom4j/demo/Demo.java trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java trunk/src/net/sourceforge/geom4j/util/SmartQueue.java trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java Modified: trunk/build.xml =================================================================== --- trunk/build.xml 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/build.xml 2009-12-05 17:47:30 UTC (rev 16) @@ -64,6 +64,7 @@ <batchtest fork="yes" todir="${test.reports.dir}"> <fileset dir="${src.dir}"> <include name="**/*Test*.java"/> + <exclude name="**/*TestBase*.java"/> </fileset> </batchtest> </junit> @@ -113,6 +114,7 @@ <batchtest fork="yes"> <fileset dir="${src.dir}"> <include name="**/*Test*.java"/> + <exclude name="**/*TestBase*.java"/> </fileset> </batchtest> </junit> Modified: trunk/src/net/sourceforge/geom4j/CompoundFigure.java =================================================================== --- trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-05 17:47:30 UTC (rev 16) @@ -54,7 +54,15 @@ public int size() { return figures.size(); } + + public boolean isEmpty() { + return figures.isEmpty(); + } + public void remove(Collection<? extends Figure> figs) { + figures.removeAll(figs); + } + /** * Hash code of a compound figure is defined as the sum of hash codes * of the figures of which it consists. Modified: trunk/src/net/sourceforge/geom4j/Polygon.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-05 17:47:30 UTC (rev 16) @@ -226,4 +226,13 @@ public List<Point> getVertices() { return vertices; } + + /** + * Check if the polygon is simple (i.e. its boundary does not cross itself) + */ + public boolean isSimple() { + PointSet intersections = getSegmentSet().getAllIntersectionPoints(); + intersections.remove(getVertices()); // we don't count vertices + return intersections.isEmpty(); + } } Modified: trunk/src/net/sourceforge/geom4j/PolygonTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/PolygonTest.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/PolygonTest.java 2009-12-05 17:47:30 UTC (rev 16) @@ -133,6 +133,22 @@ .addVertex(new Point(5, 7)) .addVertex(new Point(1, 8)); assertTrue(Config.equal(24-2-1.5-4.5-1.5, mess.getArea())); - } + + @Test + public void testSimplicity() { + assertTrue(p.isSimple()); + assertTrue(new Polygon() + .addVertex(new Point(10, 10)) + .addVertex(new Point(10, 20)) + .addVertex(new Point(20, 20)) + .addVertex(new Point(20, 10)) + .isSimple()); + assertFalse(new Polygon() + .addVertex(new Point(10, 10)) + .addVertex(new Point(10, 20)) + .addVertex(new Point(20, 10)) + .addVertex(new Point(20, 20)) + .isSimple()); + } } Modified: trunk/src/net/sourceforge/geom4j/Segment.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-05 17:47:30 UTC (rev 16) @@ -250,4 +250,46 @@ return 0; } } + + /** + * Get left endpoint (endpoint with the smaller x coordinate). + * If x coordinates of the endpoints are the same, return the + * endpoint with the smaller y coordinate. + */ + public Point getLeftPoint() { + Point p1 = startPoint; + Point p2 = endPoint; + if (Config.lessThan(p1.getX(), p2.getX())) { + return p1; + } else if (Config.lessThan(p2.getX(), p1.getX())) { + return p2; + } else { + if (Config.lessThan(p2.getY(), p1.getY())) { + return p2; + } else { + return p1; + } + } + } + + /** + * Get left endpoint (endpoint with the smaller x coordinate). + * If x coordinates of the endpoints are the same, return the + * endpoint with the smaller y coordinate. + */ + public Point getRightPoint() { + Point p1 = startPoint; + Point p2 = endPoint; + if (Config.lessThan(p1.getX(), p2.getX())) { + return p2; + } else if (Config.lessThan(p2.getX(), p1.getX())) { + return p1; + } else { + if (Config.lessThan(p1.getY(), p2.getY())) { + return p2; + } else { + return p1; + } + } + } } Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2009-12-05 17:47:30 UTC (rev 16) @@ -16,11 +16,8 @@ package net.sourceforge.geom4j; import java.util.Comparator; -import java.util.LinkedList; -import java.util.List; import net.sourceforge.geom4j.util.BinaryTreeBasedSmartQueue; -import net.sourceforge.geom4j.util.ListBasedSmartQueue; import net.sourceforge.geom4j.util.SmartQueue; /** @@ -70,9 +67,8 @@ * http://www.softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm * http://www.cs.wustl.edu/~pless/506/l4.html */ - static SegmentIntersectionAlgorithm BENTLEY_OTTMANN = new BentleyOttmannSegmentIntersectionAlgorithm(); + static SegmentIntersectionAlgorithm BENTLEY_OTTMANN = new SegmentIntersectionAlgorithm() { - class BentleyOttmannSegmentIntersectionAlgorithm implements SegmentIntersectionAlgorithm { SweepLineComparator sweepLineComparator = new SweepLineComparator(); EventComparator eventComparator = new EventComparator(); @@ -81,9 +77,9 @@ // initialization SmartQueue<Event> eventQueue = initializeEventQueue(segments); //SmartQueue<SweepLineSegment> sweepLine - // = new ListBasedSmartQueue<SweepLineSegment>(sweepLineComparator); - SmartQueue<SweepLineSegment> sweepLine = - new BinaryTreeBasedSmartQueue<SweepLineSegment>(sweepLineComparator); + // = new ListBasedSmartQueue<Segment>(sweepLineComparator); + SmartQueue<Segment> sweepLine = + new BinaryTreeBasedSmartQueue<Segment>(sweepLineComparator); PointSet intersections = new PointSet(); // process all events in the queue while (!eventQueue.isEmpty()) { @@ -96,381 +92,271 @@ } private SmartQueue<Event> initializeEventQueue(SegmentSet segments) { - List<Event> events = new LinkedList<Event>(); - for (Segment s : segments) { - events.add(new LeftEndpointEvent(new SweepLineSegment(s))); - events.add(new RightEndpointEvent(new SweepLineSegment(s))); - } //SmartQueue<Event> eventQueue = new ListBasedSmartQueue<Event>(eventComparator); SmartQueue<Event> eventQueue = new BinaryTreeBasedSmartQueue<Event>(eventComparator); - for (Event e : events) { - eventQueue.insert(e); + for (Segment s : segments) { + eventQueue.insert(new LeftEndpointEvent(s, sweepLineComparator)); + eventQueue.insert(new RightEndpointEvent(s, sweepLineComparator)); } return eventQueue; } + }; - public void setCompareBeforeSweepLine(boolean compareBefore) { - sweepLineComparator.setBefore(compareBefore); - } + /* + * Helper classes for Bentley-Ottmann algorithm + */ - /* - * Helper classes for Bentley-Ottmann algorithm - */ + /** + * Sweep line event. Events are stored in the event queue which is a + * priority queue which doesn't store duplicate elements. + */ + abstract class Event { + /** Segment left endpoint event type */ + public static final int EVENT_LEFT_ENDPOINT = 0; + /** Segment intersection event type */ + public static final int EVENT_INTERSECTION = 1; + /** Segment right endpoint event type */ + public static final int EVENT_RIGHT_ENDPOINT = 2; - /** - * Sweep line event. Events are stored in the event queue which is a - * priority queue which doesn't store duplicate elements. - * - * @author Sergey Khenkin - */ - abstract class Event { - /** Segment left endpoint event type */ - public static final int LEFT_ENDPOINT = 0; - /** Segment intersection event type */ - public static final int INTERSECTION = 1; - /** Segment right endpoint event type */ - public static final int RIGHT_ENDPOINT = 2; + protected SweepLineComparator sweepLineComparator = new SweepLineComparator(); + + public Event(SweepLineComparator sweepLineComparator) { + this.sweepLineComparator = sweepLineComparator; + } - /** Execute event-specific actions */ - public abstract void execute(SmartQueue<Event> eventQueue, - SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet); + /** Execute event-specific actions */ + public abstract void execute(SmartQueue<Event> eventQueue, + SmartQueue<Segment> sweepLine, PointSet intersectionSet); - public abstract int getType(); + public abstract int getType(); - /** Get the point associated with the event */ - public abstract Point getPoint(); + /** Get the point associated with the event */ + public abstract Point getPoint(); - /** - * Add intersection event if segments intersect and intersection point - * is to the right of the point being currently processed. It is - * important not to add intersections at the points to the left of - * currently processed one because we can end up in an infinite loop - * (moreover we never get back in the algorithm). - */ - protected void addIntersectionEvent( - SmartQueue<Event> eventQueue, SweepLineSegment seg1, - SweepLineSegment seg2, Point curPoint) { - if (seg1 != null && seg2 != null) { - for (Point p : seg1.getSegment().intersects(seg2.getSegment()) - .getPoints()) { - if (p.getX() >= curPoint.getX()) { - eventQueue.insert(new IntersectionEvent(p, seg1, seg2)); - } + /** + * Add intersection event if segments intersect and intersection point + * is to the right of the point being currently processed. It is + * important not to add intersections at the points to the left of + * currently processed one because we can end up in an infinite loop + * (moreover we never get back in the algorithm). + */ + protected void addIntersectionEvent( + SmartQueue<Event> eventQueue, Segment seg1, + Segment seg2, Point curPoint) { + if (seg1 != null && seg2 != null) { + for (Point p : seg1.intersects(seg2).getPoints()) { + if (p.getX() >= curPoint.getX()) { + eventQueue.insert(new IntersectionEvent(p, seg1, seg2, sweepLineComparator)); } } } } + } - /** - * Left endpoint event. Left end of a segment is reached. - */ - class LeftEndpointEvent extends Event { - SweepLineSegment sweepLineSegment; + /** + * Left endpoint event. Left end of a segment is reached. + */ + class LeftEndpointEvent extends Event { + Segment segment; - public LeftEndpointEvent(SweepLineSegment sweepLineSegment) { - this.sweepLineSegment = sweepLineSegment; - } - - /** - * On reaching left endpoint of a segment we insert this segment into - * the sweep line and add intersections of it with its nearest neighbors - * from top and bottom if they exist. - */ - @Override - public void execute(SmartQueue<Event> eventQueue, - SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet) { - sweepLineComparator.setBefore(true); - sweepLine.insert(sweepLineSegment); - SweepLineSegment segBefore = sweepLine.prev(sweepLineSegment); - SweepLineSegment segAfter = sweepLine.next(sweepLineSegment); - sweepLineComparator.setBefore(false); - addIntersectionEvent(eventQueue, segAfter, sweepLineSegment, - sweepLineSegment.getLeftPoint()); - addIntersectionEvent(eventQueue, sweepLineSegment, segBefore, - sweepLineSegment.getLeftPoint()); - } - - @Override - public Point getPoint() { - return sweepLineSegment.getLeftPoint(); - } - - @Override - public int getType() { - return LEFT_ENDPOINT; - } - - public String toString() { - return "<" + getType() + ", " + getPoint() + ", " - + sweepLineSegment + ">"; - } - - @Override - public boolean equals(Object obj) { - if (obj instanceof LeftEndpointEvent) { - LeftEndpointEvent lee = (LeftEndpointEvent) obj; - return sweepLineSegment.equals(lee.sweepLineSegment); - } - return false; - } + public LeftEndpointEvent(Segment segment, SweepLineComparator sweepLineComparator) { + super(sweepLineComparator); + this.segment = segment; } /** - * Right endpoint event. Right end of a segment is reached. + * On reaching left endpoint of a segment we insert this segment into + * the sweep line and add intersections of it with its nearest neighbors + * from top and bottom if they exist. */ - class RightEndpointEvent extends Event { - SweepLineSegment sweepLineSegment; + @Override + public void execute(SmartQueue<Event> eventQueue, + SmartQueue<Segment> sweepLine, PointSet intersectionSet) { + sweepLineComparator.setBefore(true); + sweepLine.insert(segment); + Segment segBefore = sweepLine.previous(segment); + Segment segAfter = sweepLine.next(segment); + sweepLineComparator.setBefore(false); + addIntersectionEvent(eventQueue, segAfter, segment, + segment.getLeftPoint()); + addIntersectionEvent(eventQueue, segment, segBefore, + segment.getLeftPoint()); + } - public RightEndpointEvent(SweepLineSegment sweepLineSegment) { - this.sweepLineSegment = sweepLineSegment; - } + @Override + public Point getPoint() { + return segment.getLeftPoint(); + } - /** - * On reaching right endpoint of a segment we check for intersection of - * segment's neighbors from top and bottom on the sweep line and add a - * new intersection event when appropriate. After that just remove the - * segment from the sweep line. - */ - @Override - public void execute(SmartQueue<Event> eventQueue, - SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet) { - SweepLineSegment segBefore = sweepLine.prev(sweepLineSegment); - SweepLineSegment segAfter = sweepLine.next(sweepLineSegment); - addIntersectionEvent(eventQueue, segAfter, segBefore, - sweepLineSegment.getRightPoint()); - sweepLine.remove(sweepLineSegment); - } + @Override + public int getType() { + return EVENT_LEFT_ENDPOINT; + } - @Override - public Point getPoint() { - return sweepLineSegment.getRightPoint(); - } + public String toString() { + return "<" + getType() + ", " + getPoint() + ", " + + segment + ">"; + } - @Override - public int getType() { - return RIGHT_ENDPOINT; + @Override + public boolean equals(Object obj) { + if (obj instanceof LeftEndpointEvent) { + LeftEndpointEvent lee = (LeftEndpointEvent) obj; + return segment.equals(lee.segment); } + return false; + } + } - public String toString() { - return "<" + getType() + ", " + getPoint() + ", " - + sweepLineSegment + ">"; - } + /** + * Right endpoint event. Right end of a segment is reached. + */ + class RightEndpointEvent extends Event { + Segment segment; - @Override - public boolean equals(Object obj) { - if (obj instanceof RightEndpointEvent) { - RightEndpointEvent ree = (RightEndpointEvent) obj; - return sweepLineSegment.equals(ree.sweepLineSegment); - } - return false; - } - + public RightEndpointEvent(Segment segment, SweepLineComparator sweepLineComparator) { + super(sweepLineComparator); + this.segment = segment; } /** - * Intersection event. Intersection point of two segments is reached. + * On reaching right endpoint of a segment we check for intersection of + * segment's neighbors from top and bottom on the sweep line and add a + * new intersection event when appropriate. After that just remove the + * segment from the sweep line. */ - class IntersectionEvent extends Event { - private Point p; - private SweepLineSegment sAbove; - private SweepLineSegment sBelow; + @Override + public void execute(SmartQueue<Event> eventQueue, + SmartQueue<Segment> sweepLine, PointSet intersectionSet) { + Segment segBefore = sweepLine.previous(segment); + Segment segAfter = sweepLine.next(segment); + addIntersectionEvent(eventQueue, segAfter, segBefore, + segment.getRightPoint()); + sweepLine.remove(segment); + } - public IntersectionEvent(Point p, SweepLineSegment sAbove, - SweepLineSegment sBelow) { - this.p = p; - this.sAbove = sAbove; - this.sBelow = sBelow; - } + @Override + public Point getPoint() { + return segment.getRightPoint(); + } - /** - * On reaching intersection point of two segments on the sweep line add - * this point to the list of intersections, then swap the intersecting - * segments on the sweep line and check if they now intersect with their - * new neighbors. If so add new intersection points accordingly. - */ - @Override - public void execute(SmartQueue<Event> eventQueue, - SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet) { - intersectionSet.add(p); - sweepLineComparator.setBefore(true); - sweepLine.swap(sAbove, sBelow); - sweepLineComparator.setBefore(false); - addIntersectionEvent(eventQueue, sAbove, sweepLine.prev(sAbove), p); - addIntersectionEvent(eventQueue, sweepLine.next(sBelow), sBelow, p); - } + @Override + public int getType() { + return EVENT_RIGHT_ENDPOINT; + } - @Override - public Point getPoint() { - return p; - } - - @Override - public int getType() { - return INTERSECTION; - } - - public String toString() { - return "<" + getType() + ", " + getPoint() + ", " + sAbove + ", " - + sBelow + ">"; - } - - @Override - public boolean equals(Object obj) { - if (obj instanceof IntersectionEvent) { - IntersectionEvent ie = (IntersectionEvent) obj; - return p.equals(ie.p) && sAbove.equals(ie.sAbove) - && sBelow.equals(ie.sBelow); - } - return false; - } + public String toString() { + return "<" + getType() + ", " + getPoint() + ", " + + segment + ">"; } - public class EventComparator implements Comparator<Event> { - - /** - * Events are sorted by x coordinate asc, then by y coordinate asc, then - * by type asc. Sorting by type is important as left endpoints should be - * processed before intersections before right endpoints in case of the - * points with equal coordinates. - */ - @Override - public int compare(Event e1, Event e2) { - Point p1 = e1.getPoint(); - Point p2 = e2.getPoint(); - if (Config.lessThan(p1.getX(), p2.getX())) { - return -1; - } else if (Config.lessThan(p2.getX(), p1.getX())) { - return 1; - } else { - if (Config.lessThan(p1.getY(), p2.getY())) { - return -1; - } else if (Config.lessThan(p2.getY(), p1.getY())) { - return 1; - } else { - if (e1.getType() < e2.getType()) { - return -1; - } else if (e1.getType() > e2.getType()) { - return 1; - } else { - return e1.equals(e2) ? 0 : -1; - } - } - } + @Override + public boolean equals(Object obj) { + if (obj instanceof RightEndpointEvent) { + RightEndpointEvent ree = (RightEndpointEvent) obj; + return segment.equals(ree.segment); } + return false; } - }; + } /** - * A wrapper class for a segment which sets segment ordering on the sweep - * line. - * + * Intersection event. Intersection point of two segments is reached. */ - class SweepLineSegment implements Comparable<SweepLineSegment> { - private Segment segment; + class IntersectionEvent extends Event { + private Point p; + private Segment sAbove; + private Segment sBelow; - public SweepLineSegment(Segment segment) { - this.segment = segment; + public IntersectionEvent(Point p, Segment sAbove, Segment sBelow, + SweepLineComparator sweepLineComparator) { + super(sweepLineComparator); + this.p = p; + this.sAbove = sAbove; + this.sBelow = sBelow; } - public Segment getSegment() { - return segment; - } - /** - * Segments are sorted from top to bottom by the y coordinate of their - * intersection with the sweep line. This order is kept during sweep - * line movement by appropriate swaps of the intersecting segments. + * On reaching intersection point of two segments on the sweep line add + * this point to the list of intersections, then swap the intersecting + * segments on the sweep line and check if they now intersect with their + * new neighbors. If so add new intersection points accordingly. */ @Override - public int compareTo(SweepLineSegment s) { - Point p1 = getLeftPoint(); - Point p2 = s.getLeftPoint(); - // p1 is always to the left of p2 or on the same vertical - Point q1 = getRightPoint(); - Point q2 = s.getRightPoint(); - int pos = relativePosition(p2, p1, q1); - if (pos != 0) { - return pos; - } else { - return -relativePosition(q2, p1, q1); - } + public void execute(SmartQueue<Event> eventQueue, + SmartQueue<Segment> sweepLine, PointSet intersectionSet) { + intersectionSet.add(p); + sweepLineComparator.setBefore(true); + sweepLine.swap(sAbove, sBelow); + sweepLineComparator.setBefore(false); + addIntersectionEvent(eventQueue, sAbove, sweepLine.previous(sAbove), p); + addIntersectionEvent(eventQueue, sweepLine.next(sBelow), sBelow, p); + } + @Override + public Point getPoint() { + return p; } - /** - * Check if p is above the segment [leftPoint, rightPoint]. - * - * @return -1 if p is above the segment 1 if p is below the segment 0 if - * p lies on the same line with segment endpoints - */ - public int relativePosition(Point p, Point leftPoint, Point rightPoint) { - Vector v1 = new Vector(leftPoint, rightPoint); - Vector v2 = new Vector(leftPoint, p); - double d = v1.crossProduct(v2); - if (d > 0) { // p2 is above [p1, q1] - return -1; - } else if (d < 0) { // p2 is below [p1, q1] - return 1; - } else { // p2 lies on (p1, q1) - return 0; - } + @Override + public int getType() { + return EVENT_INTERSECTION; } + public String toString() { + return "<" + getType() + ", " + getPoint() + ", " + sAbove + ", " + + sBelow + ">"; + } + @Override public boolean equals(Object obj) { - if (obj instanceof SweepLineSegment) { - SweepLineSegment sls = (SweepLineSegment) obj; - return segment.equals(sls.segment); + if (obj instanceof IntersectionEvent) { + IntersectionEvent ie = (IntersectionEvent) obj; + return p.equals(ie.p) && sAbove.equals(ie.sAbove) + && sBelow.equals(ie.sBelow); } return false; } + } - @Override - public int hashCode() { - return segment.hashCode(); - } + /** Comparator for events in the event queue */ + class EventComparator implements Comparator<Event> { - public Point getLeftPoint() { - Point p1 = segment.getStartPoint(); - Point p2 = segment.getEndPoint(); - if (p1.getX() < p2.getX()) { - return p1; - } else if (p1.getX() > p2.getX()) { - return p2; + /** + * Events are sorted by x coordinate asc, then by y coordinate asc, then + * by type asc. Sorting by type is important as left endpoints should be + * processed before intersections before right endpoints in case of the + * points with equal coordinates. + */ + @Override + public int compare(Event e1, Event e2) { + Point p1 = e1.getPoint(); + Point p2 = e2.getPoint(); + if (Config.lessThan(p1.getX(), p2.getX())) { + return -1; + } else if (Config.lessThan(p2.getX(), p1.getX())) { + return 1; } else { - if (p1.getY() <= p2.getY()) { - return p1; + if (Config.lessThan(p1.getY(), p2.getY())) { + return -1; + } else if (Config.lessThan(p2.getY(), p1.getY())) { + return 1; } else { - return p2; + if (e1.getType() < e2.getType()) { + return -1; + } else if (e1.getType() > e2.getType()) { + return 1; + } else { + return e1.equals(e2) ? 0 : -1; + } } } } - - public Point getRightPoint() { - Point p1 = segment.getStartPoint(); - Point p2 = segment.getEndPoint(); - if (p1.getX() > p2.getX()) { - return p1; - } else if (p1.getX() < p2.getX()) { - return p2; - } else { - if (p1.getY() >= p2.getY()) { - return p1; - } else { - return p2; - } - } - } - - public String toString() { - return segment.toString(); - } - } /** Comparator for segments stored in sweep line */ - class SweepLineComparator implements Comparator<SweepLineSegment> { + class SweepLineComparator implements Comparator<Segment> { private Point currentPoint; private boolean before = false; @@ -480,7 +366,7 @@ * line movement by appropriate swaps of the intersecting segments. */ @Override - public int compare(SweepLineSegment s1, SweepLineSegment s2) { + public int compare(Segment s1, Segment s2) { Point p1 = s1.getLeftPoint(); Point p2 = s2.getLeftPoint(); // p1 is always to the left of p2 or on the same vertical @@ -540,25 +426,6 @@ } } - /** - * Check if p is above the segment [leftPoint, rightPoint]. - * - * @return -1 if p is above the segment 1 if p is below the segment 0 if - * p lies on the same line with segment endpoints - */ - public int relativePosition(Point p, Point leftPoint, Point rightPoint) { - Vector v1 = new Vector(leftPoint, rightPoint); - Vector v2 = new Vector(leftPoint, p); - double d = v1.crossProduct(v2); - if (d > 0) { // p2 is above [p1, q1] - return -1; - } else if (d < 0) { // p2 is below [p1, q1] - return 1; - } else { // p2 lies on (p1, q1) - return 0; - } - } - public void setCurrentPoint(Point currentPoint) { this.currentPoint = currentPoint; } Modified: trunk/src/net/sourceforge/geom4j/SegmentTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentTest.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/SegmentTest.java 2009-12-05 17:47:30 UTC (rev 16) @@ -78,4 +78,27 @@ assertFalse(s1.contains(p4)); } + @Test + public void testLeftAndRightEndpoints() { + Point bottomLeft = new Point(1, 1); + Point bottomRight = new Point(2, 1); + Point topLeft = new Point(1, 2); + Point topRight = new Point(2, 2); + + Segment mainDiagonal = new Segment(topRight, bottomLeft); + assertEquals(bottomLeft, mainDiagonal.getLeftPoint()); + assertEquals(topRight, mainDiagonal.getRightPoint()); + + Segment secondDiagonal = new Segment(bottomRight, topLeft); + assertEquals(topLeft, secondDiagonal.getLeftPoint()); + assertEquals(bottomRight, secondDiagonal.getRightPoint()); + + Segment leftVertical = new Segment(topLeft, bottomLeft); + assertEquals(bottomLeft, leftVertical.getLeftPoint()); + assertEquals(topLeft, leftVertical.getRightPoint()); + + Segment topHorizontal = new Segment(topLeft, topRight); + assertEquals(topLeft, topHorizontal.getLeftPoint()); + assertEquals(topRight, topHorizontal.getRightPoint()); + } } Modified: trunk/src/net/sourceforge/geom4j/demo/Demo.java =================================================================== --- trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-05 17:47:30 UTC (rev 16) @@ -45,6 +45,7 @@ closestPairOfPointsDemo(); pointInsidePolygonDemo(); segmentIntersectionDemo(); + simplePolygonDemo(); } /** @@ -101,7 +102,7 @@ .addVertex(new Point(100, 100)) .addVertex(new Point(50, 100)) .addVertex(new Point(0, 50)); - System.out.println(String.format("The polygon %s is %sconvex", convex, convex.isConvex() ? "" : "not ")); + System.out.println(String.format("Polygon %s is %sconvex", convex, convex.isConvex() ? "" : "not ")); } /** @@ -174,4 +175,26 @@ SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); System.out.println("Segment intersections for the set " + segments + ": " + intersections); } + + /** + * Demonstrate polygon simplicity test + */ + private static void simplePolygonDemo() { + Polygon p1 = new Polygon() + .addVertex(new Point(0, 0)) + .addVertex(new Point(100, 0)) + .addVertex(new Point(100, 100)) + .addVertex(new Point(50, 100)) + .addVertex(new Point(0, 50)); + System.out.println(String.format("Polygon %s is %ssimple", + p1, p1.isSimple() ? "" : "not ")); + Polygon p2 = new Polygon() + .addVertex(new Point(0, 0)) + .addVertex(new Point(100, 100)) + .addVertex(new Point(100, 0)) + .addVertex(new Point(50, 100)) + .addVertex(new Point(0, 50)); + System.out.println(String.format("Polygon %s is %ssimple", + p2, p2.isSimple() ? "" : "not ")); + } } Modified: trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2009-12-05 17:47:30 UTC (rev 16) @@ -17,94 +17,46 @@ import java.util.Comparator; - /** * "Smarter" implementation of SmartQueue based on a binary search tree. * It takes on average O(log n) time to insert/remove/swap - * and O(1) to get prev/next elements. + * or get prev/next elements. * There's still a room for performance improvements using some kind * of self-balancing trees (like AVL-trees or Red-Black trees). * + * Actually this is a binary search tree with two added operations: + * poll() - for extracting the first tree element; + * swap() - for swapping two elements present in the tree. + * * @author Sergey Khenkin */ -public class BinaryTreeBasedSmartQueue<E> implements SmartQueue<E> { - class CustomBinarySearchTree extends BinarySearchTree<E> { - - public CustomBinarySearchTree() { - super(); - } - - public CustomBinarySearchTree(Comparator<? super E> comparator) { - super(comparator); - } - - public E poll() { - Node n = firstNode(root); - if (n == null) - return null; - removeNode(n); - return n.value; - } - - public void swap(E e1, E e2) { - Node n1 = findNode(e1); - Node n2 = findNode(e2); - if (n1 != null && n2 != null) { - n1.value = e2; - n2.value = e1; - } - } - - } - /** Tree that stores queue elements */ - private CustomBinarySearchTree tree = new CustomBinarySearchTree(); +public class BinaryTreeBasedSmartQueue<E> extends BinarySearchTree<E> + implements SmartQueue<E> { public BinaryTreeBasedSmartQueue() { - tree = new CustomBinarySearchTree(); + super(); } - public BinaryTreeBasedSmartQueue(Comparator<E> comparator) { - tree = new CustomBinarySearchTree(comparator); + public BinaryTreeBasedSmartQueue(Comparator<? super E> comparator) { + super(comparator); } - @Override - public void insert(E e) { - tree.insert(e); - } - - @Override - public E next(E e) { - return tree.next(e); - } - - @Override public E poll() { - return tree.poll(); + Node n = firstNode(root); + if (n == null) + return null; + removeNode(n); + return n.value; } - - @Override - public E prev(E e) { - return tree.previous(e); - } - - @Override - public E remove(E e) { - return tree.remove(e) ? e : null; - } - - @Override - public boolean isEmpty() { - return tree.isEmpty(); - } - - @Override + public void swap(E e1, E e2) { - tree.swap(e1, e2); + Node n1 = findNode(e1); + Node n2 = findNode(e2); + if (n1 != null && n2 != null) { + n1.value = e2; + n2.value = e1; + } } - public String toString() { - return tree.toString(); - } } - Modified: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2009-12-05 17:47:30 UTC (rev 16) @@ -43,14 +43,14 @@ } @Override - public void insert(E e) { + public boolean insert(E e) { int i = 0; while (i < list.size()) { if (compare(list.get(i), e) > 0) { break; } else if (compare(list.get(i), e) == 0) { if (list.get(i).equals(e)) { - return; // don't add duplicate + return false; // don't add duplicate } else { break; } @@ -58,6 +58,7 @@ i++; } list.add(i, e); + return true; } @Override @@ -79,7 +80,7 @@ } @Override - public E prev(E e) { + public E previous(E e) { E p = null; for (Iterator<E> i = list.iterator(); i.hasNext();) { E c = (E) i.next(); @@ -92,8 +93,8 @@ } @Override - public E remove(E e) { - return list.remove(e) ? e : null; + public boolean remove(E e) { + return list.remove(e); } @Override Modified: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java 2009-12-05 17:47:30 UTC (rev 16) @@ -33,7 +33,7 @@ q.swap("San Francisco", "Paris"); assertEquals("San Francisco", q.next("Tel Aviv")); - assertEquals("Sydney", q.prev("New York")); + assertEquals("Sydney", q.previous("New York")); assertEquals("London", q.next("Brussels")); assertEquals("Brussels", q.poll()); Modified: trunk/src/net/sourceforge/geom4j/util/SmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2009-12-05 17:47:30 UTC (rev 16) @@ -17,10 +17,10 @@ /** * SmartQueue is a priority queue which with the following properties: - * - elements are kept sorted according to their natural order, - * so they should implement Comparable interface; + * - only unique elements are stored; + * - elements are kept sorted according to some order; * - elements can be inserted and removed efficiently; - * - top element (smallest) can be extracted from the queue; + * - first element (smallest) can be extracted from the queue; * - for any element immediately previous and immediately next * elements can be obtained; * - any pair of elements can be swapped. @@ -30,15 +30,15 @@ */ public interface SmartQueue<E> { /** Insert an element */ - void insert(E e); + boolean insert(E e); /** Remove an element */ - E remove(E e); + boolean remove(E e); /** Extract (get and remove) the first element */ E poll(); /** Get next element */ E next(E e); /** Get previous element */ - E prev(E e); + E previous(E e); /** Check if empty */ boolean isEmpty(); /** Swap 2 elements */ Modified: trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java 2009-12-05 02:38:09 UTC (rev 15) +++ trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java 2009-12-05 17:47:30 UTC (rev 16) @@ -56,10 +56,10 @@ @Test public void testRemove() { SmartQueue<String> q = createQueue(); - assertEquals("Toronto", q.remove("Toronto")); - assertEquals("Zurich", q.remove("Zurich")); - assertEquals("London", q.remove("London")); - assertEquals("San Francisco", q.remove("San Francisco")); + assertTrue(q.remove("Toronto")); + assertTrue(q.remove("Zurich")); + assertTrue(q.remove("London")); + assertTrue(q.remove("San Francisco")); assertEquals("Brussels", q.poll()); assertEquals("New York", q.poll()); assertEquals("Paris", q.poll()); @@ -72,10 +72,10 @@ public void testNexAndPrev() { SmartQueue<String> q = createQueue(); assertEquals("Toronto", q.next("Tel Aviv")); - assertEquals("Sydney", q.prev("Tel Aviv")); - assertEquals("Brussels", q.prev("London")); + assertEquals("Sydney", q.previous("Tel Aviv")); + assertEquals("Brussels", q.previous("London")); assertEquals("Zurich", q.next("Toronto")); - assertNull(q.prev("Brussels")); + assertNull(q.previous("Brussels")); assertNull(q.next("Zurich")); } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-05 02:38:19
|
Revision: 15 http://geom4j.svn.sourceforge.net/geom4j/?rev=15&view=rev Author: skhenkin Date: 2009-12-05 02:38:09 +0000 (Sat, 05 Dec 2009) Log Message: ----------- Bentley-Ottmann line segments intersection algorithm implemented using priority queues based on binary trees. Tests added and refactored. Performance tested. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/Config.java trunk/src/net/sourceforge/geom4j/Point.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/util/BinarySearchTree.java trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java trunk/src/net/sourceforge/geom4j/util/SearchTree.java trunk/src/net/sourceforge/geom4j/util/SmartQueue.java Added Paths: ----------- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueueTest.java trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java Removed Paths: ------------- trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java Modified: trunk/src/net/sourceforge/geom4j/Config.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Config.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/Config.java 2009-12-05 02:38:09 UTC (rev 15) @@ -56,4 +56,16 @@ return lessThanOrEqual(a, b) && lessThanOrEqual(a, x) && lessThanOrEqual(x, b) || lessThanOrEqual(b, a) && lessThanOrEqual(x, a) && lessThanOrEqual(b, x); } + + public static boolean isPositive(double x) { + return x > precision; + } + + public static boolean isNegative(double x) { + return x < -precision; + } + + public static double roundValue(double x) { + return Math.round(x / precision) * precision; + } } Modified: trunk/src/net/sourceforge/geom4j/Point.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Point.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/Point.java 2009-12-05 02:38:09 UTC (rev 15) @@ -33,6 +33,8 @@ public double getX() { return x; } + + public double getY() { return y; @@ -49,12 +51,20 @@ @Override public int hashCode() { - long bits = java.lang.Double.doubleToLongBits(getX()); - bits ^= java.lang.Double.doubleToLongBits(getY()) * 31; + long bits = java.lang.Double.doubleToLongBits(getRoundedX()); + bits ^= java.lang.Double.doubleToLongBits(getRoundedY()) * 31; return (((int) bits) ^ ((int) (bits >> 32))); } + private double getRoundedY() { + return Config.roundValue(x); + } + + private double getRoundedX() { + return Config.roundValue(y); + } + @Override public String toString() { return "(" + x + ", " + y + ")"; Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2009-12-05 02:38:09 UTC (rev 15) @@ -15,10 +15,11 @@ package net.sourceforge.geom4j; -import java.util.Collections; +import java.util.Comparator; import java.util.LinkedList; import java.util.List; +import net.sourceforge.geom4j.util.BinaryTreeBasedSmartQueue; import net.sourceforge.geom4j.util.ListBasedSmartQueue; import net.sourceforge.geom4j.util.SmartQueue; @@ -69,16 +70,25 @@ * http://www.softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm * http://www.cs.wustl.edu/~pless/506/l4.html */ - static SegmentIntersectionAlgorithm BENTLEY_OTTMANN = new SegmentIntersectionAlgorithm() { + static SegmentIntersectionAlgorithm BENTLEY_OTTMANN = new BentleyOttmannSegmentIntersectionAlgorithm(); + + class BentleyOttmannSegmentIntersectionAlgorithm implements SegmentIntersectionAlgorithm { + SweepLineComparator sweepLineComparator = new SweepLineComparator(); + EventComparator eventComparator = new EventComparator(); + @Override public PointSet run(SegmentSet segments) { // initialization SmartQueue<Event> eventQueue = initializeEventQueue(segments); - SmartQueue<SweepLineSegment> sweepLine = new ListBasedSmartQueue<SweepLineSegment>(); + //SmartQueue<SweepLineSegment> sweepLine + // = new ListBasedSmartQueue<SweepLineSegment>(sweepLineComparator); + SmartQueue<SweepLineSegment> sweepLine = + new BinaryTreeBasedSmartQueue<SweepLineSegment>(sweepLineComparator); PointSet intersections = new PointSet(); // process all events in the queue while (!eventQueue.isEmpty()) { Event e = eventQueue.poll(); + sweepLineComparator.setCurrentPoint(e.getPoint()); e.execute(eventQueue, sweepLine, intersections); } // return found intersections @@ -91,255 +101,266 @@ events.add(new LeftEndpointEvent(new SweepLineSegment(s))); events.add(new RightEndpointEvent(new SweepLineSegment(s))); } - Collections.sort(events); - SmartQueue<Event> eventQueue = new ListBasedSmartQueue<Event>(); + //SmartQueue<Event> eventQueue = new ListBasedSmartQueue<Event>(eventComparator); + SmartQueue<Event> eventQueue = new BinaryTreeBasedSmartQueue<Event>(eventComparator); for (Event e : events) { eventQueue.insert(e); } return eventQueue; } - }; + public void setCompareBeforeSweepLine(boolean compareBefore) { + sweepLineComparator.setBefore(compareBefore); + } - /* - * Helper classes for Bentley-Ottmann algorithm - */ + /* + * Helper classes for Bentley-Ottmann algorithm + */ - /** - * Sweep line event. Events are stored in the event queue which is a - * priority queue which doesn't store duplicate elements. - * - * @author Sergey Khenkin - */ - abstract class Event implements Comparable<Event> { - /** Segment left endpoint event type */ - public static final int LEFT_ENDPOINT = 0; - /** Segment intersection event type */ - public static final int INTERSECTION = 1; - /** Segment right endpoint event type */ - public static final int RIGHT_ENDPOINT = 2; - - /** Execute event-specific actions */ - public abstract void execute(SmartQueue<Event> eventQueue, - SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet); - /** - * Events are sorted by x coordinate asc, then by y coordinate asc, then - * by type asc. Sorting by type is important as left endpoints should be - * processed before intersections before right endpoints in case of the - * points with equal coordinates. + * Sweep line event. Events are stored in the event queue which is a + * priority queue which doesn't store duplicate elements. + * + * @author Sergey Khenkin */ - @Override - public int compareTo(Event e) { - Point p1 = getPoint(); - Point p2 = e.getPoint(); - if (p1.getX() < p2.getX()) { - return -1; - } else if (p1.getX() > p2.getX()) { - return 1; - } else { - if (p1.getY() < p2.getY()) { - return -1; - } else if (p1.getY() > p2.getY()) { - return 1; - } else { - if (getType() < e.getType()) { - return -1; - } else if (getType() > e.getType()) { - return 1; - } else { - return 0; - } - } - } - } + abstract class Event { + /** Segment left endpoint event type */ + public static final int LEFT_ENDPOINT = 0; + /** Segment intersection event type */ + public static final int INTERSECTION = 1; + /** Segment right endpoint event type */ + public static final int RIGHT_ENDPOINT = 2; - public abstract int getType(); + /** Execute event-specific actions */ + public abstract void execute(SmartQueue<Event> eventQueue, + SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet); - /** Get the point associated with the event */ - public abstract Point getPoint(); + public abstract int getType(); - /** - * Add intersection event if segments intersect and intersection point - * is to the right of the point being currently processed. It is - * important not to add intersections at the points to the left of - * currently processed one because we can end up in an infinite loop - * (moreover we never get back in the algorithm). - */ - protected static void addIntersectionEvent( - SmartQueue<Event> eventQueue, SweepLineSegment seg1, - SweepLineSegment seg2, Point curPoint) { - if (seg1 != null && seg2 != null) { - for (Point p : seg1.getSegment().intersects(seg2.getSegment()) - .getPoints()) { - if (p.getX() >= curPoint.getX()) { - eventQueue.insert(new IntersectionEvent(p, seg1, seg2)); + /** Get the point associated with the event */ + public abstract Point getPoint(); + + /** + * Add intersection event if segments intersect and intersection point + * is to the right of the point being currently processed. It is + * important not to add intersections at the points to the left of + * currently processed one because we can end up in an infinite loop + * (moreover we never get back in the algorithm). + */ + protected void addIntersectionEvent( + SmartQueue<Event> eventQueue, SweepLineSegment seg1, + SweepLineSegment seg2, Point curPoint) { + if (seg1 != null && seg2 != null) { + for (Point p : seg1.getSegment().intersects(seg2.getSegment()) + .getPoints()) { + if (p.getX() >= curPoint.getX()) { + eventQueue.insert(new IntersectionEvent(p, seg1, seg2)); + } } } } } - } - /** - * Left endpoint event. Left end of a segment is reached. - */ - class LeftEndpointEvent extends Event { - SweepLineSegment sweepLineSegment; - - public LeftEndpointEvent(SweepLineSegment sweepLineSegment) { - this.sweepLineSegment = sweepLineSegment; - } - /** - * On reaching left endpoint of a segment we insert this segment into - * the sweep line and add intersections of it with its nearest neighbors - * from top and bottom if they exist. + * Left endpoint event. Left end of a segment is reached. */ - @Override - public void execute(SmartQueue<Event> eventQueue, - SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet) { - sweepLine.insert(sweepLineSegment); - SweepLineSegment segBefore = sweepLine.prev(sweepLineSegment); - SweepLineSegment segAfter = sweepLine.next(sweepLineSegment); - addIntersectionEvent(eventQueue, segAfter, sweepLineSegment, - sweepLineSegment.getLeftPoint()); - addIntersectionEvent(eventQueue, sweepLineSegment, segBefore, - sweepLineSegment.getLeftPoint()); - } + class LeftEndpointEvent extends Event { + SweepLineSegment sweepLineSegment; - @Override - public Point getPoint() { - return sweepLineSegment.getLeftPoint(); - } + public LeftEndpointEvent(SweepLineSegment sweepLineSegment) { + this.sweepLineSegment = sweepLineSegment; + } - @Override - public int getType() { - return LEFT_ENDPOINT; - } + /** + * On reaching left endpoint of a segment we insert this segment into + * the sweep line and add intersections of it with its nearest neighbors + * from top and bottom if they exist. + */ + @Override + public void execute(SmartQueue<Event> eventQueue, + SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet) { + sweepLineComparator.setBefore(true); + sweepLine.insert(sweepLineSegment); + SweepLineSegment segBefore = sweepLine.prev(sweepLineSegment); + SweepLineSegment segAfter = sweepLine.next(sweepLineSegment); + sweepLineComparator.setBefore(false); + addIntersectionEvent(eventQueue, segAfter, sweepLineSegment, + sweepLineSegment.getLeftPoint()); + addIntersectionEvent(eventQueue, sweepLineSegment, segBefore, + sweepLineSegment.getLeftPoint()); + } - public String toString() { - return "<" + getType() + ", " + getPoint() + ", " - + sweepLineSegment + ">"; - } + @Override + public Point getPoint() { + return sweepLineSegment.getLeftPoint(); + } - @Override - public boolean equals(Object obj) { - if (obj instanceof LeftEndpointEvent) { - LeftEndpointEvent lee = (LeftEndpointEvent) obj; - return sweepLineSegment.equals(lee.sweepLineSegment); + @Override + public int getType() { + return LEFT_ENDPOINT; } - return false; - } - } - /** - * Right endpoint event. Right end of a segment is reached. - */ - class RightEndpointEvent extends Event { - SweepLineSegment sweepLineSegment; + public String toString() { + return "<" + getType() + ", " + getPoint() + ", " + + sweepLineSegment + ">"; + } - public RightEndpointEvent(SweepLineSegment sweepLineSegment) { - this.sweepLineSegment = sweepLineSegment; + @Override + public boolean equals(Object obj) { + if (obj instanceof LeftEndpointEvent) { + LeftEndpointEvent lee = (LeftEndpointEvent) obj; + return sweepLineSegment.equals(lee.sweepLineSegment); + } + return false; + } } /** - * On reaching right endpoint of a segment we check for intersection of - * segment's neighbors from top and bottom on the sweep line and add a - * new intersection event when appropriate. After that just remove the - * segment from the sweep line. + * Right endpoint event. Right end of a segment is reached. */ - @Override - public void execute(SmartQueue<Event> eventQueue, - SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet) { - SweepLineSegment segBefore = sweepLine.prev(sweepLineSegment); - SweepLineSegment segAfter = sweepLine.next(sweepLineSegment); - addIntersectionEvent(eventQueue, segAfter, segBefore, - sweepLineSegment.getRightPoint()); - sweepLine.remove(sweepLineSegment); - } + class RightEndpointEvent extends Event { + SweepLineSegment sweepLineSegment; - @Override - public Point getPoint() { - return sweepLineSegment.getRightPoint(); - } + public RightEndpointEvent(SweepLineSegment sweepLineSegment) { + this.sweepLineSegment = sweepLineSegment; + } - @Override - public int getType() { - return RIGHT_ENDPOINT; - } + /** + * On reaching right endpoint of a segment we check for intersection of + * segment's neighbors from top and bottom on the sweep line and add a + * new intersection event when appropriate. After that just remove the + * segment from the sweep line. + */ + @Override + public void execute(SmartQueue<Event> eventQueue, + SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet) { + SweepLineSegment segBefore = sweepLine.prev(sweepLineSegment); + SweepLineSegment segAfter = sweepLine.next(sweepLineSegment); + addIntersectionEvent(eventQueue, segAfter, segBefore, + sweepLineSegment.getRightPoint()); + sweepLine.remove(sweepLineSegment); + } - public String toString() { - return "<" + getType() + ", " + getPoint() + ", " - + sweepLineSegment + ">"; - } + @Override + public Point getPoint() { + return sweepLineSegment.getRightPoint(); + } - @Override - public boolean equals(Object obj) { - if (obj instanceof RightEndpointEvent) { - RightEndpointEvent ree = (RightEndpointEvent) obj; - return sweepLineSegment.equals(ree.sweepLineSegment); + @Override + public int getType() { + return RIGHT_ENDPOINT; } - return false; - } - } + public String toString() { + return "<" + getType() + ", " + getPoint() + ", " + + sweepLineSegment + ">"; + } - /** - * Intersection event. Intersection point of two segments is reached. - */ - class IntersectionEvent extends Event { - private Point p; - private SweepLineSegment sAbove; - private SweepLineSegment sBelow; + @Override + public boolean equals(Object obj) { + if (obj instanceof RightEndpointEvent) { + RightEndpointEvent ree = (RightEndpointEvent) obj; + return sweepLineSegment.equals(ree.sweepLineSegment); + } + return false; + } - public IntersectionEvent(Point p, SweepLineSegment sAbove, - SweepLineSegment sBelow) { - this.p = p; - this.sAbove = sAbove; - this.sBelow = sBelow; } /** - * On reaching intersection point of two segments on the sweep line add - * this point to the list of intersections, then swap the intersecting - * segments on the sweep line and check if they now intersect with their - * new neighbors. If so add new intersection points accordingly. + * Intersection event. Intersection point of two segments is reached. */ - @Override - public void execute(SmartQueue<Event> eventQueue, - SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet) { - intersectionSet.add(p); - sweepLine.swap(sAbove, sBelow); - addIntersectionEvent(eventQueue, sAbove, sweepLine.prev(sAbove), p); - addIntersectionEvent(eventQueue, sweepLine.next(sBelow), sBelow, p); - } + class IntersectionEvent extends Event { + private Point p; + private SweepLineSegment sAbove; + private SweepLineSegment sBelow; - @Override - public Point getPoint() { - return p; - } + public IntersectionEvent(Point p, SweepLineSegment sAbove, + SweepLineSegment sBelow) { + this.p = p; + this.sAbove = sAbove; + this.sBelow = sBelow; + } - @Override - public int getType() { - return INTERSECTION; - } + /** + * On reaching intersection point of two segments on the sweep line add + * this point to the list of intersections, then swap the intersecting + * segments on the sweep line and check if they now intersect with their + * new neighbors. If so add new intersection points accordingly. + */ + @Override + public void execute(SmartQueue<Event> eventQueue, + SmartQueue<SweepLineSegment> sweepLine, PointSet intersectionSet) { + intersectionSet.add(p); + sweepLineComparator.setBefore(true); + sweepLine.swap(sAbove, sBelow); + sweepLineComparator.setBefore(false); + addIntersectionEvent(eventQueue, sAbove, sweepLine.prev(sAbove), p); + addIntersectionEvent(eventQueue, sweepLine.next(sBelow), sBelow, p); + } - public String toString() { - return "<" + getType() + ", " + getPoint() + ", " + sAbove + ", " - + sBelow + ">"; + @Override + public Point getPoint() { + return p; + } + + @Override + public int getType() { + return INTERSECTION; + } + + public String toString() { + return "<" + getType() + ", " + getPoint() + ", " + sAbove + ", " + + sBelow + ">"; + } + + @Override + public boolean equals(Object obj) { + if (obj instanceof IntersectionEvent) { + IntersectionEvent ie = (IntersectionEvent) obj; + return p.equals(ie.p) && sAbove.equals(ie.sAbove) + && sBelow.equals(ie.sBelow); + } + return false; + } } - @Override - public boolean equals(Object obj) { - if (obj instanceof IntersectionEvent) { - IntersectionEvent ie = (IntersectionEvent) obj; - return p.equals(ie.p) && sAbove.equals(ie.sAbove) - && sBelow.equals(ie.sBelow); + public class EventComparator implements Comparator<Event> { + + /** + * Events are sorted by x coordinate asc, then by y coordinate asc, then + * by type asc. Sorting by type is important as left endpoints should be + * processed before intersections before right endpoints in case of the + * points with equal coordinates. + */ + @Override + public int compare(Event e1, Event e2) { + Point p1 = e1.getPoint(); + Point p2 = e2.getPoint(); + if (Config.lessThan(p1.getX(), p2.getX())) { + return -1; + } else if (Config.lessThan(p2.getX(), p1.getX())) { + return 1; + } else { + if (Config.lessThan(p1.getY(), p2.getY())) { + return -1; + } else if (Config.lessThan(p2.getY(), p1.getY())) { + return 1; + } else { + if (e1.getType() < e2.getType()) { + return -1; + } else if (e1.getType() > e2.getType()) { + return 1; + } else { + return e1.equals(e2) ? 0 : -1; + } + } + } } - return false; } - } + }; + /** * A wrapper class for a segment which sets segment ordering on the sweep * line. @@ -448,4 +469,100 @@ } + /** Comparator for segments stored in sweep line */ + class SweepLineComparator implements Comparator<SweepLineSegment> { + private Point currentPoint; + private boolean before = false; + + /** + * Segments are sorted from top to bottom by the y coordinate of their + * intersection with the sweep line. This order is kept during sweep + * line movement by appropriate swaps of the intersecting segments. + */ + @Override + public int compare(SweepLineSegment s1, SweepLineSegment s2) { + Point p1 = s1.getLeftPoint(); + Point p2 = s2.getLeftPoint(); + // p1 is always to the left of p2 or on the same vertical + Point q1 = s1.getRightPoint(); + Point q2 = s2.getRightPoint(); + int pos = compareVerticals(p1, q1, p2, q2); + if (pos != 0) { + return pos; + } else { + int c = compareSegmentsAtIntersectionPoint(p1, q1, p2, q2); + return c; + } + } + + private int compareSegmentsAtIntersectionPoint(Point p1, Point q1, Point p2, Point q2) { + Vector v1 = new Vector(p1, q1); + Vector v2 = new Vector(p2, q2); + double d = v1.crossProduct(v2); + if (before) d = -d; + if (Config.isPositive(d)) { + return -1; + } else if (Config.isNegative(d)) { + return 1; + } else { + return 0; + } + } + + /** + * Determines how we compare segments crossing the sweep line + * at the same point: which is below before the sweep line + * (to the left of it) or after (to the right) + */ + public void setBefore(boolean flag) { + this.before = flag; + } + + /** + * Check if segment [p1,q1] crosses vertical that passes through + * point (x,0) segment below [p2,q2] + * Works for x: p1.x<=cp.x<=q1.x, p2.x<=cp.x<=q2.x + */ + private int compareVerticals(Point p1, Point q1, Point p2, Point q2) { + double y1 = calculateVertical(p1, q1); + double y2 = calculateVertical(p2, q2); + if (Config.lessThan(y1, y2)) return -1; + else if (Config.lessThan(y2, y1)) return 1; + else return 0; + } + + private double calculateVertical(Point p, Point q) { + if (Config.equal(p.getX(), q.getX())) { + return currentPoint.getY(); + } else { + return (currentPoint.getX() - p.getX()) * (q.getY() - p.getY()) + / (q.getX() - p.getX()) + p.getY(); + } + } + + /** + * Check if p is above the segment [leftPoint, rightPoint]. + * + * @return -1 if p is above the segment 1 if p is below the segment 0 if + * p lies on the same line with segment endpoints + */ + public int relativePosition(Point p, Point leftPoint, Point rightPoint) { + Vector v1 = new Vector(leftPoint, rightPoint); + Vector v2 = new Vector(leftPoint, p); + double d = v1.crossProduct(v2); + if (d > 0) { // p2 is above [p1, q1] + return -1; + } else if (d < 0) { // p2 is below [p1, q1] + return 1; + } else { // p2 lies on (p1, q1) + return 0; + } + } + + public void setCurrentPoint(Point currentPoint) { + this.currentPoint = currentPoint; + } + } + } + Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-05 02:38:09 UTC (rev 15) @@ -28,7 +28,7 @@ Polygon p = new Polygon() .addVertex(new Point(1, 1)) .addVertex(new Point(1, 2)) - //.addVertex(new Point(2, 3)) + .addVertex(new Point(2, 3)) .addVertex(new Point(3, 2)) .addVertex(new Point(3, 1)); ss2 = p.getSegmentSet(); @@ -141,5 +141,27 @@ assertEquals(naiveSet, boSet); } - + @Test + public void testBentleyOttmannPerformance() { + // a number of segments in the set + int n = 1000; + /* chaining list of segments of this shape: + * \/\/\/\/\/ + * /\/\/\/\/\ + * + * number of intersection is approximately 1.5*n + */ + SegmentSet ss = new SegmentSet(); + for (int i = 0; i < n/2; i++) { + ss.add(new Segment(new Point(i, 0), new Point(i+1, 1))); + ss.add(new Segment(new Point(i, 1), new Point(i+1, 0))); + } + //System.out.println(System.currentTimeMillis()); + PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE); + //System.out.println(System.currentTimeMillis()); + PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); + //System.out.println(System.currentTimeMillis()); + //System.out.println(naiveSet.size()); + assertEquals(naiveSet, boSet); + } } Modified: trunk/src/net/sourceforge/geom4j/SegmentSet.java =================================================================== --- trunk/src/net/sourceforge/geom4j/SegmentSet.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/SegmentSet.java 2009-12-05 02:38:09 UTC (rev 15) @@ -33,11 +33,13 @@ /** * Get all intersections between the segments of this set - * using naive algorithm - O(n*n). + * using Bentley-Ottmann algorithm - O((n+k) log n), + * where n is the number of segments in the set and k is + * the number of intersections. * @return set of intersection points */ public PointSet getAllIntersectionPoints() { - return getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE); + return getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN); } } Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-05 02:38:09 UTC (rev 15) @@ -54,13 +54,13 @@ } /** Root of the tree */ - private Node root = null; + protected Node root = null; /** * Comparator for tree node values. * If it is null the elements should implement Comparable. */ - private Comparator<? super E> comparator = null; + protected Comparator<? super E> comparator = null; /** Create an empty tree of comparable elements */ public BinarySearchTree() { @@ -147,7 +147,7 @@ return false; } - private void removeNode(Node node) { + protected void removeNode(Node node) { if (node.left == null && node.right == null) { // remove node updateNodeReferences(node, null); } else if (node.left == null){ // replace node with its single right child @@ -364,4 +364,10 @@ } } + + /** Check if tree contains elements */ + @Override + public boolean isEmpty() { + return root == null; + } } Added: trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2009-12-05 02:38:09 UTC (rev 15) @@ -0,0 +1,110 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j.util; + +import java.util.Comparator; + + +/** + * "Smarter" implementation of SmartQueue based on a binary search tree. + * It takes on average O(log n) time to insert/remove/swap + * and O(1) to get prev/next elements. + * There's still a room for performance improvements using some kind + * of self-balancing trees (like AVL-trees or Red-Black trees). + * + * @author Sergey Khenkin + */ +public class BinaryTreeBasedSmartQueue<E> implements SmartQueue<E> { + class CustomBinarySearchTree extends BinarySearchTree<E> { + + public CustomBinarySearchTree() { + super(); + } + + public CustomBinarySearchTree(Comparator<? super E> comparator) { + super(comparator); + } + + public E poll() { + Node n = firstNode(root); + if (n == null) + return null; + removeNode(n); + return n.value; + } + + public void swap(E e1, E e2) { + Node n1 = findNode(e1); + Node n2 = findNode(e2); + if (n1 != null && n2 != null) { + n1.value = e2; + n2.value = e1; + } + } + + } + /** Tree that stores queue elements */ + private CustomBinarySearchTree tree = new CustomBinarySearchTree(); + + public BinaryTreeBasedSmartQueue() { + tree = new CustomBinarySearchTree(); + } + + public BinaryTreeBasedSmartQueue(Comparator<E> comparator) { + tree = new CustomBinarySearchTree(comparator); + } + + @Override + public void insert(E e) { + tree.insert(e); + } + + @Override + public E next(E e) { + return tree.next(e); + } + + @Override + public E poll() { + return tree.poll(); + } + + @Override + public E prev(E e) { + return tree.previous(e); + } + + @Override + public E remove(E e) { + return tree.remove(e) ? e : null; + } + + @Override + public boolean isEmpty() { + return tree.isEmpty(); + } + + @Override + public void swap(E e1, E e2) { + tree.swap(e1, e2); + } + + public String toString() { + return tree.toString(); + } +} + + Added: trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueueTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueueTest.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueueTest.java 2009-12-05 02:38:09 UTC (rev 15) @@ -0,0 +1,35 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j.util; + +import static org.junit.Assert.assertEquals; + +import org.junit.Test; + +public class BinaryTreeBasedSmartQueueTest extends SmartQueueTestBase { + @Override + protected SmartQueue<String> getQueueInstance() { + return new BinaryTreeBasedSmartQueue<String>(); + } + + @Test + public void testSwap() { + // actually swapping has not much sense for the search tree + SmartQueue<String> q = createQueue(); + q.swap("New York", "Brussels"); + assertEquals("New York", q.poll()); + } +} Modified: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2009-12-05 02:38:09 UTC (rev 15) @@ -15,30 +15,40 @@ package net.sourceforge.geom4j.util; +import java.util.Comparator; import java.util.Iterator; import java.util.LinkedList; import java.util.List; /** - * Dummy implementation of SmartQueue based on linked list. + * Dummy implementation of SmartQueue based on a linked list. * It actually takes O(n) time to insert/remove/swap * or get prev/next elements. * So this is just a temporary implementation until a more - * efficient one of time O(n log n) is ready. + * efficient one of time O(log n) is ready. * * @author Sergey Khenkin */ -public class ListBasedSmartQueue<E extends Comparable<E>> implements SmartQueue<E> { +public class ListBasedSmartQueue<E> implements SmartQueue<E> { /** List that stores queue elements */ private List<E> list = new LinkedList<E>(); + protected Comparator<E> comparator = null; + + public ListBasedSmartQueue() { + } + + public ListBasedSmartQueue(Comparator<E> comparator) { + this.comparator = comparator; + } + @Override public void insert(E e) { int i = 0; while (i < list.size()) { - if (list.get(i).compareTo(e) > 0) { + if (compare(list.get(i), e) > 0) { break; - } else if (list.get(i).compareTo(e) == 0) { + } else if (compare(list.get(i), e) == 0) { if (list.get(i).equals(e)) { return; // don't add duplicate } else { @@ -105,6 +115,14 @@ return list.toString(); } + @SuppressWarnings("unchecked") + protected int compare(E e1, E e2) { + if (comparator == null) { + return ((Comparable<? super E>) e1).compareTo(e2); + } else { + return comparator.compare(e1, e2); + } + } } Added: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java 2009-12-05 02:38:09 UTC (rev 15) @@ -0,0 +1,51 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j.util; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +import org.junit.Test; + +public class ListBasedSmartQueueTest extends SmartQueueTestBase { + @Override + protected SmartQueue<String> getQueueInstance() { + return new ListBasedSmartQueue<String>(); + } + + @Test + public void testSwap() { + SmartQueue<String> q = createQueue(); + q.swap("New York", "Tel Aviv"); + q.swap("San Francisco", "Paris"); + + assertEquals("San Francisco", q.next("Tel Aviv")); + assertEquals("Sydney", q.prev("New York")); + assertEquals("London", q.next("Brussels")); + + assertEquals("Brussels", q.poll()); + assertEquals("London", q.poll()); + assertEquals("Tel Aviv", q.poll()); + assertEquals("San Francisco", q.poll()); + assertEquals("Paris", q.poll()); + assertEquals("Sydney", q.poll()); + assertEquals("New York", q.poll()); + assertEquals("Toronto", q.poll()); + assertEquals("Zurich", q.poll()); + assertTrue(q.isEmpty()); + } + +} Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-05 02:38:09 UTC (rev 15) @@ -65,4 +65,7 @@ /** Get the number of elements in the tree */ int size(); + + /** Check if tree contains elements */ + boolean isEmpty(); } Modified: trunk/src/net/sourceforge/geom4j/util/SmartQueue.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2009-12-05 02:38:09 UTC (rev 15) @@ -28,7 +28,7 @@ * * @author Sergey Khenkin */ -public interface SmartQueue<E extends Comparable<E>> { +public interface SmartQueue<E> { /** Insert an element */ void insert(E e); /** Remove an element */ Deleted: trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java 2009-12-02 20:28:03 UTC (rev 14) +++ trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java 2009-12-05 02:38:09 UTC (rev 15) @@ -1,107 +0,0 @@ -/* - * Copyright (c) 2009 Sergey Khenkin. All rights reserved. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package net.sourceforge.geom4j.util; - -import static org.junit.Assert.*; - -import org.junit.Before; -import org.junit.Test; - -public class SmartQueueTest { - - @Before - public void setUp() throws Exception { - } - - private static SmartQueue<String> createQueue() { - SmartQueue<String> q = new ListBasedSmartQueue<String>(); - q.insert("New York"); - q.insert("Toronto"); - q.insert("Tel Aviv"); - q.insert("London"); - q.insert("Zurich"); - q.insert("Paris"); - q.insert("Sydney"); - q.insert("San Francisco"); - q.insert("Brussels"); - return q; - } - - @Test - public void testPollInsertAndIsEmpty() { - SmartQueue<String> q = createQueue(); - assertFalse(q.isEmpty()); - assertEquals("Brussels", q.poll()); - assertEquals("London", q.poll()); - assertEquals("New York", q.poll()); - assertEquals("Paris", q.poll()); - assertEquals("San Francisco", q.poll()); - assertEquals("Sydney", q.poll()); - assertEquals("Tel Aviv", q.poll()); - assertEquals("Toronto", q.poll()); - assertEquals("Zurich", q.poll()); - assertTrue(q.isEmpty()); - } - - @Test - public void testRemove() { - SmartQueue<String> q = createQueue(); - assertEquals("Toronto", q.remove("Toronto")); - assertEquals("Zurich", q.remove("Zurich")); - assertEquals("London", q.remove("London")); - assertEquals("San Francisco", q.remove("San Francisco")); - assertEquals("Brussels", q.poll()); - assertEquals("New York", q.poll()); - assertEquals("Paris", q.poll()); - assertEquals("Sydney", q.poll()); - assertEquals("Tel Aviv", q.poll()); - assertTrue(q.isEmpty()); - } - - @Test - public void testNexAndPrev() { - SmartQueue<String> q = createQueue(); - assertEquals("Toronto", q.next("Tel Aviv")); - assertEquals("Sydney", q.prev("Tel Aviv")); - assertEquals("Brussels", q.prev("London")); - assertEquals("Zurich", q.next("Toronto")); - assertNull(q.prev("Brussels")); - assertNull(q.next("Zurich")); - } - - @Test - public void testSwap() { - SmartQueue<String> q = createQueue(); - q.swap("New York", "Tel Aviv"); - q.swap("San Francisco", "Paris"); - - assertEquals("San Francisco", q.next("Tel Aviv")); - assertEquals("Sydney", q.prev("New York")); - assertEquals("London", q.next("Brussels")); - - assertEquals("Brussels", q.poll()); - assertEquals("London", q.poll()); - assertEquals("Tel Aviv", q.poll()); - assertEquals("San Francisco", q.poll()); - assertEquals("Paris", q.poll()); - assertEquals("Sydney", q.poll()); - assertEquals("New York", q.poll()); - assertEquals("Toronto", q.poll()); - assertEquals("Zurich", q.poll()); - assertTrue(q.isEmpty()); - } - -} Copied: trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java (from rev 12, trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java) =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/SmartQueueTestBase.java 2009-12-05 02:38:09 UTC (rev 15) @@ -0,0 +1,82 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package net.sourceforge.geom4j.util; + +import static org.junit.Assert.*; + +import org.junit.Test; + +public abstract class SmartQueueTestBase { + + protected SmartQueue<String> createQueue() { + SmartQueue<String> q = getQueueInstance(); + q.insert("New York"); + q.insert("Toronto"); + q.insert("Tel Aviv"); + q.insert("London"); + q.insert("Zurich"); + q.insert("Paris"); + q.insert("Sydney"); + q.insert("San Francisco"); + q.insert("Brussels"); + return q; + } + + protected abstract SmartQueue<String> getQueueInstance(); + + @Test + public void testPollInsertAndIsEmpty() { + SmartQueue<String> q = createQueue(); + assertFalse(q.isEmpty()); + assertEquals("Brussels", q.poll()); + assertEquals("London", q.poll()); + assertEquals("New York", q.poll()); + assertEquals("Paris", q.poll()); + assertEquals("San Francisco", q.poll()); + assertEquals("Sydney", q.poll()); + assertEquals("Tel Aviv", q.poll()); + assertEquals("Toronto", q.poll()); + assertEquals("Zurich", q.poll()); + assertTrue(q.isEmpty()); + } + + @Test + public void testRemove() { + SmartQueue<String> q = createQueue(); + assertEquals("Toronto", q.remove("Toronto")); + assertEquals("Zurich", q.remove("Zurich")); + assertEquals("London", q.remove("London")); + assertEquals("San Francisco", q.remove("San Francisco")); + assertEquals("Brussels", q.poll()); + assertEquals("New York", q.poll()); + assertEquals("Paris", q.poll()); + assertEquals("Sydney", q.poll()); + assertEquals("Tel Aviv", q.poll()); + assertTrue(q.isEmpty()); + } + + @Test + public void testNexAndPrev() { + SmartQueue<String> q = createQueue(); + assertEquals("Toronto", q.next("Tel Aviv")); + assertEquals("Sydney", q.prev("Tel Aviv")); + assertEquals("Brussels", q.prev("London")); + assertEquals("Zurich", q.next("Toronto")); + assertNull(q.prev("Brussels")); + assertNull(q.next("Zurich")); + } + +} This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-02 20:28:14
|
Revision: 14 http://geom4j.svn.sourceforge.net/geom4j/?rev=14&view=rev Author: skhenkin Date: 2009-12-02 20:28:03 +0000 (Wed, 02 Dec 2009) Log Message: ----------- Binary search tree updated. Added methods for tree height and size calculation. Tree made iterable. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java trunk/src/net/sourceforge/geom4j/util/SearchTree.java Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-01 23:05:11 UTC (rev 13) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-02 20:28:03 UTC (rev 14) @@ -16,8 +16,10 @@ package net.sourceforge.geom4j.util; import java.util.Comparator; +import java.util.Iterator; import java.util.LinkedList; import java.util.List; +import java.util.NoSuchElementException; /** * Binary search tree. @@ -161,13 +163,13 @@ boolean pseudoRandomChoice = (node.hashCode() % 2 == 0); if (pseudoRandomChoice) { // replace node value with its in-order predecessor's value - Node predecessor = previous(node); + Node predecessor = previousNode(node); node.value = predecessor.value; // remove predecessor (it can have at most one child) removeNode(predecessor); } else { // replace node value with its in-order successor's value - Node successor = next(node); + Node successor = nextNode(node); node.value = successor.value; // remove successor (it can have at most one child) removeNode(successor); @@ -200,11 +202,11 @@ /** Get first element */ public E first() { - Node firstNode = first(root); + Node firstNode = firstNode(root); return firstNode != null ? firstNode.value : null; } - protected Node first(Node node) { + protected Node firstNode(Node node) { if (node != null) while (node.left != null) node = node.left; @@ -213,11 +215,11 @@ /** Get last element */ public E last() { - Node lastNode = last(root); + Node lastNode = lastNode(root); return lastNode != null ? lastNode.value : null; } - public Node last(Node node) { + public Node lastNode(Node node) { if (node != null) while (node.right != null) node = node.right; @@ -227,14 +229,14 @@ /** Get next (in-order successor) element for the given element */ public E next(E e) { Node node = findNode(e); - Node nextNode = next(node); + Node nextNode = nextNode(node); return nextNode != null ? nextNode.value : null; } - protected Node next(Node node) { + protected Node nextNode(Node node) { if (node == null) return null; if (node.right != null) { - return first(node.right); + return firstNode(node.right); } Node parent = node.parent; while (parent != null && parent.right == node) { @@ -247,14 +249,14 @@ /** Get previous (in-order predecessor) element for the given element */ public E previous(E e) { Node node = findNode(e); - Node prevNode = previous(node); + Node prevNode = previousNode(node); return prevNode != null ? prevNode.value : null; } - protected Node previous(Node node) { + protected Node previousNode(Node node) { if (node == null) return null; if (node.left != null) { - return last(node.left); + return lastNode(node.left); } Node parent = node.parent; while (parent != null && parent.left == node) { @@ -267,10 +269,10 @@ /** Get ordered list of all tree elements */ public List<E> toList() { List<E> list = new LinkedList<E>(); - Node n = first(root); + Node n = firstNode(root); while (n != null) { list.add(n.value); - n = next(n); + n = nextNode(n); } return list; } @@ -288,5 +290,78 @@ .append("]").toString(); } - // TODO: add iterator + /** Get tree height (max number of nodes on the path from root to leaf) */ + @Override + public int height() { + return heightNode(root); + } + + protected int heightNode(Node node) { + if (node == null) { + return 0; + } else { + return 1 + Math.max(heightNode(node.left), heightNode(node.right)); + } + } + + /** Get the number of elements in the tree */ + @Override + public int size() { + return sizeNode(root); + } + + protected int sizeNode(Node node) { + if (node == null) { + return 0; + } else { + return 1 + sizeNode(node.left) + sizeNode(node.right); + } + } + + /** Return iterator for the tree elements */ + @Override + public Iterator<E> iterator() { + return new BinarySearchTreeIterator(firstNode(root)); + } + + /** Iterator object for the binary search tree */ + public class BinarySearchTreeIterator implements Iterator<E> { + private Node node; + private Node lastAccessed = null; + + public BinarySearchTreeIterator(Node node) { + this.node = node; + } + + @Override + public boolean hasNext() { + return node != null; + } + + @Override + public E next() { + if (node == null) { + throw new NoSuchElementException(); + } + lastAccessed = node; + node = nextNode(node); + return lastAccessed.value; + } + + @Override + public void remove() { + if (lastAccessed == null) { + throw new IllegalStateException(); + } + E nextValue = (node != null ? node.value : null); + removeNode(lastAccessed); + if (lastAccessed != null && node != null + && compare(nextValue, lastAccessed.value) == 0) { + // check if the removed element is replaced by the current one + node = lastAccessed; + } + lastAccessed = null; + } + + } } Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-01 23:05:11 UTC (rev 13) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-02 20:28:03 UTC (rev 14) @@ -4,6 +4,8 @@ import java.util.Arrays; import java.util.HashSet; +import java.util.Iterator; +import java.util.LinkedList; import java.util.List; import java.util.Random; import java.util.Set; @@ -51,14 +53,53 @@ @Test public void testRandomTree() { - Integer[] values = createRandomUniqueArray(300, 1000); + Integer[] values = createRandomUniqueArray(3000, 10000); SearchTree<Integer> t = createBinaryTree(values); Arrays.sort(values); assertTrue(listsEqual(values, t.toList())); + assertEquals(values.length, t.size()); } - // TODO: test removal + @Test + public void testSizeAndHeight() { + SearchTree<Integer> t = createBinaryTree( + new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}); + assertEquals(9, t.size()); + assertEquals(4, t.height()); + + t = new BinarySearchTree<Integer>(); + assertEquals(0, t.size()); + assertEquals(0, t.height()); + } + @Test + public void testIterator() { + Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}; + SearchTree<Integer> t = createBinaryTree(values); + Arrays.sort(values); + List<Integer> treeValues = new LinkedList<Integer>(); + for (Integer i: t) { + treeValues.add(i); + } + assertTrue(Arrays.equals(values, treeValues.toArray())); + } + + @Test + public void testIteratorRemoval() { + Integer[] values = new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}; + SearchTree<Integer> t = createBinaryTree(values); + Arrays.sort(values); + List<Integer> treeValues = new LinkedList<Integer>(); + Iterator<Integer> i = t.iterator(); + while (i.hasNext()) { + Integer v = i.next(); + treeValues.add(v); + i.remove(); + } + assertTrue(Arrays.equals(values, treeValues.toArray())); + } + + private boolean listsEqual(Integer[] values, List<Integer> list) { if (values.length != list.size()) return false; @@ -96,5 +137,4 @@ tree.insert(i); } } - } Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-01 23:05:11 UTC (rev 13) +++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-02 20:28:03 UTC (rev 14) @@ -21,12 +21,16 @@ * General purpose search tree. * Supports operations of inserting, searching and removing for * the elements of type E. + * Duplicate elements are discarded during insertion. + * Tree stores only unique elements. * * @author Sergey Khenkin */ -public interface SearchTree<E> { +public interface SearchTree<E> extends Iterable<E> { /** - * Insert element e into the tree + * Insert element e into the tree. + * If the tree already contains an equal element + * the new one does not get inserted. * @return true if element was actually inserted and has not * already been present in the tree */ @@ -55,4 +59,10 @@ /** Get ordered list of all tree elements */ List<E> toList(); + + /** Get tree height (max number of nodes on the path from root to leaf) */ + int height(); + + /** Get the number of elements in the tree */ + int size(); } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-12-01 23:05:27
|
Revision: 13 http://geom4j.svn.sourceforge.net/geom4j/?rev=13&view=rev Author: skhenkin Date: 2009-12-01 23:05:11 +0000 (Tue, 01 Dec 2009) Log Message: ----------- Binary search tree implemented. Tests for it added. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/Vector.java trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java trunk/src/net/sourceforge/geom4j/util/SearchTree.java Added Paths: ----------- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java Modified: trunk/src/net/sourceforge/geom4j/Vector.java =================================================================== --- trunk/src/net/sourceforge/geom4j/Vector.java 2009-11-30 23:05:54 UTC (rev 12) +++ trunk/src/net/sourceforge/geom4j/Vector.java 2009-12-01 23:05:11 UTC (rev 13) @@ -15,7 +15,6 @@ package net.sourceforge.geom4j; -import java.util.Iterator; /** * A vector on a plane. Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-11-30 23:05:54 UTC (rev 12) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-01 23:05:11 UTC (rev 13) @@ -16,6 +16,8 @@ package net.sourceforge.geom4j.util; import java.util.Comparator; +import java.util.LinkedList; +import java.util.List; /** * Binary search tree. @@ -76,7 +78,7 @@ protected Node findNode(E e) { Node node = root; while (node != null) { - int c = compare(node.value, e); + int c = compare(e, node.value); if (c == 0) return node; else if (c < 0) @@ -99,9 +101,10 @@ } Node node = root; Node parent; + int c; do { parent = node; - int c = compare(node.value, e); + c = compare(e, node.value); if (c == 0) { return false; } else if (c < 0) { @@ -110,7 +113,7 @@ node = node.right; } } while (node != null); - if (node == parent.left) { + if (c < 0) { parent.left = new Node(e, parent); } else { parent.right = new Node(e, parent); @@ -128,7 +131,7 @@ return false; } do { // node != null - int c = compare(node.value, e); + int c = compare(e, node.value); if (c == 0) { removeNode(node); return true; @@ -143,14 +146,50 @@ } private void removeNode(Node node) { - // TODO: !!! - if (node.left == null && node.right == null) { - //detachNode(parent, node); - } else if (node.left == null){ - node = node.right; + if (node.left == null && node.right == null) { // remove node + updateNodeReferences(node, null); + } else if (node.left == null){ // replace node with its single right child + updateNodeReferences(node, node.right); + } else if (node.right == null){ // replace node with its single left child + updateNodeReferences(node, node.left); + } else { + /* We can either replace the node with the biggest element of its + * left subtree or with the smallest element of its right subtree. + * We randomize the selection of this element to prevent tree + * degeneration into list + */ + boolean pseudoRandomChoice = (node.hashCode() % 2 == 0); + if (pseudoRandomChoice) { + // replace node value with its in-order predecessor's value + Node predecessor = previous(node); + node.value = predecessor.value; + // remove predecessor (it can have at most one child) + removeNode(predecessor); + } else { + // replace node value with its in-order successor's value + Node successor = next(node); + node.value = successor.value; + // remove successor (it can have at most one child) + removeNode(successor); + } } } + private void updateNodeReferences(Node node, Node replacement) { + if (node.parent == null) { // node == root + root = replacement; + } else { + if (node.parent.left == node) { + node.parent.left = replacement; + } else { + node.parent.right = replacement; + } + } + if (replacement != null) { + replacement.parent = node.parent; + } + } + @SuppressWarnings("unchecked") private int compare(E e1, E e2) { if (comparator == null) @@ -225,6 +264,29 @@ return parent; } - // TODO: create unit test; one of the ideas: build random tree, - // traverse its elements with next() and compare with the sorted set + /** Get ordered list of all tree elements */ + public List<E> toList() { + List<E> list = new LinkedList<E>(); + Node n = first(root); + while (n != null) { + list.add(n.value); + n = next(n); + } + return list; + } + + @Override + public String toString() { + return toString(root); + } + + public String toString(Node node) { + if (node == null) + return "*"; + return new StringBuilder("[").append(node.value).append(" ") + .append(toString(node.left)).append(" ").append(toString(node.right)) + .append("]").toString(); + } + + // TODO: add iterator } Added: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java (rev 0) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTest.java 2009-12-01 23:05:11 UTC (rev 13) @@ -0,0 +1,100 @@ +package net.sourceforge.geom4j.util; + +import static org.junit.Assert.*; + +import java.util.Arrays; +import java.util.HashSet; +import java.util.List; +import java.util.Random; +import java.util.Set; + +import org.junit.Before; +import org.junit.Test; + +public class BinarySearchTreeTest { + + @Before + public void setUp() throws Exception { + } + + @Test + public void testSmallTree() { + SearchTree<Integer> t = createBinaryTree( + new Integer[] {7, 11, 5, 17, 6, 3, 9, 10, 4}); + assertEquals(3, t.first()); + assertEquals(17, t.last()); + assertEquals(7, t.next(6)); + assertEquals(10, t.previous(11)); + assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 7, 9, 10, 11, 17}, + t.toList())); + assertTrue(t.contains(7)); + t.remove(7); + assertFalse(t.contains(7)); + assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 9, 10, 11, 17}, + t.toList())); + assertTrue(t.contains(9)); + t.remove(9); + assertFalse(t.contains(9)); + assertTrue(listsEqual(new Integer[] {3, 4, 5, 6, 10, 11, 17}, + t.toList())); + assertTrue(t.contains(5)); + t.remove(5); + assertFalse(t.contains(5)); + assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11, 17}, + t.toList())); + assertTrue(t.contains(17)); + t.remove(17); + assertFalse(t.contains(17)); + assertTrue(listsEqual(new Integer[] {3, 4, 6, 10, 11}, + t.toList())); + } + + @Test + public void testRandomTree() { + Integer[] values = createRandomUniqueArray(300, 1000); + SearchTree<Integer> t = createBinaryTree(values); + Arrays.sort(values); + assertTrue(listsEqual(values, t.toList())); + } + + // TODO: test removal + + private boolean listsEqual(Integer[] values, List<Integer> list) { + if (values.length != list.size()) + return false; + int i = 0; + for (Integer v: list) { + if (!v.equals(values[i++])) + return false; + } + return true; + } + + private Integer[] createRandomUniqueArray(int size, int maxValue) { + Random r = new Random(); + Set<Integer> used = new HashSet<Integer>(); + Integer[] values = new Integer[size]; + for (int i = 0; i < size; i++) { + Integer v; + do { + v = r.nextInt(maxValue); + } while (used.contains(v)); + values[i] = v; + used.add(v); + } + return values; + } + + private SearchTree<Integer> createBinaryTree(Integer[] values) { + SearchTree<Integer> tree = new BinarySearchTree<Integer>(); + populateTree(tree, values); + return tree; + } + + private void populateTree(SearchTree<Integer> tree, Integer[] values) { + for (int i: values) { + tree.insert(i); + } + } + +} Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-11-30 23:05:54 UTC (rev 12) +++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-01 23:05:11 UTC (rev 13) @@ -15,6 +15,8 @@ package net.sourceforge.geom4j.util; +import java.util.List; + /** * General purpose search tree. * Supports operations of inserting, searching and removing for @@ -50,4 +52,7 @@ /** Get previous (in-order predecessor) element for the given element */ E previous(E e); + + /** Get ordered list of all tree elements */ + List<E> toList(); } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-11-30 23:06:01
|
Revision: 12 http://geom4j.svn.sourceforge.net/geom4j/?rev=12&view=rev Author: skhenkin Date: 2009-11-30 23:05:54 +0000 (Mon, 30 Nov 2009) Log Message: ----------- next() and previous() implementations added to BinarySearchTree Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java trunk/src/net/sourceforge/geom4j/util/SearchTree.java trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-11-30 21:26:47 UTC (rev 11) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-11-30 23:05:54 UTC (rev 12) @@ -1,3 +1,18 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + package net.sourceforge.geom4j.util; import java.util.Comparator; @@ -54,19 +69,24 @@ /** Check if the tree contains element e */ public boolean contains(E e) { + return findNode(e) != null; + } + + /** Find element node in the tree */ + protected Node findNode(E e) { Node node = root; while (node != null) { int c = compare(node.value, e); if (c == 0) - return true; + return node; else if (c < 0) node = node.left; else // c > 0 node = node.right; } - return false; + return node; } - + /** * Insert element e into the tree * @return true if element was actually inserted and has not @@ -141,32 +161,70 @@ /** Get first element */ public E first() { - Node node = root; - if (root != null) + Node firstNode = first(root); + return firstNode != null ? firstNode.value : null; + } + + protected Node first(Node node) { + if (node != null) while (node.left != null) node = node.left; - return node == null ? null : node.value; + return node; } /** Get last element */ public E last() { - Node node = root; - if (root != null) + Node lastNode = last(root); + return lastNode != null ? lastNode.value : null; + } + + public Node last(Node node) { + if (node != null) while (node.right != null) node = node.right; - return node == null ? null : node.value; + return node; } /** Get next (in-order successor) element for the given element */ public E next(E e) { - // TODO Auto-generated method stub - return null; + Node node = findNode(e); + Node nextNode = next(node); + return nextNode != null ? nextNode.value : null; } + + protected Node next(Node node) { + if (node == null) return null; + if (node.right != null) { + return first(node.right); + } + Node parent = node.parent; + while (parent != null && parent.right == node) { + node = parent; + parent = parent.parent; + } + return parent; + } /** Get previous (in-order predecessor) element for the given element */ public E previous(E e) { - // TODO Auto-generated method stub - return null; + Node node = findNode(e); + Node prevNode = previous(node); + return prevNode != null ? prevNode.value : null; } + protected Node previous(Node node) { + if (node == null) return null; + if (node.left != null) { + return last(node.left); + } + Node parent = node.parent; + while (parent != null && parent.left == node) { + node = parent; + parent = parent.parent; + } + return parent; + } + + // TODO: create unit test; one of the ideas: build random tree, + // traverse its elements with next() and compare with the sorted set } Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-11-30 21:26:47 UTC (rev 11) +++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-11-30 23:05:54 UTC (rev 12) @@ -1,3 +1,18 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + package net.sourceforge.geom4j.util; /** Modified: trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java 2009-11-30 21:26:47 UTC (rev 11) +++ trunk/src/net/sourceforge/geom4j/util/SmartQueueTest.java 2009-11-30 23:05:54 UTC (rev 12) @@ -1,3 +1,18 @@ +/* + * Copyright (c) 2009 Sergey Khenkin. All rights reserved. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + package net.sourceforge.geom4j.util; import static org.junit.Assert.*; This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <skh...@us...> - 2009-11-30 21:27:00
|
Revision: 11 http://geom4j.svn.sourceforge.net/geom4j/?rev=11&view=rev Author: skhenkin Date: 2009-11-30 21:26:47 +0000 (Mon, 30 Nov 2009) Log Message: ----------- SearchTree interface extended. contains(), insert(), first() and last() methods implemented for binary search tree. Modified Paths: -------------- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java trunk/src/net/sourceforge/geom4j/util/SearchTree.java Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-11-29 23:06:05 UTC (rev 10) +++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-11-30 21:26:47 UTC (rev 11) @@ -18,16 +18,19 @@ public class BinarySearchTree<E> implements SearchTree<E> { /** Tree node element */ - protected class Node<E> { + protected class Node { /** Tree node value */ E value; /** Reference to the root node of the left subtree */ Node left = null; /** Reference to the root node of the right subtree */ Node right = null; + /** Reference to the parent node */ + Node parent = null; - public Node(E value) { + public Node(E value, Node parent) { this.value = value; + this.parent = parent; } } @@ -49,23 +52,121 @@ this.comparator = comparator; } - @Override + /** Check if the tree contains element e */ public boolean contains(E e) { - // TODO Auto-generated method stub + Node node = root; + while (node != null) { + int c = compare(node.value, e); + if (c == 0) + return true; + else if (c < 0) + node = node.left; + else // c > 0 + node = node.right; + } return false; } - @Override - public void insert(E e) { - // TODO Auto-generated method stub - + /** + * Insert element e into the tree + * @return true if element was actually inserted and has not + * already been present in the tree + */ + public boolean insert(E e) { + if (root == null) { + root = new Node(e, null); + return true; + } + Node node = root; + Node parent; + do { + parent = node; + int c = compare(node.value, e); + if (c == 0) { + return false; + } else if (c < 0) { + node = node.left; + } else { // c > 0 + node = node.right; + } + } while (node != null); + if (node == parent.left) { + parent.left = new Node(e, parent); + } else { + parent.right = new Node(e, parent); + } + return true; } - @Override + /** + * Remove element e from the tree. + * @return true if element was actually present in the tree before removal + */ public boolean remove(E e) { - // TODO Auto-generated method stub + Node node = root; + if (node == null) { + return false; + } + do { // node != null + int c = compare(node.value, e); + if (c == 0) { + removeNode(node); + return true; + } + if (c < 0) { + node = node.left; + } else { // c > 0 + node = node.right; + } + } while (node != null); return false; } + + private void removeNode(Node node) { + // TODO: !!! + if (node.left == null && node.right == null) { + //detachNode(parent, node); + } else if (node.left == null){ + node = node.right; + } + } + + @SuppressWarnings("unchecked") + private int compare(E e1, E e2) { + if (comparator == null) + return ((Comparable<? super E>) e1).compareTo(e2); + else + return comparator.compare(e1, e2); + } + + /** Get first element */ + public E first() { + Node node = root; + if (root != null) + while (node.left != null) + node = node.left; + return node == null ? null : node.value; + } + + /** Get last element */ + public E last() { + Node node = root; + if (root != null) + while (node.right != null) + node = node.right; + return node == null ? null : node.value; + } + + /** Get next (in-order successor) element for the given element */ + public E next(E e) { + // TODO Auto-generated method stub + return null; + } + + /** Get previous (in-order predecessor) element for the given element */ + public E previous(E e) { + // TODO Auto-generated method stub + return null; + } - } Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java =================================================================== --- trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-11-29 23:06:05 UTC (rev 10) +++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-11-30 21:26:47 UTC (rev 11) @@ -8,8 +8,12 @@ * @author Sergey Khenkin */ public interface SearchTree<E> { - /** Insert element e into the tree */ - void insert(E e); + /** + * Insert element e into the tree + * @return true if element was actually inserted and has not + * already been present in the tree + */ + boolean insert(E e); /** Check if the tree contains element e */ boolean contains(E e); @@ -19,4 +23,16 @@ * @return true if element was actually present in the tree before removal */ boolean remove(E e); + + /** Get first element */ + E first(); + + /** Get last element */ + E last(); + + /** Get next (in-order successor) element for the given element */ + E next(E e); + + /** Get previous (in-order predecessor) element for the given element */ + E previous(E e); } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: Sergey K. <skh...@gm...> - 2009-11-30 19:38:58
|
Hi everybody, This is the greetings email to the newly created geom4j developers group. Best luck, Sergey |