[Geom4j-developer] SF.net SVN: geom4j:[27] trunk/src/net/sourceforge/geom4j/ SegmentIntersectionAlg
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[27] trunk/src/net/sourceforge/geom4j/ SegmentIntersectionAlgorithmTest.java
|
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.
|
