[Geom4j-developer] SF.net SVN: geom4j:[27] trunk/src/net/sourceforge/geom4j/ SegmentIntersectionAlgorithmTest.java

[<skh...@us...>]

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.