Changeset 5282

Timestamp:

May 6, 2008, 4:28:34 PM (17 years ago)

Author:

ole

Message:

Added differentiation between intersection, parallel, coinciding and
non-intersecting lines.
Lots of tests

Location:

anuga_core/source/anuga/utilities

Files:

• polygon.py (modified) (3 diffs)
• test_polygon.py (modified) (7 diffs)

anuga_core/source/anuga/utilities/polygon.py

@@ -44 +44 @@
 
 def intersection(line0, line1):
-    """Returns intersecting point between two line segments or None (if parallel or no intersection is found)
+    """Returns intersecting point between two line segments or None
+    (if parallel or no intersection is found).
+
+    However, if parallel lines coincide partly (i.e. shara a common segment,
+    the line segment where lines coincide is returned
+    
 
     Inputs:
         line0, line1: Each defined by two end points as in: [[x0, y0], [x1, y1]]
-                      A line can also be a 2x2 numeric array with each row corresponding to a point.
+                      A line can also be a 2x2 numeric array with each row
+                      corresponding to a point.
 
 
     Output:
-        Point [x,y] or None.
-
-    If line extensions intersect outside their limits, None is returned as well.
+        status, value
+
+        where status is interpreted as follows
+        
+        status == 0: no intersection with value set to None
+        status == 1: One intersection point found and returned in value as [x,y]
+        status == 2: Coinciding line segment found. Value taks the form [[x0,y0], [x1,y1]]
+        status == 3: Lines would coincide but only if extended. Value set to None
+        status == 4: Lines are parallel with a fixed distance apart. Value set to that distance.
     
     """
@@ -70 +82 @@
 
     denom = (y3-y2)*(x1-x0) - (x3-x2)*(y1-y0)
-
-    #print 'denom', denom, line0, line1
+    u0 = (x3-x2)*(y0-y2) - (y3-y2)*(x0-x2)
+    u1 = (x2-x0)*(y1-y0) - (y2-y0)*(x1-x0)
+        
     if allclose(denom, 0.0):
-        # Lines are parallel
-        return None
+        # Lines are parallel - check if they coincide on a shared a segment
+
+        if allclose( [u0, u1], 0.0 ):
+            # We now know that the lines if continued coincide
+            # The remaining check will establish if the finite lines share a segment
+
+            line0_starts_on_line1 = line0_ends_on_line1 =\
+            line1_starts_on_line0 = line1_ends_on_line0 = False
+                
+            if point_on_line([x0, y0], line1):
+                line0_starts_on_line1 = True
+
+            if point_on_line([x1, y1], line1):
+                line0_ends_on_line1 = True
+ 
+            if point_on_line([x2, y2], line0):
+                line1_starts_on_line0 = True
+
+            if point_on_line([x3, y3], line0):
+                line1_ends_on_line0 = True                               
+
+            #print line0_starts_on_line1
+            #print line1_starts_on_line0            
+            #print line1_ends_on_line0
+            #print line0_ends_on_line1            
+
+            if not(line0_starts_on_line1 or line0_ends_on_line1\
+               or line1_starts_on_line0 or line1_ends_on_line0):
+                # Lines are parallel and would coincide if extended, but not as they are.
+                return 3, None
+
+            # One line fully included in the other. Use direction of included line
+            if line0_starts_on_line1 and line0_ends_on_line1:
+                # Shared segment is line0 fully included in line1
+                segment = array([[x0, y0], [x1, y1]])                
+
+            if line1_starts_on_line0 and line1_ends_on_line0:
+                # Shared segment is line1 fully included in line0
+                segment = array([[x2, y2], [x3, y3]])
+            
+
+            # Overlap with lines are oriented the same way
+            if line0_starts_on_line1 and line1_ends_on_line0:
+                # Shared segment from line0 start to line 1 end
+                segment = array([[x0, y0], [x3, y3]])
+
+            if line1_starts_on_line0 and line0_ends_on_line1:
+                # Shared segment from line1 start to line 0 end
+                segment = array([[x2, y2], [x1, y1]])                                
+
+
+            # Overlap in opposite directions - use direction of line0
+            if line0_starts_on_line1 and line1_starts_on_line0:
+                # Shared segment from line0 start to line 1 end
+                segment = array([[x0, y0], [x2, y2]])
+
+            if line0_ends_on_line1 and line1_ends_on_line0:
+                # Shared segment from line0 start to line 1 end
+                segment = array([[x3, y3], [x1, y1]])                
+
+                
+            return 2, segment
+        else:
+            # Lines are parallel but they don't coincide
+            return 4, None
+            
     else:
-        u0 = (x3-x2)*(y0-y2) - (y3-y2)*(x0-x2)
+        # Lines are not parallel or coinciding
         u0 = u0/denom
-
-        u1 = (x2-x0)*(y1-y0) - (y2-y0)*(x1-x0)
         u1 = u1/denom        
 
@@ -92 +167 @@
             # We have intersection
 
-            # Need tolerances if going ahead with this check
-            #msg = 'Algorithm error. Intersection was detected but point (%f, %f) does not lie ' %(x,y)
-            #msg += 'on line0: %s' %(line0)
-            #assert point_on_line([x, y], line0), msg
-            #msg = 'Algorithm error. Intersection was detected but point (%f, %f) does not lie ' %(x,y)
-            #msg += 'on line1: %s' %(line1)            
-            #assert point_on_line([x, y], line1), msg
-        
-            return [x, y]
+            return 1, [x, y]
         else:
-            return None
+            # No intersection
+            return 0, None
+
 
 

anuga_core/source/anuga/utilities/test_polygon.py

@@ -583 +583 @@
         line1 = [[0,-1], [0,1]]
 
-        p = intersection(line0, line1)
-        assert allclose(p, [0.0, 0.0])
+        status, value = intersection(line0, line1)
+        assert status == 1
+        assert allclose(value, [0.0, 0.0])
 
     def test_intersection2(self):
@@ -590 +591 @@
         line1 = [[0,12], [24,0]]
 
-        p = intersection(line0, line1)
-        assert allclose(p, [12.0, 6.0])
+        status, value = intersection(line0, line1)
+        assert status == 1
+        assert allclose(value, [12.0, 6.0])
 
         # Swap direction of one line
         line1 = [[24,0], [0,12]]
 
-        p = intersection(line0, line1)
-        assert allclose(p, [12.0, 6.0])
+        status, value = intersection(line0, line1)
+        assert status == 1
+        assert allclose(value, [12.0, 6.0])
 
         # Swap order of lines
-        p = intersection(line1, line0)
-        assert allclose(p, [12.0, 6.0])        
+        status, value = intersection(line1, line0)
+        assert status == 1
+        assert allclose(value, [12.0, 6.0])        
         
     def test_intersection3(self):
@@ -607 +611 @@
         line1 = [[0,17], [24,0]]
 
-        p = intersection(line0, line1)
-        #print p
-        assert allclose(p, [14.068965517, 7.0344827586])
+        status, value = intersection(line0, line1)
+        assert status == 1
+        assert allclose(value, [14.068965517, 7.0344827586])
 
         # Swap direction of one line
         line1 = [[24,0], [0,17]]
 
-        p = intersection(line0, line1)
-        #print p
-        assert allclose(p, [14.068965517, 7.0344827586])        
+        status, value = intersection(line0, line1)
+        assert status == 1
+        assert allclose(value, [14.068965517, 7.0344827586])        
 
         # Swap order of lines
-        p = intersection(line1, line0)
-        assert allclose(p, [14.068965517, 7.0344827586])        
-
-
-    def test_intersection4(self):
-        line0 = [[0,0], [24,12]]
-        line1 = [[0,22], [21,0]]
-
-        p = intersection(line0, line1)
-        #print 'P',p
-
-        
+        status, value = intersection(line1, line0)
+        assert status == 1        
+        assert allclose(value, [14.068965517, 7.0344827586])        
+
+
     def test_intersection_direction_invariance(self):
         """This runs through a number of examples and checks that direction of lines don't matter.
         """
-
               
         line0 = [[0,0], [100,100]]
@@ -644 +640 @@
 
             line1 = [[x,0], common_end_point]
-            p1 = intersection(line0, line1)
+            status, p1 = intersection(line0, line1)
+            assert status == 1
+
 
             # Swap direction of line1
             line1 = [common_end_point, [x,0]]            
-            p2 = intersection(line0, line1)
+            status, p2 = intersection(line0, line1)
+            assert status == 1            
 
             msg = 'Orientation of line shouldn not matter.\n'
@@ -659 +658 @@
 
             # Swap order of lines
-            p3 = intersection(line1, line0)
+            status, p3 = intersection(line1, line0)
+            assert status == 1                        
             msg = 'Order of lines gave different results'
             assert allclose(p1, p3), msg
+            
 
     def test_no_intersection(self):
@@ -667 +668 @@
         line1 = [[0,-1], [0,0]]
 
-        p = intersection(line0, line1)
-        assert p is None
+        status, value = intersection(line0, line1)
+        assert status == 0
+        assert value is None
+        
 
     def test_intersection_parallel(self):
@@ -674 +677 @@
         line1 = [[-1,0], [5,0]]
 
-        p = intersection(line0, line1)
-        assert p is None                
-
+        status, value = intersection(line0, line1)
+        assert status == 4        
+        assert value is None
+
+
+        line0 = [[0,0], [10,100]]
+        line1 = [[-10,5], [0,105]]
+
+        status, value = intersection(line0, line1)
+        assert status == 4                
+        assert value is None        
+
+
+    def test_intersection_coincide(self):
+        """def test_intersection_coincide(self):
+        Test what happens whe two lines partly coincide
+        """
+
+        # Overlap 1
+        line0 = [[0,0], [5,0]]
+        line1 = [[-3,0], [3,0]]
+
+        status, value = intersection(line0, line1)
+        assert status == 2
+        assert allclose(value, [[0,0], [3,0]])
+
+        # Overlap 2
+        line0 = [[-10,0], [5,0]]
+        line1 = [[-3,0], [10,0]]
+
+        status, value = intersection(line0, line1)
+        assert status == 2
+        assert allclose(value, [[-3, 0], [5,0]])        
+
+        # Inclusion 1
+        line0 = [[0,0], [5,0]]
+        line1 = [[2,0], [3,0]]
+
+        status, value = intersection(line0, line1)
+        assert status == 2        
+        assert allclose(value, line1)
+
+        # Inclusion 2
+        line0 = [[1,0], [5,0]]
+        line1 = [[-10,0], [15,0]]
+
+        status, value = intersection(line0, line1)
+        assert status == 2        
+        assert allclose(value, line0)                                        
+
+
+        # Exclusion (no intersection)
+        line0 = [[-10,0], [1,0]]
+        line1 = [[3,0], [15,0]]
+
+        status, value = intersection(line0, line1)
+        assert status == 3        
+        assert value is None
+        
+
+        # Try examples with some slope (y=2*x+5)
+
+        # Overlap
+        line0 = [[0,5], [7,19]]
+        line1 = [[1,7], [10,25]]
+        status, value = intersection(line0, line1)
+        assert status == 2                
+        assert allclose(value, [[1, 7], [7, 19]])
+
+        status, value = intersection(line1, line0)
+        assert status == 2
+        assert allclose(value, [[1, 7], [7, 19]])
+
+        # Swap direction
+        line0 = [[7,19], [0,5]]
+        line1 = [[1,7], [10,25]]
+        status, value = intersection(line0, line1)
+        assert status == 2
+        assert allclose(value, [[7, 19], [1, 7]])
+
+        line0 = [[0,5], [7,19]]
+        line1 = [[10,25], [1,7]]
+        status, value = intersection(line0, line1)
+        assert status == 2
+        assert allclose(value, [[1, 7], [7, 19]])        
+        
+
+        # Inclusion
+        line0 = [[1,7], [7,19]]
+        line1 = [[0,5], [10,25]]
+        status, value = intersection(line0, line1)
+        assert status == 2                        
+        assert allclose(value, [[1,7], [7, 19]])                
+
+        line0 = [[0,5], [10,25]]
+        line1 = [[1,7], [7,19]]
+        status, value = intersection(line0, line1)
+        assert status == 2                        
+        assert allclose(value, [[1,7], [7, 19]])
+
+
+        line0 = [[0,5], [10,25]]
+        line1 = [[7,19], [1,7]]
+        status, value = intersection(line0, line1)
+        assert status == 2                        
+        assert allclose(value, [[7, 19], [1, 7]])