Changeset 5282


Ignore:
Timestamp:
May 6, 2008, 4:28:34 PM (16 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:
2 edited

Legend:

Unmodified
Added
Removed
  • anuga_core/source/anuga/utilities/polygon.py

    r5225 r5282  
    4444
    4545def intersection(line0, line1):
    46     """Returns intersecting point between two line segments or None (if parallel or no intersection is found)
     46    """Returns intersecting point between two line segments or None
     47    (if parallel or no intersection is found).
     48
     49    However, if parallel lines coincide partly (i.e. shara a common segment,
     50    the line segment where lines coincide is returned
     51   
    4752
    4853    Inputs:
    4954        line0, line1: Each defined by two end points as in: [[x0, y0], [x1, y1]]
    50                       A line can also be a 2x2 numeric array with each row corresponding to a point.
     55                      A line can also be a 2x2 numeric array with each row
     56                      corresponding to a point.
    5157
    5258
    5359    Output:
    54         Point [x,y] or None.
    55 
    56     If line extensions intersect outside their limits, None is returned as well.
     60        status, value
     61
     62        where status is interpreted as follows
     63       
     64        status == 0: no intersection with value set to None
     65        status == 1: One intersection point found and returned in value as [x,y]
     66        status == 2: Coinciding line segment found. Value taks the form [[x0,y0], [x1,y1]]
     67        status == 3: Lines would coincide but only if extended. Value set to None
     68        status == 4: Lines are parallel with a fixed distance apart. Value set to that distance.
    5769   
    5870    """
     
    7082
    7183    denom = (y3-y2)*(x1-x0) - (x3-x2)*(y1-y0)
    72 
    73     #print 'denom', denom, line0, line1
     84    u0 = (x3-x2)*(y0-y2) - (y3-y2)*(x0-x2)
     85    u1 = (x2-x0)*(y1-y0) - (y2-y0)*(x1-x0)
     86       
    7487    if allclose(denom, 0.0):
    75         # Lines are parallel
    76         return None
     88        # Lines are parallel - check if they coincide on a shared a segment
     89
     90        if allclose( [u0, u1], 0.0 ):
     91            # We now know that the lines if continued coincide
     92            # The remaining check will establish if the finite lines share a segment
     93
     94            line0_starts_on_line1 = line0_ends_on_line1 =\
     95            line1_starts_on_line0 = line1_ends_on_line0 = False
     96               
     97            if point_on_line([x0, y0], line1):
     98                line0_starts_on_line1 = True
     99
     100            if point_on_line([x1, y1], line1):
     101                line0_ends_on_line1 = True
     102 
     103            if point_on_line([x2, y2], line0):
     104                line1_starts_on_line0 = True
     105
     106            if point_on_line([x3, y3], line0):
     107                line1_ends_on_line0 = True                               
     108
     109            #print line0_starts_on_line1
     110            #print line1_starts_on_line0           
     111            #print line1_ends_on_line0
     112            #print line0_ends_on_line1           
     113
     114            if not(line0_starts_on_line1 or line0_ends_on_line1\
     115               or line1_starts_on_line0 or line1_ends_on_line0):
     116                # Lines are parallel and would coincide if extended, but not as they are.
     117                return 3, None
     118
     119            # One line fully included in the other. Use direction of included line
     120            if line0_starts_on_line1 and line0_ends_on_line1:
     121                # Shared segment is line0 fully included in line1
     122                segment = array([[x0, y0], [x1, y1]])               
     123
     124            if line1_starts_on_line0 and line1_ends_on_line0:
     125                # Shared segment is line1 fully included in line0
     126                segment = array([[x2, y2], [x3, y3]])
     127           
     128
     129            # Overlap with lines are oriented the same way
     130            if line0_starts_on_line1 and line1_ends_on_line0:
     131                # Shared segment from line0 start to line 1 end
     132                segment = array([[x0, y0], [x3, y3]])
     133
     134            if line1_starts_on_line0 and line0_ends_on_line1:
     135                # Shared segment from line1 start to line 0 end
     136                segment = array([[x2, y2], [x1, y1]])                               
     137
     138
     139            # Overlap in opposite directions - use direction of line0
     140            if line0_starts_on_line1 and line1_starts_on_line0:
     141                # Shared segment from line0 start to line 1 end
     142                segment = array([[x0, y0], [x2, y2]])
     143
     144            if line0_ends_on_line1 and line1_ends_on_line0:
     145                # Shared segment from line0 start to line 1 end
     146                segment = array([[x3, y3], [x1, y1]])               
     147
     148               
     149            return 2, segment
     150        else:
     151            # Lines are parallel but they don't coincide
     152            return 4, None
     153           
    77154    else:
    78         u0 = (x3-x2)*(y0-y2) - (y3-y2)*(x0-x2)
     155        # Lines are not parallel or coinciding
    79156        u0 = u0/denom
    80 
    81         u1 = (x2-x0)*(y1-y0) - (y2-y0)*(x1-x0)
    82157        u1 = u1/denom       
    83158
     
    92167            # We have intersection
    93168
    94             # Need tolerances if going ahead with this check
    95             #msg = 'Algorithm error. Intersection was detected but point (%f, %f) does not lie ' %(x,y)
    96             #msg += 'on line0: %s' %(line0)
    97             #assert point_on_line([x, y], line0), msg
    98             #msg = 'Algorithm error. Intersection was detected but point (%f, %f) does not lie ' %(x,y)
    99             #msg += 'on line1: %s' %(line1)           
    100             #assert point_on_line([x, y], line1), msg
    101        
    102             return [x, y]
     169            return 1, [x, y]
    103170        else:
    104             return None
     171            # No intersection
     172            return 0, None
     173
    105174
    106175
  • anuga_core/source/anuga/utilities/test_polygon.py

    r5225 r5282  
    583583        line1 = [[0,-1], [0,1]]
    584584
    585         p = intersection(line0, line1)
    586         assert allclose(p, [0.0, 0.0])
     585        status, value = intersection(line0, line1)
     586        assert status == 1
     587        assert allclose(value, [0.0, 0.0])
    587588
    588589    def test_intersection2(self):
     
    590591        line1 = [[0,12], [24,0]]
    591592
    592         p = intersection(line0, line1)
    593         assert allclose(p, [12.0, 6.0])
     593        status, value = intersection(line0, line1)
     594        assert status == 1
     595        assert allclose(value, [12.0, 6.0])
    594596
    595597        # Swap direction of one line
    596598        line1 = [[24,0], [0,12]]
    597599
    598         p = intersection(line0, line1)
    599         assert allclose(p, [12.0, 6.0])
     600        status, value = intersection(line0, line1)
     601        assert status == 1
     602        assert allclose(value, [12.0, 6.0])
    600603
    601604        # Swap order of lines
    602         p = intersection(line1, line0)
    603         assert allclose(p, [12.0, 6.0])       
     605        status, value = intersection(line1, line0)
     606        assert status == 1
     607        assert allclose(value, [12.0, 6.0])       
    604608       
    605609    def test_intersection3(self):
     
    607611        line1 = [[0,17], [24,0]]
    608612
    609         p = intersection(line0, line1)
    610         #print p
    611         assert allclose(p, [14.068965517, 7.0344827586])
     613        status, value = intersection(line0, line1)
     614        assert status == 1
     615        assert allclose(value, [14.068965517, 7.0344827586])
    612616
    613617        # Swap direction of one line
    614618        line1 = [[24,0], [0,17]]
    615619
    616         p = intersection(line0, line1)
    617         #print p
    618         assert allclose(p, [14.068965517, 7.0344827586])       
     620        status, value = intersection(line0, line1)
     621        assert status == 1
     622        assert allclose(value, [14.068965517, 7.0344827586])       
    619623
    620624        # Swap order of lines
    621         p = intersection(line1, line0)
    622         assert allclose(p, [14.068965517, 7.0344827586])       
    623 
    624 
    625     def test_intersection4(self):
    626         line0 = [[0,0], [24,12]]
    627         line1 = [[0,22], [21,0]]
    628 
    629         p = intersection(line0, line1)
    630         #print 'P',p
    631 
    632        
     625        status, value = intersection(line1, line0)
     626        assert status == 1       
     627        assert allclose(value, [14.068965517, 7.0344827586])       
     628
     629
    633630    def test_intersection_direction_invariance(self):
    634631        """This runs through a number of examples and checks that direction of lines don't matter.
    635632        """
    636 
    637633             
    638634        line0 = [[0,0], [100,100]]
     
    644640
    645641            line1 = [[x,0], common_end_point]
    646             p1 = intersection(line0, line1)
     642            status, p1 = intersection(line0, line1)
     643            assert status == 1
     644
    647645
    648646            # Swap direction of line1
    649647            line1 = [common_end_point, [x,0]]           
    650             p2 = intersection(line0, line1)
     648            status, p2 = intersection(line0, line1)
     649            assert status == 1           
    651650
    652651            msg = 'Orientation of line shouldn not matter.\n'
     
    659658
    660659            # Swap order of lines
    661             p3 = intersection(line1, line0)
     660            status, p3 = intersection(line1, line0)
     661            assert status == 1                       
    662662            msg = 'Order of lines gave different results'
    663663            assert allclose(p1, p3), msg
     664           
    664665
    665666    def test_no_intersection(self):
     
    667668        line1 = [[0,-1], [0,0]]
    668669
    669         p = intersection(line0, line1)
    670         assert p is None
     670        status, value = intersection(line0, line1)
     671        assert status == 0
     672        assert value is None
     673       
    671674
    672675    def test_intersection_parallel(self):
     
    674677        line1 = [[-1,0], [5,0]]
    675678
    676         p = intersection(line0, line1)
    677         assert p is None               
    678 
     679        status, value = intersection(line0, line1)
     680        assert status == 4       
     681        assert value is None
     682
     683
     684        line0 = [[0,0], [10,100]]
     685        line1 = [[-10,5], [0,105]]
     686
     687        status, value = intersection(line0, line1)
     688        assert status == 4               
     689        assert value is None       
     690
     691
     692    def test_intersection_coincide(self):
     693        """def test_intersection_coincide(self):
     694        Test what happens whe two lines partly coincide
     695        """
     696
     697        # Overlap 1
     698        line0 = [[0,0], [5,0]]
     699        line1 = [[-3,0], [3,0]]
     700
     701        status, value = intersection(line0, line1)
     702        assert status == 2
     703        assert allclose(value, [[0,0], [3,0]])
     704
     705        # Overlap 2
     706        line0 = [[-10,0], [5,0]]
     707        line1 = [[-3,0], [10,0]]
     708
     709        status, value = intersection(line0, line1)
     710        assert status == 2
     711        assert allclose(value, [[-3, 0], [5,0]])       
     712
     713        # Inclusion 1
     714        line0 = [[0,0], [5,0]]
     715        line1 = [[2,0], [3,0]]
     716
     717        status, value = intersection(line0, line1)
     718        assert status == 2       
     719        assert allclose(value, line1)
     720
     721        # Inclusion 2
     722        line0 = [[1,0], [5,0]]
     723        line1 = [[-10,0], [15,0]]
     724
     725        status, value = intersection(line0, line1)
     726        assert status == 2       
     727        assert allclose(value, line0)                                       
     728
     729
     730        # Exclusion (no intersection)
     731        line0 = [[-10,0], [1,0]]
     732        line1 = [[3,0], [15,0]]
     733
     734        status, value = intersection(line0, line1)
     735        assert status == 3       
     736        assert value is None
     737       
     738
     739        # Try examples with some slope (y=2*x+5)
     740
     741        # Overlap
     742        line0 = [[0,5], [7,19]]
     743        line1 = [[1,7], [10,25]]
     744        status, value = intersection(line0, line1)
     745        assert status == 2               
     746        assert allclose(value, [[1, 7], [7, 19]])
     747
     748        status, value = intersection(line1, line0)
     749        assert status == 2
     750        assert allclose(value, [[1, 7], [7, 19]])
     751
     752        # Swap direction
     753        line0 = [[7,19], [0,5]]
     754        line1 = [[1,7], [10,25]]
     755        status, value = intersection(line0, line1)
     756        assert status == 2
     757        assert allclose(value, [[7, 19], [1, 7]])
     758
     759        line0 = [[0,5], [7,19]]
     760        line1 = [[10,25], [1,7]]
     761        status, value = intersection(line0, line1)
     762        assert status == 2
     763        assert allclose(value, [[1, 7], [7, 19]])       
     764       
     765
     766        # Inclusion
     767        line0 = [[1,7], [7,19]]
     768        line1 = [[0,5], [10,25]]
     769        status, value = intersection(line0, line1)
     770        assert status == 2                       
     771        assert allclose(value, [[1,7], [7, 19]])               
     772
     773        line0 = [[0,5], [10,25]]
     774        line1 = [[1,7], [7,19]]
     775        status, value = intersection(line0, line1)
     776        assert status == 2                       
     777        assert allclose(value, [[1,7], [7, 19]])
     778
     779
     780        line0 = [[0,5], [10,25]]
     781        line1 = [[7,19], [1,7]]
     782        status, value = intersection(line0, line1)
     783        assert status == 2                       
     784        assert allclose(value, [[7, 19], [1, 7]])                       
    679785       
    680786       
Note: See TracChangeset for help on using the changeset viewer.