Changeset 5942


Ignore:
Timestamp:
Nov 12, 2008, 10:55:39 AM (16 years ago)
Author:
rwilson
Message:

Modified intersection() code to handle special cases, added lots of test cases.

Location:
anuga_core/source/anuga/utilities
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • anuga_core/source/anuga/utilities/polygon.py

    r5932 r5942  
    4242
    4343
    44 
    45 
     44######
     45# Result functions used in intersection() below for collinear lines.
     46# (p0,p1) defines line 0, (p2,p3) defines line 1.
     47######
     48
     49# result functions for possible states
     50def lines_dont_coincide(p0,p1,p2,p3):               return (3, None)
     51def lines_0_fully_included_in_1(p0,p1,p2,p3):       return (2, array([p0,p1]))
     52def lines_1_fully_included_in_0(p0,p1,p2,p3):       return (2, array([p2,p3]))
     53def lines_overlap_same_direction(p0,p1,p2,p3):      return (2, array([p0,p3]))
     54def lines_overlap_same_direction2(p0,p1,p2,p3):     return (2, array([p2,p1]))
     55def lines_overlap_opposite_direction(p0,p1,p2,p3):  return (2, array([p0,p2]))
     56def lines_overlap_opposite_direction2(p0,p1,p2,p3): return (2, array([p3,p1]))
     57
     58# this function called when an impossible state is found
     59def lines_error(p1, p2, p3, p4): raise RuntimeError, "INTERNAL ERROR"
     60
     61#                     0s1    0e1    1s0    1e0   # line 0 starts on 1, 0 ends 1, 1 starts 0, 1 ends 0
     62collinear_result = { (False, False, False, False): lines_dont_coincide,
     63                     (False, False, False, True ): lines_error,
     64                     (False, False, True,  False): lines_error,
     65                     (False, False, True,  True ): lines_1_fully_included_in_0,
     66                     (False, True,  False, False): lines_error,
     67                     (False, True,  False, True ): lines_overlap_opposite_direction2,
     68                     (False, True,  True,  False): lines_overlap_same_direction2,
     69                     (False, True,  True,  True ): lines_1_fully_included_in_0,
     70                     (True,  False, False, False): lines_error,
     71                     (True,  False, False, True ): lines_overlap_same_direction,
     72                     (True,  False, True,  False): lines_overlap_opposite_direction,
     73                     (True,  False, True,  True ): lines_1_fully_included_in_0,
     74                     (True,  True,  False, False): lines_0_fully_included_in_1,
     75                     (True,  True,  False, True ): lines_0_fully_included_in_1,
     76                     (True,  True,  True,  False): lines_0_fully_included_in_1,
     77                     (True,  True,  True,  True ): lines_0_fully_included_in_1
     78                   }
    4679
    4780def intersection(line0, line1, rtol=1.0e-5, atol=1.0e-8):
    … …  
    5588    Inputs:
    5689        line0, line1: Each defined by two end points as in: [[x0, y0], [x1, y1]]
    57                       A line can also be a 2x2 numeric array with each row
     90                      A line can also be a 2x2 numpy array with each row
    5891                      corresponding to a point.
    5992
    … …  
    6295        status, value
    6396
    64         where status is interpreted as follows
     97        where status and value is interpreted as follows
    6598       
    66         status == 0: no intersection with value set to None
    67         status == 1: One intersection point found and returned in value as [x,y]
    68         status == 2: Coinciding line segment found. Value taks the form [[x0,y0], [x1,y1]]
    69         status == 3: Lines would coincide but only if extended. Value set to None
     99        status == 0: no intersection, value set to None.
     100        status == 1: intersection point found and returned in value as [x,y].
     101        status == 2: Collinear overlapping lines found. Value takes the form [[x0,y0], [x1,y1]].
     102        status == 3: Collinear non-overlapping lines. Value set to None.
    70103        status == 4: Lines are parallel with a fixed distance apart. Value set to None.
    71104   
    … …  
    88121       
    89122    if allclose(denom, 0.0, rtol=rtol, atol=atol):
    90         # Lines are parallel - check if they coincide on a shared a segment
    91 
    92         if allclose( [u0, u1], 0.0, rtol=rtol, atol=atol ):
    93             # We now know that the lines if continued coincide
    94             # The remaining check will establish if the finite lines share a segment
    95 
    96             line0_starts_on_line1 = line0_ends_on_line1 =\
    97             line1_starts_on_line0 = line1_ends_on_line0 = False
    98                
    99             if point_on_line([x0, y0], line1, rtol=rtol, atol=atol):
    100                 line0_starts_on_line1 = True
    101 
    102             if point_on_line([x1, y1], line1, rtol=rtol, atol=atol):
    103                 line0_ends_on_line1 = True
    104  
    105             if point_on_line([x2, y2], line0, rtol=rtol, atol=atol):
    106                 line1_starts_on_line0 = True
    107 
    108             if point_on_line([x3, y3], line0, rtol=rtol, atol=atol):
    109                 line1_ends_on_line0 = True                               
    110 
    111             if not(line0_starts_on_line1 or line0_ends_on_line1\
    112                or line1_starts_on_line0 or line1_ends_on_line0):
    113                 # Lines are parallel and would coincide if extended, but not as they are.
    114                 return 3, None
    115 
    116 
    117             # One line fully included in the other. Use direction of included line
    118             if line0_starts_on_line1 and line0_ends_on_line1:
    119                 # Shared segment is line0 fully included in line1
    120                 segment = array([[x0, y0], [x1, y1]])               
    121 
    122             if line1_starts_on_line0 and line1_ends_on_line0:
    123                 # Shared segment is line1 fully included in line0
    124                 segment = array([[x2, y2], [x3, y3]])
    125            
    126 
    127             # Overlap with lines are oriented the same way
    128             if line0_starts_on_line1 and line1_ends_on_line0:
    129                 # Shared segment from line0 start to line 1 end
    130                 segment = array([[x0, y0], [x3, y3]])
    131 
    132             if line1_starts_on_line0 and line0_ends_on_line1:
    133                 # Shared segment from line1 start to line 0 end
    134                 segment = array([[x2, y2], [x1, y1]])                               
    135 
    136 
    137             # Overlap in opposite directions - use direction of line0
    138             if line0_starts_on_line1 and line1_starts_on_line0:
    139                 # Shared segment from line0 start to line 1 end
    140                 segment = array([[x0, y0], [x2, y2]])
    141 
    142             if line0_ends_on_line1 and line1_ends_on_line0:
    143                 # Shared segment from line0 start to line 1 end
    144                 segment = array([[x3, y3], [x1, y1]])               
    145 
    146                
    147             return 2, segment
     123        # Lines are parallel - check if they are collinear
     124        if allclose([u0, u1], 0.0, rtol=rtol, atol=atol):
     125            # We now know that the lines are collinear
     126            state_tuple = (point_on_line([x0, y0], line1, rtol=rtol, atol=atol),
     127                           point_on_line([x1, y1], line1, rtol=rtol, atol=atol),
     128                           point_on_line([x2, y2], line0, rtol=rtol, atol=atol),
     129                           point_on_line([x3, y3], line0, rtol=rtol, atol=atol))
     130
     131            return collinear_result[state_tuple]([x0,y0],[x1,y1],[x2,y2],[x3,y3])
    148132        else:
    149             # Lines are parallel but they don't coincide
     133            # Lines are parallel but aren't collinear
    150134            return 4, None #FIXME (Ole): Add distance here instead of None
    151            
    152135    else:
    153         # Lines are not parallel or coinciding
     136        # Lines are not parallel, check if they intersect
    154137        u0 = u0/denom
    155138        u1 = u1/denom       
    … …  
    165148        if 0.0 <= u0 <= 1.0 and 0.0 <= u1 <= 1.0:
    166149            # We have intersection
    167 
    168150            return 1, array([x, y])
    169151        else:

  • anuga_core/source/anuga/utilities/test_polygon.py

    r5940 r5942  
    650650        assert status == 1
    651651        assert allclose(value, [1.0, 1.0])       
    652        
    653 
    654     # This function is a helper function for the test_intersection_bug_20081110_?()
    655     # set of tests.
     652
     653
     654    # This function is a helper function for
     655    # the test_intersection_bug_20081110_?() set of tests.
     656    # This function tests all parallel line cases for 4 collinear points.
    656657    # This function should never be run directly by the unittest code.
    657658    def helper_test_parallel_intersection_code(self, P1, P2, P3, P4):
    … …  
    700701                                       str(value))
    701702
     703        #----------------------------------------------------------------------
     704
    702705        # line0 fully within line1, same direction
    703706        # 0:         ---->----
    … …  
    748751        self.failUnless(allclose(value, line0))
    749752
     753        #----------------------------------------------------------------------
     754
    750755        # line1 fully within line0, same direction
    751756        # 0:    --------->-----------
    … …  
    796801        self.failUnless(allclose(value, line1))
    797802
     803        #----------------------------------------------------------------------
     804
    798805        # line in same direction, partial overlap
    799806        # 0:    ----->-----
    … …  
    844851        self.failUnless(allclose(value, [line1[1],line0[1]]))
    845852
     853        #----------------------------------------------------------------------
     854
    846855        # line in same direction, partial overlap
    847856        # 0:       ------>------
    … …  
    892901        self.failUnless(allclose(value, [line0[0],line1[0]]))
    893902
    894        
    895     def test_intersection_bug_20081110_1(self):
     903        #----------------------------------------------------------------------
     904
     905        # line in same direction, same left point, line1 longer
     906        # 0:    ----->------
     907        # 1:    ------->--------
     908        # value should be line0:
     909        #       ----->------
     910        line0 = [P1,P3]
     911        line1 = [P1,P4]
     912        status, value = intersection(line0, line1)
     913        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     914                               (str(status), str(value)))
     915        self.failUnless(allclose(value, line0))
     916
     917        # line in same direction, same left point, line1 longer
     918        # 0:    -----<------
     919        # 1:    -------<--------
     920        # value should be line0:
     921        #       -----<------
     922        line0 = [P3,P1]
     923        line1 = [P4,P1]
     924        status, value = intersection(line0, line1)
     925        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     926                               (str(status), str(value)))
     927        self.failUnless(allclose(value, line0))
     928
     929        # line in opposite direction, same left point, line1 longer
     930        # 0:    ----->------
     931        # 1:    -------<--------
     932        # value should be line0:
     933        #       ----->------
     934        line0 = [P1,P3]
     935        line1 = [P4,P1]
     936        status, value = intersection(line0, line1)
     937        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     938                               (str(status), str(value)))
     939        self.failUnless(allclose(value, line0))
     940
     941        # line in opposite direction, same start point, line1 longer
     942        # 0:    -----<------
     943        # 1:    ------->--------
     944        # value should be line0:
     945        #       -----<------
     946        line0 = [P3,P1]
     947        line1 = [P1,P4]
     948        status, value = intersection(line0, line1)
     949        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     950                               (str(status), str(value)))
     951        self.failUnless(allclose(value, line0))
     952
     953        #----------------------------------------------------------------------
     954
     955        # line in same direction, same left point, same right point
     956        # 0:    ------->--------
     957        # 1:    ------->--------
     958        # value should be line0 or line1:
     959        #       ------->--------
     960        line0 = [P1,P3]
     961        line1 = [P1,P3]
     962        status, value = intersection(line0, line1)
     963        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     964                               (str(status), str(value)))
     965        self.failUnless(allclose(value, line0))
     966
     967        # line in same direction, same left point, same right point
     968        # 0:    -------<--------
     969        # 1:    -------<--------
     970        # value should be line0 (or line1):
     971        #       -------<--------
     972        line0 = [P3,P1]
     973        line1 = [P3,P1]
     974        status, value = intersection(line0, line1)
     975        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     976                               (str(status), str(value)))
     977        self.failUnless(allclose(value, line0))
     978
     979        # line in opposite direction, same left point, same right point
     980        # 0:    ------->--------
     981        # 1:    -------<--------
     982        # value should be line0:
     983        #       ------->--------
     984        line0 = [P1,P3]
     985        line1 = [P3,P1]
     986        status, value = intersection(line0, line1)
     987        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     988                               (str(status), str(value)))
     989        self.failUnless(allclose(value, line0))
     990
     991        # line in opposite direction, same left point, same right point
     992        # 0:    -------<--------
     993        # 1:    ------->--------
     994        # value should be line0:
     995        #       -------<--------
     996        line0 = [P3,P1]
     997        line1 = [P1,P3]
     998        status, value = intersection(line0, line1)
     999        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1000                               (str(status), str(value)))
     1001        self.failUnless(allclose(value, line0))
     1002
     1003        #----------------------------------------------------------------------
     1004
     1005        # line in same direction, same right point, line1 longer
     1006        # 0:        ----->------
     1007        # 1:    ------->--------
     1008        # value should be line0:
     1009        #           ----->------
     1010        line0 = [P2,P4]
     1011        line1 = [P1,P4]
     1012        status, value = intersection(line0, line1)
     1013        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1014                               (str(status), str(value)))
     1015        self.failUnless(allclose(value, line0))
     1016
     1017        # line in same direction, same right point, line1 longer
     1018        # 0:        -----<------
     1019        # 1:    -------<--------
     1020        # value should be line0:
     1021        #           -----<------
     1022        line0 = [P4,P2]
     1023        line1 = [P4,P1]
     1024        status, value = intersection(line0, line1)
     1025        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1026                               (str(status), str(value)))
     1027        self.failUnless(allclose(value, line0))
     1028
     1029        # line in opposite direction, same right point, line1 longer
     1030        # 0:        ----->------
     1031        # 1:    -------<--------
     1032        # value should be line0:
     1033        #           ----->------
     1034        line0 = [P2,P4]
     1035        line1 = [P4,P1]
     1036        status, value = intersection(line0, line1)
     1037        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1038                               (str(status), str(value)))
     1039        self.failUnless(allclose(value, line0))
     1040
     1041        # line in opposite direction, same right point, line1 longer
     1042        # 0:        -----<------
     1043        # 1:    ------->--------
     1044        # value should be line0:
     1045        #           -----<------
     1046        line0 = [P4,P2]
     1047        line1 = [P1,P4]
     1048        status, value = intersection(line0, line1)
     1049        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1050                               (str(status), str(value)))
     1051        self.failUnless(allclose(value, line0))
     1052
     1053        #----------------------------------------------------------------------
     1054
     1055        # line in same direction, same left point, line0 longer
     1056        # 0:    ------->--------
     1057        # 1:    ----->------
     1058        # value should be line1:
     1059        #       ----->------
     1060        line0 = [P1,P4]
     1061        line1 = [P1,P3]
     1062        status, value = intersection(line0, line1)
     1063        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1064                               (str(status), str(value)))
     1065        self.failUnless(allclose(value, line1))
     1066
     1067        # line in same direction, same left point, line0 longer
     1068        # 0:    -------<--------
     1069        # 1:    -----<------
     1070        # value should be line1:
     1071        #       -----<------
     1072        line0 = [P4,P1]
     1073        line1 = [P3,P1]
     1074        status, value = intersection(line0, line1)
     1075        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1076                               (str(status), str(value)))
     1077        self.failUnless(allclose(value, line1))
     1078
     1079        # line in opposite direction, same left point, line0 longer
     1080        # 0:    ------->--------
     1081        # 1:    -----<------
     1082        # value should be line1:
     1083        #       -----<------
     1084        line0 = [P1,P4]
     1085        line1 = [P3,P1]
     1086        status, value = intersection(line0, line1)
     1087        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1088                               (str(status), str(value)))
     1089        self.failUnless(allclose(value, line1))
     1090
     1091        # line in opposite direction, same left point, line0 longer
     1092        # 0:    -------<--------
     1093        # 1:    ----->------
     1094        # value should be line1:
     1095        #       ----->------
     1096        line0 = [P4,P1]
     1097        line1 = [P1,P3]
     1098        status, value = intersection(line0, line1)
     1099        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1100                               (str(status), str(value)))
     1101        self.failUnless(allclose(value, line1))
     1102
     1103        #----------------------------------------------------------------------
     1104
     1105        # line in same direction, same right point, line0 longer
     1106        # 0:    ------->--------
     1107        # 1:        ----->------
     1108        # value should be line1:
     1109        #           ----->------
     1110        line0 = [P1,P4]
     1111        line1 = [P2,P4]
     1112        status, value = intersection(line0, line1)
     1113        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1114                               (str(status), str(value)))
     1115        self.failUnless(allclose(value, line1))
     1116
     1117        # line in same direction, same right point, line0 longer
     1118        # 0:    -------<--------
     1119        # 1:        -----<------
     1120        # value should be line1:
     1121        #           -----<------
     1122        line0 = [P4,P1]
     1123        line1 = [P4,P2]
     1124        status, value = intersection(line0, line1)
     1125        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1126                               (str(status), str(value)))
     1127        self.failUnless(allclose(value, line1))
     1128
     1129        # line in opposite direction, same right point, line0 longer
     1130        # 0:    ------->--------
     1131        # 1:        -----<------
     1132        # value should be line1:
     1133        #           -----<------
     1134        line0 = [P1,P4]
     1135        line1 = [P4,P2]
     1136        status, value = intersection(line0, line1)
     1137        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1138                               (str(status), str(value)))
     1139        self.failUnless(allclose(value, line1))
     1140
     1141        # line in opposite direction, same right point, line0 longer
     1142        # 0:    -------<--------
     1143        # 1:        ----->------
     1144        # value should be line1:
     1145        #           ----->------
     1146        line0 = [P4,P1]
     1147        line1 = [P2,P4]
     1148        status, value = intersection(line0, line1)
     1149        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
     1150                               (str(status), str(value)))
     1151        self.failUnless(allclose(value, line1))
     1152
     1153       
     1154    def test_intersection_bug_20081110_TR(self):
    8961155        """test_intersection_bug_20081110(self)
    8971156
    898         Run through all possible cases of parallel lines.
     1157        Test all cases in top-right quadrant
    8991158        """
    9001159
    901         # define 4 collinear points
     1160        # define 4 collinear points in top-right quadrant
    9021161        #    P1---P2---P3---P4
    903         P1 = [1.0, 0.0]
    904         P2 = [2.0, 0.0]
    905         P3 = [3.0, 0.0]
    906         P4 = [4.0, 0.0]
    907        
     1162        P1 = [1.0, 1.0]
     1163        P2 = [2.0, 2.0]
     1164        P3 = [3.0, 3.0]
     1165        P4 = [4.0, 4.0]
     1166       
     1167        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1168        P1 = [1.0, 1.0+1.0e-9]
    9081169        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
    909 
    910 
    911     def test_intersection_bug_20081110_2(self):
     1170        P1 = [1.0, 1.0]
     1171        P2 = [2.0, 2.0+1.0e-9]
     1172        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1173        P2 = [2.0, 2.0]
     1174        P3 = [3.0, 3.0+1.0e-9]
     1175        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1176        P3 = [3.0, 3.0]
     1177        P4 = [4.0, 4.0+1.0e-9]
     1178        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1179
     1180    def test_intersection_bug_20081110_TL(self):
    9121181        """test_intersection_bug_20081110(self)
    9131182
    914         Run through all possible cases of parallel lines.
     1183        Test all cases in top-left quadrant
    9151184        """
    9161185
    917         # define 4 *almost* collinear points
     1186        # define 4 collinear points in top-left quadrant
    9181187        #    P1---P2---P3---P4
    919         P1 = [1.0, 1.0e-9]
    920         P2 = [2.0, 0.0]
    921         P3 = [3.0, 0.0]
    922         P4 = [4.0, 0.0]
    923 
     1188        P1 = [-1.0, 1.0]
     1189        P2 = [-2.0, 2.0]
     1190        P3 = [-3.0, 3.0]
     1191        P4 = [-4.0, 4.0]
     1192       
     1193        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1194        P1 = [-1.0, 1.0+1.0e-9]
    9241195        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
    925 
    926 
    927     def test_intersection_bug_20081110_3(self):
     1196        P1 = [-1.0, 1.0]
     1197        P2 = [-2.0, 2.0+1.0e-9]
     1198        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1199        P2 = [-2.0, 2.0]
     1200        P3 = [-3.0, 3.0+1.0e-9]
     1201        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1202        P3 = [-3.0, 3.0]
     1203        P4 = [-4.0, 4.0+1.0e-9]
     1204        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1205
     1206    def test_intersection_bug_20081110_BL(self):
    9281207        """test_intersection_bug_20081110(self)
    9291208
    930         Run through all possible cases of parallel lines.
     1209        Test all cases in bottom-left quadrant
    9311210        """
    9321211
    933         # define 4 *almost* collinear points
     1212        # define 4 collinear points in bottom-left quadrant
    9341213        #    P1---P2---P3---P4
    935         P1 = [1.0, 0.0]
    936         P2 = [2.0, 1.0e-9]
    937         P3 = [3.0, 0.0]
    938         P4 = [4.0, 0.0]
    939 
     1214        P1 = [-1.0, -1.0]
     1215        P2 = [-2.0, -2.0]
     1216        P3 = [-3.0, -3.0]
     1217        P4 = [-4.0, -4.0]
     1218       
     1219        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1220        P1 = [-1.0, -1.0+1.0e-9]
    9401221        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
    941 
    942 
    943     def test_intersection_bug_20081110_4(self):
     1222        P1 = [-1.0, -1.0]
     1223        P2 = [-2.0, -2.0+1.0e-9]
     1224        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1225        P2 = [-2.0, -2.0]
     1226        P3 = [-3.0, -3.0+1.0e-9]
     1227        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1228        P3 = [-3.0, -3.0]
     1229        P4 = [-4.0, -4.0+1.0e-9]
     1230        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1231
     1232    def test_intersection_bug_20081110_BR(self):
    9441233        """test_intersection_bug_20081110(self)
    9451234
    946         Run through all possible cases of parallel lines.
     1235        Test all cases in bottom-right quadrant
    9471236        """
    9481237
    949         # define 4 *almost* collinear points
     1238        # define 4 collinear points in bottom-right quadrant
    9501239        #    P1---P2---P3---P4
    951         P1 = [1.0, 0.0]
    952         P2 = [2.0, 0.0]
    953         P3 = [3.0, 1.0e-9]
    954         P4 = [4.0, 0.0]
    955 
     1240        P1 = [1.0, -1.0]
     1241        P2 = [2.0, -2.0]
     1242        P3 = [3.0, -3.0]
     1243        P4 = [4.0, -4.0]
     1244       
     1245        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1246        P1 = [1.0, -1.0+1.0e-9]
    9561247        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
    957 
    958 
    959     def test_intersection_bug_20081110_5(self):
     1248        P1 = [1.0, -1.0]
     1249        P2 = [2.0, -2.0+1.0e-9]
     1250        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1251        P2 = [2.0, -2.0]
     1252        P3 = [3.0, -3.0+1.0e-9]
     1253        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1254        P3 = [3.0, -3.0]
     1255        P4 = [4.0, -4.0+1.0e-9]
     1256        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
     1257
     1258    def test_intersection_bug_20081110_TR_TL(self):
    9601259        """test_intersection_bug_20081110(self)
    9611260
    962         Run through all possible cases of parallel lines.
     1261        Test all cases in top-right & top-left quadrant
    9631262        """
    9641263
    965         # define 4 *almost* collinear points
     1264        # define 4 collinear points, 1 in TL, 3 in TR
    9661265        #    P1---P2---P3---P4
    967         P1 = [1.0, 0.0]
    968         P2 = [2.0, 0.0]
    969         P3 = [3.0, 0.0]
    970         P4 = [4.0, 1.0e-9]
    971 
    972         self.helper_test_parallel_intersection_code(P1, P2, P3, P4)       
    973 
    974 
    975     def test_intersection_bug_20081111(self):
    976         """test_intersection_bug_20081111(self)
    977 
    978         Case from Rajaraman that is failing still.
     1266        P1 = [-3.0, 1.0]
     1267        P2 = [ 1.0, 5.0]
     1268        P3 = [ 2.0, 6.0]
     1269        P4 = [ 3.0, 7.0]
     1270        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1271
     1272        # define 4 collinear points, 2 in TL, 2 in TR
     1273        #    P1---P2---P3---P4
     1274        P1 = [-3.0, 1.0]
     1275        P2 = [-2.0, 2.0]
     1276        P3 = [ 2.0, 6.0]
     1277        P4 = [ 3.0, 7.0]
     1278        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1279
     1280        # define 4 collinear points, 2 in TL, 1 in TR
     1281        #    P1---P2---P3---P4
     1282        P1 = [-3.0, 1.0]
     1283        P2 = [-2.0, 2.0]
     1284        P3 = [-1.0, 3.0]
     1285        P4 = [ 3.0, 7.0]
     1286        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1287
     1288    def test_intersection_bug_20081110_TR_BL(self):
     1289        """test_intersection_bug_20081110(self)
     1290
     1291        Test all cases in top-right & bottom-left quadrant
    9791292        """
    9801293
    981         # define 4  collinear points
    982         #
    983         #   Y
    984         #   ^
    985         #   |         x (2,2)
    986         #   |        /
    987         #   |       /
    988         #   |      /
    989         #   |     /
    990         #   |    x (1,1)
    991         #   |   /
    992         #   |  /
    993         #   | /
    994         #   |/
    995         #   x------------>X
    996 
    997         line0 = [[2.0, 2.0],[0.0,0.0]]
    998         line1 = [[1.0, 1.0],[0.0,0.0]]
    999 
    1000         status, value = intersection(line0, line1)
    1001         print 'status=%s, value=%s' % (str(status), str(value))
    1002        
    1003         self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
    1004                                (str(status), str(value)))
    1005         self.failUnless(allclose(value, [line0[0],line1[1]]))
     1294        # define 4 collinear points, 1 in BL, 3 in TR
     1295        #    P1---P2---P3---P4
     1296        P1 = [-4.0, -3.0]
     1297        P2 = [ 1.0,  2.0]
     1298        P3 = [ 2.0,  3.0]
     1299        P4 = [ 3.0,  4.0]
     1300        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1301
     1302        # define 4 collinear points, 2 in TL, 2 in TR
     1303        #    P1---P2---P3---P4
     1304        P1 = [-4.0, -3.0]
     1305        P2 = [-3.0, -2.0]
     1306        P3 = [ 2.0,  3.0]
     1307        P4 = [ 3.0,  4.0]
     1308        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1309
     1310        # define 4 collinear points, 3 in TL, 1 in TR
     1311        #    P1---P2---P3---P4
     1312        P1 = [-4.0, -3.0]
     1313        P2 = [-3.0, -2.0]
     1314        P3 = [-2.0, -1.0]
     1315        P4 = [ 3.0,  4.0]
     1316        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1317
     1318    def test_intersection_bug_20081110_TR_BR(self):
     1319        """test_intersection_bug_20081110(self)
     1320
     1321        Test all cases in top-right & bottom-right quadrant
     1322        """
     1323
     1324        # define 4 collinear points, 1 in BR, 3 in TR
     1325        #    P1---P2---P3---P4
     1326        P1 = [ 1.0, -3.0]
     1327        P2 = [ 5.0,  1.0]
     1328        P3 = [ 6.0,  2.0]
     1329        P4 = [ 7.0,  3.0]
     1330        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1331
     1332        # define 4 collinear points, 2 in BR, 2 in TR
     1333        #    P1---P2---P3---P4
     1334        P1 = [ 1.0, -3.0]
     1335        P2 = [ 2.0, -2.0]
     1336        P3 = [ 6.0,  2.0]
     1337        P4 = [ 7.0,  3.0]
     1338        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
     1339
     1340        # define 4 collinear points, 3 in BR, 1 in TR
     1341        #    P1---P2---P3---P4
     1342        P1 = [ 1.0, -3.0]
     1343        P2 = [ 2.0, -2.0]
     1344        P3 = [ 3.0, -1.0]
     1345        P4 = [ 7.0,  3.0]
     1346        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
    10061347
    10071348
    … …  
    13441685if __name__ == "__main__":
    13451686    suite = unittest.makeSuite(Test_Polygon,'test')
    1346     #suite = unittest.makeSuite(Test_Polygon,'test_inside_polygon_geo_ref')
     1687#    suite = unittest.makeSuite(Test_Polygon,'test_intersection_bug_20081111')
    13471688    runner = unittest.TextTestRunner()
    13481689    runner.run(suite)
Note: See TracChangeset for help on using the changeset viewer.