source: trunk/anuga_core/source/anuga/geometry/test_polygon.py @ 7841

Last change on this file since 7841 was 7841, checked in by hudson, 14 years ago

Refactorings to allow tests to pass.

File size: 67.6 KB
Line 
1#!/usr/bin/env python
2
3import unittest
4import numpy as num
5from math import sqrt, pi
6from anuga.utilities.numerical_tools import ensure_numeric
7from anuga.utilities.system_tools import get_pathname_from_package
8
9from polygon import *
10from anuga.coordinate_transforms.geo_reference import Geo_reference
11from anuga.geospatial_data.geospatial_data import Geospatial_data
12
13
14def test_function(x, y):
15    return x+y
16
17
18class Test_Polygon(unittest.TestCase):
19    def setUp(self):
20        pass
21
22    def tearDown(self):
23        pass
24
25    def test_that_C_extension_compiles(self):
26        FN = 'polygon_ext.c'
27        try:
28            import polygon_ext
29        except:
30            from compile import compile
31
32            try:
33                compile(FN)
34            except:
35                raise Exception, 'Could not compile %s' %FN
36            else:
37                import polygon_ext
38
39    # Polygon stuff
40    def test_polygon_function_constants(self):
41        p1 = [[0,0], [10,0], [10,10], [0,10]]
42        p2 = [[0,0], [10,10], [15,5], [20, 10], [25,0], [30,10], [40,-10]]
43
44        f = Polygon_function([(p1, 1.0)])
45        z = f([5, 5, 27, 35], [5, 9, 8, -5])    # Two first inside p1
46        assert num.allclose(z, [1, 1, 0, 0])
47
48        f = Polygon_function([(p2, 2.0)])
49        z = f([5, 5, 27, 35], [5, 9, 8, -5])    # First and last inside p2
50        assert num.allclose(z, [2, 0, 0, 2])
51
52        # Combined
53        f = Polygon_function([(p1, 1.0), (p2, 2.0)])
54        z = f([5, 5, 27, 35], [5, 9, 8, -5])
55        assert num.allclose(z, [2, 1, 0, 2])
56
57    def test_polygon_function_csvfile(self):
58        from os import sep, getenv
59
60        # Get path where this test is run
61        path = get_pathname_from_package('anuga.utilities')
62
63        # Form absolute filename and read
64        filename = path + sep + 'mainland_only.csv'
65        p1 = read_polygon(filename)
66
67        f = Polygon_function([(p1, 10.0)])
68        z = f([430000, 480000], [490000, 7720000]) # 1st outside, 2nd inside
69
70        assert num.allclose(z, [0, 10])
71
72    def test_polygon_function_georef(self):
73        """Check that georeferencing works"""
74
75        from anuga.coordinate_transforms.geo_reference import Geo_reference
76
77        geo = Geo_reference(56, 200, 1000)
78
79        # Make points 'absolute'
80        p1 = [[200,1000], [210,1000], [210,1010], [200,1010]]
81        p2 = [[200,1000], [210,1010], [215,1005], [220, 1010], [225,1000],
82              [230,1010], [240,990]]
83
84        f = Polygon_function([(p1, 1.0)], geo_reference=geo)
85        z = f([5, 5, 27, 35], [5, 9, 8, -5]) # Two first inside p1
86
87        assert num.allclose(z, [1, 1, 0, 0])
88
89        f = Polygon_function([(p2, 2.0)], geo_reference=geo)
90        z = f([5, 5, 27, 35], [5, 9, 8, -5]) # First and last inside p2
91        assert num.allclose(z, [2, 0, 0, 2])
92
93        # Combined
94        f = Polygon_function([(p1, 1.0), (p2, 2.0)], geo_reference=geo)
95        z = f([5, 5, 27, 35], [5, 9, 8, -5])
96        assert num.allclose(z, [2, 1, 0, 2])
97
98        # Check that it would fail without geo
99        f = Polygon_function([(p1, 1.0), (p2, 2.0)])
100        z = f([5, 5, 27, 35], [5, 9, 8, -5])
101        assert not num.allclose(z, [2, 1, 0, 2])
102
103    def test_polygon_function_callable(self):
104        """Check that values passed into Polygon_function can be callable."""
105
106        p1 = [[0,0], [10,0], [10,10], [0,10]]
107        p2 = [[0,0], [10,10], [15,5], [20, 10], [25,0], [30,10], [40,-10]]
108
109        f = Polygon_function([(p1, test_function)])
110        z = f([5, 5, 27, 35], [5, 9, 8, -5]) # Two first inside p1
111        assert num.allclose(z, [10, 14, 0, 0])
112
113        # Combined
114        f = Polygon_function([(p1, test_function), (p2, 2.0)])
115        z = f([5, 5, 27, 35], [5, 9, 8, -5])
116        assert num.allclose(z, [2, 14, 0, 2])
117
118        # Combined w default
119        f = Polygon_function([(p1, test_function), (p2, 2.0)], default = 3.14)
120        z = f([5, 5, 27, 35], [5, 9, 8, -5])
121        assert num.allclose(z, [2, 14, 3.14, 2])
122
123        # Combined w default func
124        f = Polygon_function([(p1, test_function), (p2, 2.0)],
125                             default=test_function)
126        z = f([5, 5, 27, 35], [5, 9, 8, -5])
127        assert num.allclose(z, [2, 14, 35, 2])
128
129    def test_point_on_line(self):
130        # Endpoints first
131        assert point_on_line([0,0], [[0,0], [1,0]])
132        assert point_on_line([1,0], [[0,0], [1,0]])
133
134        # Endpoints first - non-simple
135        assert point_on_line([-0.1,0.0], [[-0.1,0.0], [1.5,0.6]])
136        assert point_on_line([1.5,0.6], [[-0.1,0.0], [1.5,0.6]])
137
138        # Then points on line
139        assert point_on_line([0.5,0], [[0,0], [1,0]])
140        assert point_on_line([0,0.5], [[0,1], [0,0]])
141        assert point_on_line([1,0.5], [[1,1], [1,0]])
142        assert point_on_line([0.5,0.5], [[0,0], [1,1]])
143
144        # Then points not on line
145        assert not point_on_line([0.5,0], [[0,1], [1,1]])
146        assert not point_on_line([0,0.5], [[0,0], [1,1]])
147
148        # From real example that failed
149        assert not point_on_line([40,50], [[40,20], [40,40]])
150
151        # From real example that failed
152        assert not point_on_line([40,19], [[40,20], [40,40]])
153
154        # Degenerate line
155        assert point_on_line([40,19], [[40,19], [40,19]])
156        assert not point_on_line([40,19], [[40,40], [40,40]])
157
158    def test_is_inside_polygon_main(self):
159        # Simplest case: Polygon is the unit square
160        polygon = [[0,0], [1,0], [1,1], [0,1]]
161
162        assert is_inside_polygon((0.5, 0.5), polygon)
163        assert not is_inside_polygon((0.5, 1.5), polygon)
164        assert not is_inside_polygon((0.5, -0.5), polygon)
165        assert not is_inside_polygon((-0.5, 0.5), polygon)
166        assert not is_inside_polygon((1.5, 0.5), polygon)
167
168        # Try point on borders
169        assert is_inside_polygon((1., 0.5), polygon, closed=True)
170        assert is_inside_polygon((0.5, 1.), polygon, closed=True)
171        assert is_inside_polygon((0., 0.5), polygon, closed=True)
172        assert is_inside_polygon((0.5, 0.), polygon, closed=True)
173
174        assert not is_inside_polygon((0.5, 1.), polygon, closed=False)
175        assert not is_inside_polygon((0., 0.5), polygon, closed=False)
176        assert not is_inside_polygon((0.5, 0.), polygon, closed=False)
177        assert not is_inside_polygon((1., 0.5), polygon, closed=False)
178
179    def test_inside_polygon_main(self):
180        """test_is_inside_polygon
181       
182        Test fast version of of is_inside_polygon
183        """
184
185        # Simplest case: Polygon is the unit square
186        polygon = [[0,0], [1,0], [1,1], [0,1]]
187
188        assert is_inside_polygon( (0.5, 0.5), polygon )
189        assert not is_inside_polygon( (0.5, 1.5), polygon )
190        assert not is_inside_polygon( (0.5, -0.5), polygon )
191        assert not is_inside_polygon( (-0.5, 0.5), polygon )
192        assert not is_inside_polygon( (1.5, 0.5), polygon )
193
194        # Try point on borders
195        assert is_inside_polygon( (1., 0.5), polygon, closed=True)
196        assert is_inside_polygon( (0.5, 1), polygon, closed=True)
197        assert is_inside_polygon( (0., 0.5), polygon, closed=True)
198        assert is_inside_polygon( (0.5, 0.), polygon, closed=True)
199
200        assert not is_inside_polygon( (0.5, 1), polygon, closed=False)
201        assert not is_inside_polygon( (0., 0.5), polygon, closed=False)
202        assert not is_inside_polygon( (0.5, 0.), polygon, closed=False)
203        assert not is_inside_polygon( (1., 0.5), polygon, closed=False)
204
205
206    def test_inside_polygon_main(self):
207        # Simplest case: Polygon is the unit square
208        polygon = [[0,0], [1,0], [1,1], [0,1]]
209
210        # From real example (that failed)
211        polygon = [[20,20], [40,20], [40,40], [20,40]]
212        points = [[40, 50]]
213        res = inside_polygon(points, polygon)
214        assert len(res) == 0
215
216        polygon = [[20,20], [40,20], [40,40], [20,40]]
217        points = [[25, 25], [30, 20], [40, 50], [90, 20], [40, 90]]
218        res = inside_polygon(points, polygon)
219        assert len(res) == 2
220        assert num.allclose(res, [0,1])
221
222        # More convoluted and non convex polygon
223        polygon = [[0,0], [1,0], [0.5,-1], [2, -1], [2,1], [0,1]]
224        assert is_inside_polygon( (0.5, 0.5), polygon )
225        assert is_inside_polygon( (1, -0.5), polygon )
226        assert is_inside_polygon( (1.5, 0), polygon )
227
228        assert not is_inside_polygon( (0.5, 1.5), polygon )
229        assert not is_inside_polygon( (0.5, -0.5), polygon )
230
231        assert is_inside_polygon( (0.5, 0.5), polygon )
232        assert is_inside_polygon( (1, -0.5), polygon )
233        assert is_inside_polygon( (1.5, 0), polygon )
234
235        assert not is_inside_polygon( (0.5, 1.5), polygon )
236        assert not is_inside_polygon( (0.5, -0.5), polygon )
237
238        # Very convoluted polygon
239        polygon = [[0,0], [10,10], [15,5], [20, 10], [25,0], [30,10], [40,-10]]
240        assert is_inside_polygon((5, 5), polygon)
241        assert is_inside_polygon((17, 7), polygon)
242        assert is_inside_polygon((27, 2), polygon)
243        assert is_inside_polygon((35, -5), polygon)
244        assert not is_inside_polygon((15, 7), polygon)
245        assert not is_inside_polygon((24, 3), polygon)
246        assert not is_inside_polygon((25, -10), polygon)
247
248        # Another combination (that failed)
249        polygon = [[0,0], [10,0], [10,10], [0,10]]
250        assert is_inside_polygon((5, 5), polygon)
251        assert is_inside_polygon((7, 7), polygon)
252        assert not is_inside_polygon((-17, 7), polygon)
253        assert not is_inside_polygon((7, 17), polygon)
254        assert not is_inside_polygon((17, 7), polygon)
255        assert not is_inside_polygon((27, 8), polygon)
256        assert not is_inside_polygon((35, -5), polygon)
257
258        # Multiple polygons
259        polygon = [[0,0], [1,0], [1,1], [0,1], [0,0], [10,10],
260                   [11,10], [11,11], [10,11], [10,10]]
261        assert is_inside_polygon((0.5, 0.5), polygon)
262        assert is_inside_polygon((10.5, 10.5), polygon)
263
264        # FIXME: Fails if point is 5.5, 5.5
265        assert not is_inside_polygon((0, 5.5), polygon)
266
267        # Polygon with a hole
268        polygon = [[-1,-1], [2,-1], [2,2], [-1,2], [-1,-1],
269                   [0,0], [1,0], [1,1], [0,1], [0,0]]
270
271        assert is_inside_polygon((0, -0.5), polygon)
272        assert not is_inside_polygon((0.5, 0.5), polygon)
273
274    def test_duplicate_points_being_ok(self):
275        # Simplest case: Polygon is the unit square
276        polygon = [[0,0], [1,0], [1,0], [1,0], [1,1], [0,1], [0,0]]
277
278        assert is_inside_polygon((0.5, 0.5), polygon)
279        assert not is_inside_polygon((0.5, 1.5), polygon)
280        assert not is_inside_polygon((0.5, -0.5), polygon)
281        assert not is_inside_polygon((-0.5, 0.5), polygon)
282        assert not is_inside_polygon((1.5, 0.5), polygon)
283
284        # Try point on borders
285        assert is_inside_polygon((1., 0.5), polygon, closed=True)
286        assert is_inside_polygon((0.5, 1), polygon, closed=True)
287        assert is_inside_polygon((0., 0.5), polygon, closed=True)
288        assert is_inside_polygon((0.5, 0.), polygon, closed=True)
289
290        assert not is_inside_polygon((0.5, 1), polygon, closed=False)
291        assert not is_inside_polygon((0., 0.5), polygon, closed=False)
292        assert not is_inside_polygon((0.5, 0.), polygon, closed=False)
293        assert not is_inside_polygon((1., 0.5), polygon, closed=False)
294
295        # From real example
296        polygon = [[20,20], [40,20], [40,40], [20,40]]
297        points = [[40, 50]]
298        res = inside_polygon(points, polygon)
299        assert len(res) == 0
300
301    def test_inside_polygon_vector_version(self):
302        # Now try the vector formulation returning indices
303        polygon = [[0,0], [1,0], [0.5,-1], [2, -1], [2,1], [0,1]]
304        points = [[0.5, 0.5], [1, -0.5], [1.5, 0], [0.5, 1.5], [0.5, -0.5]]
305        res = inside_polygon( points, polygon, verbose=False )
306        assert num.allclose(res, [0,1,2])
307
308    def test_outside_polygon(self):
309        # unit square
310        U = [[0,0], [1,0], [1,1], [0,1]]
311
312        # evaluate to False as the point 0.5, 0.5 is inside the unit square
313        assert not is_outside_polygon([0.5, 0.5], U)
314
315        # evaluate to True as the point 1.5, 0.5 is outside the unit square
316        assert is_outside_polygon([1.5, 0.5], U)
317
318        indices = outside_polygon([[0.5, 0.5], [1, -0.5], [0.3, 0.2]], U)
319        assert num.allclose(indices, [1])
320
321        # One more test of vector formulation returning indices
322        polygon = [[0,0], [1,0], [0.5,-1], [2, -1], [2,1], [0,1]]
323        points = [[0.5, 0.5], [1, -0.5], [1.5, 0], [0.5, 1.5], [0.5, -0.5]]
324        res = outside_polygon(points, polygon)
325        assert num.allclose(res, [3, 4])
326
327        polygon = [[0,0], [1,0], [0.5,-1], [2, -1], [2,1], [0,1]]
328        points = [[0.5, 1.4], [0.5, 0.5], [1, -0.5], [1.5, 0],
329                  [0.5, 1.5], [0.5, -0.5]]
330        res = outside_polygon(points, polygon)
331
332        assert num.allclose(res, [0, 4, 5])
333
334    def test_outside_polygon2(self):
335        # unit square
336        U = [[0,0], [1,0], [1,1], [0,1]]
337
338        # evaluate to False as the point 0.5, 1.0 is inside the unit square
339        assert not outside_polygon([0.5, 1.0], U, closed = True)
340
341        # evaluate to True as the point 0.5, 1.0 is outside the unit square
342        assert is_outside_polygon([0.5, 1.0], U, closed = False)
343
344    def test_all_outside_polygon(self):
345        """Test case where all points are outside poly"""
346
347        # unit square
348        U = [[0,0], [1,0], [1,1], [0,1]]
349
350        points = [[2,2], [1,3], [-1,1], [0,2]]      # All outside
351
352        indices, count = separate_points_by_polygon(points, U)
353        assert count == 0                           # None inside
354        assert num.allclose(indices, [3, 2, 1, 0])
355
356        indices = outside_polygon(points, U, closed = True)
357        assert num.allclose(indices, [0, 1, 2, 3])
358
359        indices = inside_polygon(points, U, closed = True)
360        assert num.allclose(indices, [])
361
362    def test_all_inside_polygon(self):
363        """Test case where all points are inside poly"""
364
365        # unit square
366        U = [[0,0], [1,0], [1,1], [0,1]]
367
368        points = [[0.5,0.5], [0.2,0.3], [0,0.5]]    # All inside (or on edge)
369
370        indices, count = separate_points_by_polygon(points, U)
371        assert count == 3       # All inside
372        assert num.allclose(indices, [0, 1, 2])
373
374        indices = outside_polygon(points, U, closed=True)
375        assert num.allclose(indices, [])
376
377        indices = inside_polygon(points, U, closed=True)
378        assert num.allclose(indices, [0, 1, 2])
379
380
381    def test_separate_points_by_polygon(self):
382        # unit square
383        U = [[0,0], [1,0], [1,1], [0,1]]
384
385        indices, count = separate_points_by_polygon([[0.5, 0.5],
386                                                     [1, -0.5],
387                                                     [0.3, 0.2]],
388                                                    U)
389        assert num.allclose( indices, [0, 2, 1] )
390        assert count == 2
391
392        # One more test of vector formulation returning indices
393        polygon = [[0,0], [1,0], [0.5,-1], [2, -1], [2,1], [0,1]]
394        points = [[0.5, 0.5], [1, -0.5], [1.5, 0], [0.5, 1.5], [0.5, -0.5]]
395        res, count = separate_points_by_polygon(points, polygon)
396
397        assert num.allclose(res, [0, 1, 2, 4, 3])
398        assert count == 3
399
400        polygon = [[0,0], [1,0], [0.5,-1], [2, -1], [2,1], [0,1]]
401        points = [ [0.5, 1.4], [0.5, 0.5], [1, -0.5], [1.5, 0], [0.5, 1.5], [0.5, -0.5]]
402        res, count = separate_points_by_polygon( points, polygon )
403
404        assert num.allclose( res, [1,2,3,5,4,0] )
405        assert count == 3
406
407
408    def test_is_inside_triangle(self):
409        # Simplest case:
410        triangle = [[0, 0], [1, 0], [0.5, 1]]
411
412        assert is_inside_triangle((0.5, 0.5), triangle)
413        assert is_inside_triangle((0.9, 0.1), triangle)
414        assert not is_inside_triangle((0.5, 1.5), triangle)
415        assert not is_inside_triangle((0.5, -0.5), triangle)
416        assert not is_inside_triangle((-0.5, 0.5), triangle)
417        assert not is_inside_triangle((1.5, 0.5), triangle)
418
419        # Try point on borders
420        assert is_inside_triangle((0.5, 0), triangle, closed=True)
421        assert is_inside_triangle((1, 0), triangle, closed=True)
422
423        assert not is_inside_triangle((0.5, 0), triangle, closed=False)
424        assert not is_inside_triangle((1, 0), triangle, closed=False)
425
426        # Try vertices
427        for P in triangle:
428            assert is_inside_triangle(P, triangle, closed=True)
429            assert not is_inside_triangle(P, triangle, closed=False)
430
431        # Slightly different
432        triangle = [[0, 0.1], [1, -0.2], [0.5, 1]]
433        assert is_inside_triangle((0.5, 0.5), triangle)
434        assert is_inside_triangle((0.4, 0.1), triangle)
435        assert not is_inside_triangle((1, 1), triangle)
436
437        # Try vertices
438        for P in triangle:
439            assert is_inside_triangle(P, triangle, closed=True)
440            assert not is_inside_triangle(P, triangle, closed=False)
441
442
443    def test_populate_polygon(self):
444        polygon = [[0,0], [1,0], [1,1], [0,1]]
445        points = populate_polygon(polygon, 5)
446
447        assert len(points) == 5
448        for point in points:
449            assert is_inside_polygon(point, polygon)
450
451            assert is_inside_polygon(point, polygon)
452
453
454        # Very convoluted polygon
455        polygon = [[0,0], [10,10], [15,5], [20, 10], [25,0], [30,10], [40,-10]]
456        points = populate_polygon(polygon, 5)
457        assert len(points) == 5
458        for point in points:
459            assert is_inside_polygon(point, polygon)
460            assert is_inside_polygon(point, polygon)
461
462
463    def test_populate_polygon_with_exclude(self):
464        polygon = [[0,0], [1,0], [1,1], [0,1]]
465        ex_poly = [[0,0], [0.5,0], [0.5, 0.5], [0,0.5]]     # SW quarter
466        points = populate_polygon(polygon, 5, exclude=[ex_poly])
467
468        assert len(points) == 5
469        for point in points:
470            assert is_inside_polygon(point, polygon)
471            assert not is_inside_polygon(point, ex_poly)
472
473        # overlap
474        polygon = [[0,0], [1,0], [1,1], [0,1]]
475        ex_poly = [[-1,-1], [0.5,0], [0.5, 0.5], [-1,0.5]]
476        points = populate_polygon(polygon, 5, exclude=[ex_poly])
477
478        assert len(points) == 5
479        for point in points:
480            assert is_inside_polygon(point, polygon)
481            assert not is_inside_polygon(point, ex_poly)
482
483        # Multiple
484        polygon = [[0,0], [1,0], [1,1], [0,1]]
485        ex_poly1 = [[0,0], [0.5,0], [0.5, 0.5], [0,0.5]]    # SW quarter
486        ex_poly2 = [[0.5,0.5], [0.5,1], [1, 1], [1,0.5]]    # NE quarter
487
488        points = populate_polygon(polygon, 20, exclude=[ex_poly1, ex_poly2])
489
490        assert len(points) == 20
491        for point in points:
492            assert is_inside_polygon(point, polygon)
493            assert not is_inside_polygon(point, ex_poly1)
494            assert not is_inside_polygon(point, ex_poly2)
495
496        # Very convoluted polygon
497        polygon = [[0,0], [10,10], [15,5], [20, 10], [25,0], [30,10], [40,-10]]
498        ex_poly = [[-1,-1], [5,0], [5, 5], [-1,5]]
499        points = populate_polygon(polygon, 20, exclude=[ex_poly])
500
501        assert len(points) == 20
502        for point in points:
503            assert is_inside_polygon(point, polygon)
504            assert not is_inside_polygon(point, ex_poly), '%s' % str(point)
505
506    def test_populate_polygon_with_exclude2(self):
507        min_outer = 0
508        max_outer = 1000
509        polygon_outer = [[min_outer,min_outer], [max_outer,min_outer],
510                         [max_outer,max_outer], [min_outer,max_outer]]
511
512        delta = 10
513        min_inner1 = min_outer + delta
514        max_inner1 = max_outer - delta
515        inner1_polygon = [[min_inner1,min_inner1], [max_inner1,min_inner1],
516                          [max_inner1,max_inner1], [min_inner1,max_inner1]]
517
518        density_inner2 = 1000
519        min_inner2 = min_outer + 2*delta
520        max_inner2 = max_outer - 2*delta
521        inner2_polygon = [[min_inner2,min_inner2], [max_inner2,min_inner2],
522                          [max_inner2,max_inner2], [min_inner2,max_inner2]]
523
524        points = populate_polygon(polygon_outer, 20,
525                                  exclude=[inner1_polygon, inner2_polygon])
526
527        assert len(points) == 20
528        for point in points:
529            assert is_inside_polygon(point, polygon_outer)
530            assert not is_inside_polygon(point, inner1_polygon)
531            assert not is_inside_polygon(point, inner2_polygon)
532
533        # Very convoluted polygon
534        polygon = [[0,0], [10,10], [15,5], [20, 10], [25,0], [30,10], [40,-10]]
535        ex_poly = [[-1,-1], [5,0], [5, 5], [-1,5]]
536        points = populate_polygon(polygon, 20, exclude=[ex_poly])
537
538        assert len(points) == 20
539        for point in points:
540            assert is_inside_polygon(point, polygon)
541            assert not is_inside_polygon(point, ex_poly), '%s' % str(point)
542
543    def test_point_in_polygon(self):
544        polygon = [[0,0], [1,0], [1,1], [0,1]]
545        point = point_in_polygon(polygon)
546        assert is_inside_polygon(point, polygon)
547
548        # this may get into a vicious loop
549        # polygon = [[1e32,1e54], [1,0], [1,1], [0,1]]
550
551        polygon = [[1e15,1e7], [1,0], [1,1], [0,1]]
552        point = point_in_polygon(polygon)
553        assert is_inside_polygon(point, polygon)
554
555        polygon = [[0,0], [1,0], [1,1], [1e8,1e8]]
556        point = point_in_polygon(polygon)
557        assert is_inside_polygon(point, polygon)
558
559        polygon = [[1e32,1e54], [-1e32,1e54], [1e32,-1e54]]
560        point = point_in_polygon(polygon)
561        assert is_inside_polygon(point, polygon)
562
563        polygon = [[1e18,1e15], [1,0], [0,1]]
564        point = point_in_polygon(polygon)
565        assert is_inside_polygon(point, polygon)
566
567    def test_in_and_outside_polygon_main(self):
568        # Simplest case: Polygon is the unit square
569        polygon = [[0,0], [1,0], [1,1], [0,1]]
570
571        inside, outside = in_and_outside_polygon((0.5, 0.5), polygon)
572        assert inside[0] == 0
573        assert len(outside) == 0
574
575        inside, outside = in_and_outside_polygon((1., 0.5), polygon,
576                                                 closed=True)
577        assert inside[0] == 0
578        assert len(outside) == 0
579
580        inside, outside = in_and_outside_polygon((1., 0.5), polygon,
581                                                 closed=False)
582        assert len(inside) == 0
583        assert outside[0] == 0
584
585        points = [(1., 0.25),(1., 0.75)]
586        inside, outside = in_and_outside_polygon(points, polygon, closed=True)
587        assert num.alltrue(inside == [0,1])
588        assert len(outside) == 0
589
590        inside, outside = in_and_outside_polygon(points, polygon, closed=False)
591        assert len(inside) == 0
592        assert num.alltrue(outside == [0,1])
593
594        points = [(100., 0.25), (0.5, 0.5) ]
595        inside, outside = in_and_outside_polygon(points, polygon)
596        assert num.alltrue(inside == [1])
597        assert outside[0] == 0
598
599        points = [(100., 0.25),(0.5, 0.5), (39,20), (0.6,0.7),(56,43),(67,90)]
600        inside, outside = in_and_outside_polygon(points, polygon)
601        assert num.alltrue(inside == [1, 3])
602        assert num.alltrue(outside == [0, 2, 4, 5])
603
604    def test_intersection1(self):
605        line0 = [[-1,0], [1,0]]
606        line1 = [[0,-1], [0,1]]
607
608        status, value = intersection(line0, line1)
609        assert status == 1
610        assert num.allclose(value, [0.0, 0.0])
611
612    def test_intersection2(self):
613        line0 = [[0,0], [24,12]]
614        line1 = [[0,12], [24,0]]
615
616        status, value = intersection(line0, line1)
617        assert status == 1
618        assert num.allclose(value, [12.0, 6.0])
619
620        # Swap direction of one line
621        line1 = [[24,0], [0,12]]
622
623        status, value = intersection(line0, line1)
624        assert status == 1
625        assert num.allclose(value, [12.0, 6.0])
626
627        # Swap order of lines
628        status, value = intersection(line1, line0)
629        assert status == 1
630        assert num.allclose(value, [12.0, 6.0])
631
632    def test_intersection3(self):
633        line0 = [[0,0], [24,12]]
634        line1 = [[0,17], [24,0]]
635
636        status, value = intersection(line0, line1)
637        assert status == 1
638        assert num.allclose(value, [14.068965517, 7.0344827586])
639
640        # Swap direction of one line
641        line1 = [[24,0], [0,17]]
642
643        status, value = intersection(line0, line1)
644        assert status == 1
645        assert num.allclose(value, [14.068965517, 7.0344827586])
646
647        # Swap order of lines
648        status, value = intersection(line1, line0)
649        assert status == 1
650        assert num.allclose(value, [14.068965517, 7.0344827586])
651
652    def test_intersection_endpoints(self):
653        """test_intersection_endpoints(self):
654
655        Test that coinciding endpoints are picked up
656        """
657
658        line0 = [[0,0], [1,1]]
659        line1 = [[1,1], [2,1]]
660
661        status, value = intersection(line0, line1)
662        assert status == 1
663        assert num.allclose(value, [1.0, 1.0])
664
665        line0 = [[1,1], [2,0]]
666        line1 = [[1,1], [2,1]]
667
668        status, value = intersection(line0, line1)
669        assert status == 1
670        assert num.allclose(value, [1.0, 1.0])
671
672    # This function is a helper function for
673    # the test_intersection_bug_20081110_?() set of tests.
674    # This function tests all parallel line cases for 4 collinear points.
675    # This function should never be run directly by the unittest code.
676    def helper_test_parallel_intersection_code(self, P1, P2, P3, P4):
677        # lines in same direction, no overlap
678        # 0:         ---->----
679        # 1:                     --------->-----------
680        line0 = [P1, P2]
681        line1 = [P3, P4]
682        status, value = intersection(line0, line1)
683        self.failIf(status!=3, 'Expected status 3, got status=%s, value=%s' %
684                               (str(status), str(value)))
685        self.failUnless(value is None, 'Expected value of None, got %s' %
686                                       str(value))
687
688        # lines in same direction, no overlap
689        # 0:         ----<----
690        # 1:                     ---------<-----------
691        line0 = [P2, P1]
692        line1 = [P4, P3]
693        status, value = intersection(line0, line1)
694        self.failIf(status!=3, 'Expected status 3, got status=%s, value=%s' %
695                               (str(status), str(value)))
696        self.failUnless(value is None, 'Expected value of None, got %s' %
697                                       str(value))
698
699        # lines in opposite direction, no overlap
700        # 0:         ----<----
701        # 1:                     --------->-----------
702        line0 = [P2, P1]
703        line1 = [P3, P4]
704        status, value = intersection(line0, line1)
705        self.failIf(status!=3, 'Expected status 3, got status=%s, value=%s' %
706                               (str(status), str(value)))
707        self.failUnless(value is None, 'Expected value of None, got %s' %
708                                       str(value))
709
710        # lines in opposite direction, no overlap
711        # 0:         ---->----
712        # 1:                     ---------<-----------
713        line0 = [P1, P2]
714        line1 = [P4, P3]
715        status, value = intersection(line0, line1)
716        self.failIf(status!=3, 'Expected status 3, got status=%s, value=%s' %
717                               (str(status), str(value)))
718        self.failUnless(value is None, 'Expected value of None, got %s' %
719                                       str(value))
720
721        # ----------------------------------------------------------------------
722
723        # line0 fully within line1, same direction
724        # 0:         ---->----
725        # 1:    --------->-----------
726        # value should be line0:
727        #            ---->----
728        line0 = [P2, P3]
729        line1 = [P1, P4]
730        status, value = intersection(line0, line1)
731        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
732                               (str(status), str(value)))
733        self.failUnless(num.allclose(value, line0))
734
735        # line0 fully within line1, same direction
736        # 0:         ----<----
737        # 1:    ---------<-----------
738        # value should be line0:
739        #            ----<----
740        line0 = [P3, P2]
741        line1 = [P4, P1]
742        status, value = intersection(line0, line1)
743        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
744                               (str(status), str(value)))
745        self.failUnless(num.allclose(value, line0))
746
747        # line0 fully within line1, opposite direction
748        # 0:         ----<----
749        # 1:    --------->-----------
750        # value should be line0:
751        #            ----<----
752        line0 = [P3, P2]
753        line1 = [P1, P4]
754        status, value = intersection(line0, line1)
755        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
756                               (str(status), str(value)))
757        self.failUnless(num.allclose(value, line0))
758
759        # line0 fully within line1, opposite direction
760        # 0:         ---->----
761        # 1:    ---------<-----------
762        # value should be line0:
763        #            ---->----
764        line0 = [P2, P3]
765        line1 = [P4, P1]
766        status, value = intersection(line0, line1)
767        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
768                               (str(status), str(value)))
769        self.failUnless(num.allclose(value, line0))
770
771        # ----------------------------------------------------------------------
772
773        # line1 fully within line0, same direction
774        # 0:    --------->-----------
775        # 1:         ---->----
776        # value should be line1:
777        #            ---->----
778        line0 = [P1, P4]
779        line1 = [P2, P3]
780        status, value = intersection(line0, line1)
781        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
782                               (str(status), str(value)))
783        self.failUnless(num.allclose(value, line1))
784
785        # line1 fully within line0, same direction
786        # 0:    ---------<-----------
787        # 1:         ----<----
788        # value should be line1:
789        #            ----<----
790        line0 = [P4, P1]
791        line1 = [P3, P2]
792        status, value = intersection(line0, line1)
793        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
794                               (str(status), str(value)))
795        self.failUnless(num.allclose(value, line1))
796
797        # line1 fully within line0, opposite direction
798        # 0:    ---------<-----------
799        # 1:         ---->----
800        # value should be line1:
801        #            ---->----
802        line0 = [P4, P1]
803        line1 = [P2, P3]
804        status, value = intersection(line0, line1)
805        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
806                               (str(status), str(value)))
807        self.failUnless(num.allclose(value, line1))
808
809        # line1 fully within line0, opposite direction
810        # 0:    --------->-----------
811        # 1:         ----<----
812        # value should be line1:
813        #            ----<----
814        line0 = [P1, P4]
815        line1 = [P3, P2]
816        status, value = intersection(line0, line1)
817        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
818                               (str(status), str(value)))
819        self.failUnless(num.allclose(value, line1))
820
821        # ----------------------------------------------------------------------
822
823        # line in same direction, partial overlap
824        # 0:    ----->-----
825        # 1:       ------->--------
826        # value should be segment line1_start->line0_end:
827        #          --->----
828        line0 = [P1, P3]
829        line1 = [P2, P4]
830        status, value = intersection(line0, line1)
831        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
832                               (str(status), str(value)))
833        self.failUnless(num.allclose(value, [line1[0],line0[1]]))
834
835        # line in same direction, partial overlap
836        # 0:    -----<-----
837        # 1:       -------<--------
838        # value should be segment line0_start->line1_end:
839        #          ---<----
840        line0 = [P3, P1]
841        line1 = [P4, P2]
842        status, value = intersection(line0, line1)
843        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
844                               (str(status), str(value)))
845        self.failUnless(num.allclose(value, [line0[0],line1[1]]))
846
847        # line in opposite direction, partial overlap
848        # 0:    -----<-----
849        # 1:       ------->--------
850        # value should be segment line0_start->line1_start:
851        #          ---<----
852        line0 = [P3, P1]
853        line1 = [P2, P4]
854        status, value = intersection(line0, line1)
855        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
856                               (str(status), str(value)))
857        self.failUnless(num.allclose(value, [line0[0],line1[0]]))
858
859        # line in opposite direction, partial overlap
860        # 0:    ----->-----
861        # 1:       -------<--------
862        # value should be segment line1_end->line0_end:
863        #          --->----
864        line0 = [P1, P3]
865        line1 = [P4, P2]
866        status, value = intersection(line0, line1)
867        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
868                               (str(status), str(value)))
869        self.failUnless(num.allclose(value, [line1[1],line0[1]]))
870
871        # ----------------------------------------------------------------------
872
873        # line in same direction, partial overlap
874        # 0:       ------>------
875        # 1:    ------>------
876        # value should be segment line0_start->line1_end:
877        #          --->----
878        line0 = [P2, P4]
879        line1 = [P1, P3]
880        status, value = intersection(line0, line1)
881        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
882                               (str(status), str(value)))
883        self.failUnless(num.allclose(value, [line0[0],line1[1]]))
884
885        # line in same direction, partial overlap
886        # 0:       ------<------
887        # 1:    ------<------
888        # value should be segment line1_start->line0_end:
889        #          ----<-----
890        line0 = [P4, P2]
891        line1 = [P3, P1]
892        status, value = intersection(line0, line1)
893        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
894                               (str(status), str(value)))
895        self.failUnless(num.allclose(value, [line1[0],line0[1]]))
896
897        # line in opposite direction, partial overlap
898        # 0:       ------<------
899        # 1:    ----->------
900        # value should be segment line1_end->line0_end:
901        #          --->----
902        line0 = [P4, P2]
903        line1 = [P1, P3]
904        status, value = intersection(line0, line1)
905        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
906                               (str(status), str(value)))
907        self.failUnless(num.allclose(value, [line1[1],line0[1]]))
908
909        # line in opposite direction, partial overlap
910        # 0:       ------>------
911        # 1:    -----<------
912        # value should be segment line0_start->line1_start:
913        #          ---<----
914        line0 = [P2, P4]
915        line1 = [P3, P1]
916        status, value = intersection(line0, line1)
917        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
918                               (str(status), str(value)))
919        self.failUnless(num.allclose(value, [line0[0],line1[0]]))
920
921        # ----------------------------------------------------------------------
922
923        # line in same direction, same left point, line1 longer
924        # 0:    ----->------
925        # 1:    ------->--------
926        # value should be line0:
927        #       ----->------
928        line0 = [P1, P3]
929        line1 = [P1, P4]
930        status, value = intersection(line0, line1)
931        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
932                               (str(status), str(value)))
933        self.failUnless(num.allclose(value, line0))
934
935        # line in same direction, same left point, line1 longer
936        # 0:    -----<------
937        # 1:    -------<--------
938        # value should be line0:
939        #       -----<------
940        line0 = [P3, P1]
941        line1 = [P4, P1]
942        status, value = intersection(line0, line1)
943        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
944                               (str(status), str(value)))
945        self.failUnless(num.allclose(value, line0))
946
947        # line in opposite direction, same left point, line1 longer
948        # 0:    ----->------
949        # 1:    -------<--------
950        # value should be line0:
951        #       ----->------
952        line0 = [P1, P3]
953        line1 = [P4, P1]
954        status, value = intersection(line0, line1)
955        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
956                               (str(status), str(value)))
957        self.failUnless(num.allclose(value, line0))
958
959        # line in opposite direction, same start point, line1 longer
960        # 0:    -----<------
961        # 1:    ------->--------
962        # value should be line0:
963        #       -----<------
964        line0 = [P3, P1]
965        line1 = [P1, P4]
966        status, value = intersection(line0, line1)
967        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
968                               (str(status), str(value)))
969        self.failUnless(num.allclose(value, line0))
970
971        # ----------------------------------------------------------------------
972
973        # line in same direction, same left point, same right point
974        # 0:    ------->--------
975        # 1:    ------->--------
976        # value should be line0 or line1:
977        #       ------->--------
978        line0 = [P1, P3]
979        line1 = [P1, P3]
980        status, value = intersection(line0, line1)
981        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
982                               (str(status), str(value)))
983        self.failUnless(num.allclose(value, line0))
984
985        # line in same direction, same left point, same right point
986        # 0:    -------<--------
987        # 1:    -------<--------
988        # value should be line0 (or line1):
989        #       -------<--------
990        line0 = [P3, P1]
991        line1 = [P3, P1]
992        status, value = intersection(line0, line1)
993        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
994                               (str(status), str(value)))
995        self.failUnless(num.allclose(value, line0))
996
997        # line in opposite direction, same left point, same right point
998        # 0:    ------->--------
999        # 1:    -------<--------
1000        # value should be line0:
1001        #       ------->--------
1002        line0 = [P1, P3]
1003        line1 = [P3, P1]
1004        status, value = intersection(line0, line1)
1005        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1006                               (str(status), str(value)))
1007        self.failUnless(num.allclose(value, line0))
1008
1009        # line in opposite direction, same left point, same right point
1010        # 0:    -------<--------
1011        # 1:    ------->--------
1012        # value should be line0:
1013        #       -------<--------
1014        line0 = [P3, P1]
1015        line1 = [P1, P3]
1016        status, value = intersection(line0, line1)
1017        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1018                               (str(status), str(value)))
1019        self.failUnless(num.allclose(value, line0))
1020
1021        # ----------------------------------------------------------------------
1022
1023        # line in same direction, same right point, line1 longer
1024        # 0:        ----->------
1025        # 1:    ------->--------
1026        # value should be line0:
1027        #           ----->------
1028        line0 = [P2, P4]
1029        line1 = [P1, P4]
1030        status, value = intersection(line0, line1)
1031        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1032                               (str(status), str(value)))
1033        self.failUnless(num.allclose(value, line0))
1034
1035        # line in same direction, same right point, line1 longer
1036        # 0:        -----<------
1037        # 1:    -------<--------
1038        # value should be line0:
1039        #           -----<------
1040        line0 = [P4, P2]
1041        line1 = [P4, P1]
1042        status, value = intersection(line0, line1)
1043        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1044                               (str(status), str(value)))
1045        self.failUnless(num.allclose(value, line0))
1046
1047        # line in opposite direction, same right point, line1 longer
1048        # 0:        ----->------
1049        # 1:    -------<--------
1050        # value should be line0:
1051        #           ----->------
1052        line0 = [P2, P4]
1053        line1 = [P4, P1]
1054        status, value = intersection(line0, line1)
1055        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1056                               (str(status), str(value)))
1057        self.failUnless(num.allclose(value, line0))
1058
1059        # line in opposite direction, same right point, line1 longer
1060        # 0:        -----<------
1061        # 1:    ------->--------
1062        # value should be line0:
1063        #           -----<------
1064        line0 = [P4, P2]
1065        line1 = [P1, P4]
1066        status, value = intersection(line0, line1)
1067        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1068                               (str(status), str(value)))
1069        self.failUnless(num.allclose(value, line0))
1070
1071        # ----------------------------------------------------------------------
1072
1073        # line in same direction, same left point, line0 longer
1074        # 0:    ------->--------
1075        # 1:    ----->------
1076        # value should be line1:
1077        #       ----->------
1078        line0 = [P1, P4]
1079        line1 = [P1, P3]
1080        status, value = intersection(line0, line1)
1081        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1082                               (str(status), str(value)))
1083        self.failUnless(num.allclose(value, line1))
1084
1085        # line in same direction, same left point, line0 longer
1086        # 0:    -------<--------
1087        # 1:    -----<------
1088        # value should be line1:
1089        #       -----<------
1090        line0 = [P4, P1]
1091        line1 = [P3, P1]
1092        status, value = intersection(line0, line1)
1093        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1094                               (str(status), str(value)))
1095        self.failUnless(num.allclose(value, line1))
1096
1097        # line in opposite direction, same left point, line0 longer
1098        # 0:    ------->--------
1099        # 1:    -----<------
1100        # value should be line1:
1101        #       -----<------
1102        line0 = [P1, P4]
1103        line1 = [P3, P1]
1104        status, value = intersection(line0, line1)
1105        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1106                               (str(status), str(value)))
1107        self.failUnless(num.allclose(value, line1))
1108
1109        # line in opposite direction, same left point, line0 longer
1110        # 0:    -------<--------
1111        # 1:    ----->------
1112        # value should be line1:
1113        #       ----->------
1114        line0 = [P4, P1]
1115        line1 = [P1, P3]
1116        status, value = intersection(line0, line1)
1117        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1118                               (str(status), str(value)))
1119        self.failUnless(num.allclose(value, line1))
1120
1121        # ----------------------------------------------------------------------
1122
1123        # line in same direction, same right point, line0 longer
1124        # 0:    ------->--------
1125        # 1:        ----->------
1126        # value should be line1:
1127        #           ----->------
1128        line0 = [P1, P4]
1129        line1 = [P2, P4]
1130        status, value = intersection(line0, line1)
1131        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1132                               (str(status), str(value)))
1133        self.failUnless(num.allclose(value, line1))
1134
1135        # line in same direction, same right point, line0 longer
1136        # 0:    -------<--------
1137        # 1:        -----<------
1138        # value should be line1:
1139        #           -----<------
1140        line0 = [P4, P1]
1141        line1 = [P4, P2]
1142        status, value = intersection(line0, line1)
1143        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1144                               (str(status), str(value)))
1145        self.failUnless(num.allclose(value, line1))
1146
1147        # line in opposite direction, same right point, line0 longer
1148        # 0:    ------->--------
1149        # 1:        -----<------
1150        # value should be line1:
1151        #           -----<------
1152        line0 = [P1, P4]
1153        line1 = [P4, P2]
1154        status, value = intersection(line0, line1)
1155        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1156                               (str(status), str(value)))
1157        self.failUnless(num.allclose(value, line1))
1158
1159        # line in opposite direction, same right point, line0 longer
1160        # 0:    -------<--------
1161        # 1:        ----->------
1162        # value should be line1:
1163        #           ----->------
1164        line0 = [P4, P1]
1165        line1 = [P2, P4]
1166        status, value = intersection(line0, line1)
1167        self.failIf(status!=2, 'Expected status 2, got status=%s, value=%s' %
1168                               (str(status), str(value)))
1169        self.failUnless(num.allclose(value, line1))
1170
1171
1172    def test_intersection_bug_20081110_TR(self):
1173        """test_intersection_bug_20081110(self)
1174
1175        Test all cases in top-right quadrant
1176        """
1177
1178        # define 4 collinear points in top-right quadrant
1179        #    P1---P2---P3---P4
1180        P1 = [1.0, 1.0]
1181        P2 = [2.0, 2.0]
1182        P3 = [3.0, 3.0]
1183        P4 = [4.0, 4.0]
1184
1185        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1186        P1 = [1.0, 1.0+1.0e-9]
1187        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1188        P1 = [1.0, 1.0]
1189        P2 = [2.0, 2.0+1.0e-9]
1190        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1191        P2 = [2.0, 2.0]
1192        P3 = [3.0, 3.0+1.0e-9]
1193        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1194        P3 = [3.0, 3.0]
1195        P4 = [4.0, 4.0+1.0e-9]
1196        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1197
1198    def test_intersection_bug_20081110_TL(self):
1199        """test_intersection_bug_20081110(self)
1200
1201        Test all cases in top-left quadrant
1202        """
1203
1204        # define 4 collinear points in top-left quadrant
1205        #    P1---P2---P3---P4
1206        P1 = [-1.0, 1.0]
1207        P2 = [-2.0, 2.0]
1208        P3 = [-3.0, 3.0]
1209        P4 = [-4.0, 4.0]
1210
1211        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1212        P1 = [-1.0, 1.0+1.0e-9]
1213        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1214        P1 = [-1.0, 1.0]
1215        P2 = [-2.0, 2.0+1.0e-9]
1216        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1217        P2 = [-2.0, 2.0]
1218        P3 = [-3.0, 3.0+1.0e-9]
1219        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1220        P3 = [-3.0, 3.0]
1221        P4 = [-4.0, 4.0+1.0e-9]
1222        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1223
1224    def test_intersection_bug_20081110_BL(self):
1225        """test_intersection_bug_20081110(self)
1226
1227        Test all cases in bottom-left quadrant
1228        """
1229
1230        # define 4 collinear points in bottom-left quadrant
1231        #    P1---P2---P3---P4
1232        P1 = [-1.0, -1.0]
1233        P2 = [-2.0, -2.0]
1234        P3 = [-3.0, -3.0]
1235        P4 = [-4.0, -4.0]
1236
1237        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1238        P1 = [-1.0, -1.0+1.0e-9]
1239        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1240        P1 = [-1.0, -1.0]
1241        P2 = [-2.0, -2.0+1.0e-9]
1242        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1243        P2 = [-2.0, -2.0]
1244        P3 = [-3.0, -3.0+1.0e-9]
1245        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1246        P3 = [-3.0, -3.0]
1247        P4 = [-4.0, -4.0+1.0e-9]
1248        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1249
1250    def test_intersection_bug_20081110_BR(self):
1251        """test_intersection_bug_20081110(self)
1252
1253        Test all cases in bottom-right quadrant
1254        """
1255
1256        # define 4 collinear points in bottom-right quadrant
1257        #    P1---P2---P3---P4
1258        P1 = [1.0, -1.0]
1259        P2 = [2.0, -2.0]
1260        P3 = [3.0, -3.0]
1261        P4 = [4.0, -4.0]
1262
1263        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1264        P1 = [1.0, -1.0+1.0e-9]
1265        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1266        P1 = [1.0, -1.0]
1267        P2 = [2.0, -2.0+1.0e-9]
1268        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1269        P2 = [2.0, -2.0]
1270        P3 = [3.0, -3.0+1.0e-9]
1271        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1272        P3 = [3.0, -3.0]
1273        P4 = [4.0, -4.0+1.0e-9]
1274        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1275
1276    def test_intersection_bug_20081110_TR_TL(self):
1277        """test_intersection_bug_20081110(self)
1278
1279        Test all cases in top-right & top-left quadrant
1280        """
1281
1282        # define 4 collinear points, 1 in TL, 3 in TR
1283        #    P1-+-P2---P3---P4
1284        P1 = [-3.0, 1.0]
1285        P2 = [ 1.0, 5.0]
1286        P3 = [ 2.0, 6.0]
1287        P4 = [ 3.0, 7.0]
1288        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1289
1290        # define 4 collinear points, 2 in TL, 2 in TR
1291        #    P1---P2-+-P3---P4
1292        P1 = [-3.0, 1.0]
1293        P2 = [-2.0, 2.0]
1294        P3 = [ 2.0, 6.0]
1295        P4 = [ 3.0, 7.0]
1296        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1297
1298        # define 4 collinear points, 3 in TL, 1 in TR
1299        #    P1---P2---P3-+-P4
1300        P1 = [-3.0, 1.0]
1301        P2 = [-2.0, 2.0]
1302        P3 = [-1.0, 3.0]
1303        P4 = [ 3.0, 7.0]
1304        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1305
1306    def test_intersection_bug_20081110_TR_BL(self):
1307        """test_intersection_bug_20081110(self)
1308
1309        Test all cases in top-right & bottom-left quadrant
1310        """
1311
1312        # define 4 collinear points, 1 in BL, 3 in TR
1313        #    P1-+-P2---P3---P4
1314        P1 = [-4.0, -3.0]
1315        P2 = [ 1.0,  2.0]
1316        P3 = [ 2.0,  3.0]
1317        P4 = [ 3.0,  4.0]
1318        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1319
1320        # define 4 collinear points, 2 in TL, 2 in TR
1321        #    P1---P2-+-P3---P4
1322        P1 = [-4.0, -3.0]
1323        P2 = [-3.0, -2.0]
1324        P3 = [ 2.0,  3.0]
1325        P4 = [ 3.0,  4.0]
1326        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1327
1328        # define 4 collinear points, 3 in TL, 1 in TR
1329        #    P1---P2---P3-+-P4
1330        P1 = [-4.0, -3.0]
1331        P2 = [-3.0, -2.0]
1332        P3 = [-2.0, -1.0]
1333        P4 = [ 3.0,  4.0]
1334        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1335
1336    def test_intersection_bug_20081110_TR_BR(self):
1337        """test_intersection_bug_20081110(self)
1338
1339        Test all cases in top-right & bottom-right quadrant
1340        """
1341
1342        # define 4 collinear points, 1 in BR, 3 in TR
1343        #    P1-+-P2---P3---P4
1344        P1 = [ 1.0, -3.0]
1345        P2 = [ 5.0,  1.0]
1346        P3 = [ 6.0,  2.0]
1347        P4 = [ 7.0,  3.0]
1348        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1349
1350        # define 4 collinear points, 2 in BR, 2 in TR
1351        #    P1---P2-+-P3---P4
1352        P1 = [ 1.0, -3.0]
1353        P2 = [ 2.0, -2.0]
1354        P3 = [ 6.0,  2.0]
1355        P4 = [ 7.0,  3.0]
1356        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1357
1358        # define 4 collinear points, 3 in BR, 1 in TR
1359        #    P1---P2---P3-+-P4
1360        P1 = [ 1.0, -3.0]
1361        P2 = [ 2.0, -2.0]
1362        P3 = [ 3.0, -1.0]
1363        P4 = [ 7.0,  3.0]
1364        self.helper_test_parallel_intersection_code(P1, P2, P3, P4)
1365
1366
1367    def test_intersection_direction_invariance(self):
1368        """This runs through a number of examples and checks that
1369        direction of lines don't matter.
1370        """
1371
1372        line0 = [[0,0], [100,100]]
1373
1374        common_end_point = [20, 150]
1375
1376        for i in range(100):
1377            x = 20 + i * 1.0/100
1378
1379            line1 = [[x,0], common_end_point]
1380            status, p1 = intersection(line0, line1)
1381            assert status == 1
1382
1383            # Swap direction of line1
1384            line1 = [common_end_point, [x,0]]
1385            status, p2 = intersection(line0, line1)
1386            assert status == 1
1387
1388            msg = ('Orientation of line should not matter.\n'
1389                   'However, segment [%f,%f], [%f, %f]' %
1390                   (x, 0, common_end_point[0], common_end_point[1]))
1391            msg += ' gave %s, \nbut when reversed we got %s' % (p1, p2)
1392            assert num.allclose(p1, p2), msg
1393
1394            # Swap order of lines
1395            status, p3 = intersection(line1, line0)
1396            assert status == 1
1397            msg = 'Order of lines gave different results'
1398            assert num.allclose(p1, p3), msg
1399
1400    def test_no_intersection(self):
1401        line0 = [[-1,1], [1,1]]
1402        line1 = [[0,-1], [0,0]]
1403
1404        status, value = intersection(line0, line1)
1405        assert status == 0
1406        assert value is None
1407
1408    def test_intersection_parallel(self):
1409        line0 = [[-1,1], [1,1]]
1410        line1 = [[-1,0], [5,0]]
1411
1412        status, value = intersection(line0, line1)
1413        assert status == 4
1414        assert value is None
1415
1416        line0 = [[0,0], [10,100]]
1417        line1 = [[-10,5], [0,105]]
1418
1419        status, value = intersection(line0, line1)
1420        assert status == 4
1421        assert value is None
1422
1423    def test_intersection_coincide(self):
1424        """Test what happens when two lines partly coincide"""
1425
1426        # Overlap 1
1427        line0 = [[0,0], [5,0]]
1428        line1 = [[-3,0], [3,0]]
1429
1430        status, value = intersection(line0, line1)
1431        assert status == 2
1432        assert num.allclose(value, [[0,0], [3,0]])
1433
1434        # Overlap 2
1435        line0 = [[-10,0], [5,0]]
1436        line1 = [[-3,0], [10,0]]
1437
1438        status, value = intersection(line0, line1)
1439        assert status == 2
1440        assert num.allclose(value, [[-3, 0], [5,0]])
1441
1442        # Inclusion 1
1443        line0 = [[0,0], [5,0]]
1444        line1 = [[2,0], [3,0]]
1445
1446        status, value = intersection(line0, line1)
1447        assert status == 2
1448        assert num.allclose(value, line1)
1449
1450        # Inclusion 2
1451        line0 = [[1,0], [5,0]]
1452        line1 = [[-10,0], [15,0]]
1453
1454        status, value = intersection(line0, line1)
1455        assert status == 2
1456        assert num.allclose(value, line0)
1457
1458        # Exclusion (no intersection)
1459        line0 = [[-10,0], [1,0]]
1460        line1 = [[3,0], [15,0]]
1461
1462        status, value = intersection(line0, line1)
1463        assert status == 3
1464        assert value is None
1465
1466        # Try examples with some slope (y=2*x+5)
1467
1468        # Overlap
1469        line0 = [[0,5], [7,19]]
1470        line1 = [[1,7], [10,25]]
1471        status, value = intersection(line0, line1)
1472        assert status == 2
1473        assert num.allclose(value, [[1, 7], [7, 19]])
1474
1475        status, value = intersection(line1, line0)
1476        assert status == 2
1477        assert num.allclose(value, [[1, 7], [7, 19]])
1478
1479        # Swap direction
1480        line0 = [[7,19], [0,5]]
1481        line1 = [[1,7], [10,25]]
1482        status, value = intersection(line0, line1)
1483        assert status == 2
1484        assert num.allclose(value, [[7, 19], [1, 7]])
1485
1486        line0 = [[0,5], [7,19]]
1487        line1 = [[10,25], [1,7]]
1488        status, value = intersection(line0, line1)
1489        assert status == 2
1490        assert num.allclose(value, [[1, 7], [7, 19]])
1491
1492        # Inclusion
1493        line0 = [[1,7], [7,19]]
1494        line1 = [[0,5], [10,25]]
1495        status, value = intersection(line0, line1)
1496        assert status == 2
1497        assert num.allclose(value, [[1,7], [7, 19]])
1498
1499        line0 = [[0,5], [10,25]]
1500        line1 = [[1,7], [7,19]]
1501        status, value = intersection(line0, line1)
1502        assert status == 2
1503        assert num.allclose(value, [[1,7], [7, 19]])
1504
1505        line0 = [[0,5], [10,25]]
1506        line1 = [[7,19], [1,7]]
1507        status, value = intersection(line0, line1)
1508        assert status == 2
1509        assert num.allclose(value, [[7, 19], [1, 7]])
1510
1511
1512    def NOtest_inside_polygon_main(self):
1513        # FIXME (Ole): Why is this disabled?
1514        #print "inside",inside
1515        #print "outside",outside
1516
1517        assert not inside_polygon((0.5, 1.5), polygon)
1518        assert not inside_polygon((0.5, -0.5), polygon)
1519        assert not inside_polygon((-0.5, 0.5), polygon)
1520        assert not inside_polygon((1.5, 0.5), polygon)
1521
1522        # Try point on borders
1523        assert inside_polygon((1., 0.5), polygon, closed=True)
1524        assert inside_polygon((0.5, 1), polygon, closed=True)
1525        assert inside_polygon((0., 0.5), polygon, closed=True)
1526        assert inside_polygon((0.5, 0.), polygon, closed=True)
1527
1528        assert not inside_polygon((0.5, 1), polygon, closed=False)
1529        assert not inside_polygon((0., 0.5), polygon, closed=False)
1530        assert not inside_polygon((0.5, 0.), polygon, closed=False)
1531        assert not inside_polygon((1., 0.5), polygon, closed=False)
1532
1533        # From real example (that failed)
1534        polygon = [[20,20], [40,20], [40,40], [20,40]]
1535        points = [[40, 50]]
1536        res = inside_polygon(points, polygon)
1537        assert len(res) == 0
1538
1539        polygon = [[20,20], [40,20], [40,40], [20,40]]
1540        points = [[25, 25], [30, 20], [40, 50], [90, 20], [40, 90]]
1541        res = inside_polygon(points, polygon)
1542        assert len(res) == 2
1543        assert num.allclose(res, [0,1])
1544
1545    def test_polygon_area(self):
1546        # Simplest case: Polygon is the unit square
1547        polygon = [[0,0], [1,0], [1,1], [0,1]]
1548        assert polygon_area(polygon) == 1
1549
1550        # Simple case: Polygon is a rectangle
1551        polygon = [[0,0], [1,0], [1,4], [0,4]]
1552        assert polygon_area(polygon) == 4
1553
1554        # Simple case: Polygon is a unit triangle
1555        polygon = [[0,0], [1,0], [0,1]]
1556        assert polygon_area(polygon) == 0.5
1557
1558        # Simple case: Polygon is a diamond
1559        polygon = [[0,0], [1,1], [2,0], [1, -1]]
1560        assert polygon_area(polygon) == 2.0
1561
1562        # Complex case where numerical errors might occur
1563        polygon = [[314037.58727982, 6224952.2960092],
1564                   [314038.58727982, 6224952.2960092],
1565                   [314038.58727982, 6224953.2960092],
1566                   [314037.58727982, 6224953.2960092]]
1567        assert polygon_area(polygon) == 1.0
1568
1569    def test_poly_xy(self):
1570        # Simplest case: Polygon is the unit square
1571        polygon = [[0,0], [1,0], [1,1], [0,1]]
1572        x, y = poly_xy(polygon)
1573        assert len(x) == len(polygon)+1
1574        assert len(y) == len(polygon)+1
1575        assert x[0] == 0
1576        assert x[1] == 1
1577        assert x[2] == 1
1578        assert x[3] == 0
1579        assert y[0] == 0
1580        assert y[1] == 0
1581        assert y[2] == 1
1582        assert y[3] == 1
1583
1584    # Arbitrary polygon
1585        polygon = [[1,5], [1,1], [100,10], [1,10], [3,6]]
1586        x, y = poly_xy(polygon)
1587        assert len(x) == len(polygon)+1
1588        assert len(y) == len(polygon)+1
1589        assert x[0] == 1
1590        assert x[1] == 1
1591        assert x[2] == 100
1592        assert x[3] == 1
1593        assert x[4] == 3
1594        assert y[0] == 5
1595        assert y[1] == 1
1596        assert y[2] == 10
1597        assert y[3] == 10
1598        assert y[4] == 6
1599
1600
1601    def test_plot_polygons(self):
1602        import os
1603
1604        # Simplest case: Polygon is the unit square
1605        polygon1 = [[0,0], [1,0], [1,1], [0,1]]
1606        polygon2 = [[1,1], [2,1], [3,2], [2,2]]
1607        v = plot_polygons([polygon1, polygon2], figname='test1')
1608        assert len(v) == 4
1609        assert v[0] == 0
1610        assert v[1] == 3
1611        assert v[2] == 0
1612        assert v[3] == 2
1613
1614        # Another case
1615        polygon3 = [[1,5], [10,1], [100,10], [50,10], [3,6]]
1616        v = plot_polygons([polygon2,polygon3], figname='test2')
1617        assert len(v) == 4
1618        assert v[0] == 1
1619        assert v[1] == 100
1620        assert v[2] == 1
1621        assert v[3] == 10
1622
1623        os.remove('test1.png')
1624        os.remove('test2.png')
1625
1626    def test_inside_polygon_geospatial(self):
1627        #Simplest case: Polygon is the unit square
1628        polygon_absolute = [[0,0], [1,0], [1,1], [0,1]]
1629        poly_geo_ref = Geo_reference(57, 100, 100)
1630        polygon = poly_geo_ref.change_points_geo_ref(polygon_absolute)
1631        poly_spatial = Geospatial_data(polygon, geo_reference=poly_geo_ref)
1632
1633        points_absolute = (0.5, 0.5)
1634        points_geo_ref = Geo_reference(57, 78, -56)
1635        points = points_geo_ref.change_points_geo_ref(points_absolute)
1636        points_spatial = Geospatial_data(points, geo_reference=points_geo_ref)
1637
1638        assert is_inside_polygon(points_absolute, polygon_absolute)
1639        assert is_inside_polygon(ensure_numeric(points_absolute),
1640                                 ensure_numeric(polygon_absolute))
1641        assert is_inside_polygon(points_absolute, poly_spatial)
1642        assert is_inside_polygon(points_spatial, poly_spatial)
1643        assert is_inside_polygon(points_spatial, polygon_absolute)
1644
1645        assert is_inside_polygon(points_absolute, polygon_absolute)
1646
1647    def NOtest_decimate_polygon(self):
1648        polygon = [[0,0], [10,10], [15,5], [20, 10],
1649                   [25,0], [30,10], [40,-10], [35, -5]]
1650
1651        dpoly = decimate_polygon(polygon, factor=2)
1652
1653        print dpoly
1654
1655        assert len(dpoly)*2==len(polygon)
1656
1657        minx = maxx = polygon[0][0]
1658        miny = maxy = polygon[0][1]
1659        for point in polygon[1:]:
1660            x, y = point
1661
1662            if x < minx: minx = x
1663            if x > maxx: maxx = x
1664            if y < miny: miny = y
1665            if y > maxy: maxy = y
1666
1667        assert [minx, miny] in polygon
1668        print minx, maxy
1669        assert [minx, maxy] in polygon
1670        assert [maxx, miny] in polygon
1671        assert [maxx, maxy] in polygon
1672
1673    def test_interpolate_polyline(self):
1674        """test_interpolate_polyline(self):
1675
1676        This test is added under the assumption that the function
1677        interpolate_polyline implemented by John Jakeman works.
1678        It has been exercised somewhat by tests of sts boundary,
1679        but never before separately.
1680        """
1681
1682        f = num.array([58.06150614, 58.06150614, 58.06150614])
1683        vertex_coordinates = num.array([[0., 0., ],
1684                                        [4.04092634, 1106.11074699],
1685                                        [8.08836552, 2212.16910609]])
1686        gauge_neighbour_id = [1, 2, -1]
1687        point_coordinates = num.array([[2.21870766e+03, 1.09802864e+03],
1688                                       [1.62739645e+03, 2.20626983e+03],
1689                                       [5.20084967e+02, 2.21030386e+03],
1690                                       [6.06464546e+00, 1.65913993e+03],
1691                                       [1.61934862e+03, -5.88143836e+00],
1692                                       [5.11996623e+02, -1.85956061e+00],
1693                                       [2.02046270e+00, 5.53055373e+02]])
1694
1695        z_ref = [0., 0., 0., 58.06150614, 0., 0., 58.06150614]
1696
1697        z = interpolate_polyline(f, vertex_coordinates,
1698                                 gauge_neighbour_id, point_coordinates)
1699        assert num.allclose(z, z_ref)
1700
1701        # Another f
1702        f = num.array([58.06150614, 158.06150614, 258.06150614])
1703        z_ref = [0., 0., 0., 208.06150645, 0., 0., 108.0615061]
1704        z = interpolate_polyline(f, vertex_coordinates,
1705                                 gauge_neighbour_id, point_coordinates)
1706        assert num.allclose(z, z_ref)
1707
1708        # Other and simpler numbers
1709        f = num.array([1, 5, 13])
1710        vertex_coordinates = num.array([[0., 0., ],
1711                                        [4., 4.],
1712                                        [8., 8.]])
1713        point_coordinates = num.array([[0.1, 0.1],
1714                                       [3.5, 3.5],
1715                                       [4.0, 4.0],
1716                                       [5.2, 5.2],
1717                                       [7.0, 7.0],
1718                                       [8.3, 8.3]])
1719        gauge_neighbour_id = [1, 2, -1]
1720
1721        z = interpolate_polyline(f, vertex_coordinates,
1722                                 gauge_neighbour_id, point_coordinates)
1723        z_ref = [1.1, 4.5, 5., 7.4, 11., 0.]
1724        assert num.allclose(z, z_ref)
1725
1726        # Test exception thrown for one point
1727        f = num.array([5])
1728        vertex_coordinates = num.array([[4., 4.]])
1729        try:
1730            z = interpolate_polyline(f, vertex_coordinates,
1731                                     gauge_neighbour_id, point_coordinates)
1732        except Exception:
1733            pass
1734        else:
1735            raise Exception, 'One point should have raised exception'
1736
1737        # More polyline nodes
1738        data = num.array([1, 5, 13, 12, 6, 29])
1739        polyline_nodes = num.array([[0., 0.],
1740                                    [4., 4.],
1741                                    [8., 8.],
1742                                    [10., 10.],
1743                                    [10., 5.],
1744                                    [10., 0.]])
1745        point_coordinates = num.array([[0.1, 0.1],
1746                                       [3.5, 3.5],
1747                                       [4.0, 4.0],
1748                                       [5.2, 5.2],
1749                                       [7.0, 7.0],
1750                                       [8.3, 8.3],
1751                                       [10., 10.],
1752                                       [10., 9.],
1753                                       [10., 7.1],
1754                                       [10., 4.3],
1755                                       [10., 1.0]])
1756        gauge_neighbour_id = [1, 2, 3, 4, 5, -1]
1757        z = interpolate_polyline(data, polyline_nodes,
1758                                 gauge_neighbour_id, point_coordinates)
1759        z_ref = [1.1, 4.5, 5., 7.4, 11., 12.85, 12., 10.8, 8.52, 9.22, 24.4]
1760        assert num.allclose(z, z_ref)
1761
1762
1763    def test_is_inside_triangle_more(self):
1764
1765        res = is_inside_triangle([0.5, 0.5], [[ 0.5,  0. ],
1766                                              [ 0.5,  0.5],
1767                                              [ 0.,   0. ]])
1768        assert res is True
1769
1770        res = is_inside_triangle([0.59999999999999998, 0.29999999999999999],
1771                                 [[ 0.5,  0. ], [ 0.5, 0.5], [0., 0.]])
1772        assert res is False
1773
1774        res = is_inside_triangle([0.59999999999999998, 0.29999999999999999],
1775                                 [[1., 0.], [1., 0.5], [0.5, 0.]])
1776        assert res is False
1777
1778
1779        res = is_inside_triangle([0.59999999999999998, 0.29999999999999999],
1780                                 [[0.5, 0.5], [0.5, 0.], [1., 0.5]])
1781        assert res is True
1782
1783
1784        res = is_inside_triangle([0.10000000000000001, 0.20000000000000001],
1785                                 [[0.5, 0.], [0.5, 0.5], [0., 0.]])
1786        assert res is False
1787
1788
1789        res = is_inside_triangle([0.10000000000000001, 0.20000000000000001],
1790                                 [[0., 0.5], [0., 0.], [0.5, 0.5]])
1791        assert res is True
1792
1793        res = is_inside_triangle([0.69999999999999996, 0.69999999999999996],
1794                                 [[0.5, 0.], [0.5, 0.5], [0., 0.]])
1795        assert res is False
1796
1797        res = is_inside_triangle([0.59999999999999998, 0.29999999999999999],
1798                                 [[0.25, 0.5], [0.25, 0.25], [0.5, 0.5]])
1799        assert res is False
1800
1801
1802        res = is_inside_triangle([10, 3],
1803                                 [[0.1, 0.],
1804                                  [0.1, 0.08333333],
1805                                  [0., 0.]])
1806        assert res is False
1807
1808       
1809    def test_is_polygon_complex(self):
1810        """Test a concave and a complex poly with is_complex, to make sure it can detect
1811           self-intersection.
1812        """
1813        concave_poly = [[0, 0], [10, 0], [5, 5], [10, 10], [0, 10]]
1814        complex_poly = [[0, 0], [10, 0], [5, 5], [4, 15], [5, 7], [10, 10], [0, 10]]
1815
1816        assert not is_complex(concave_poly)
1817        assert is_complex(complex_poly)
1818
1819    def test_is_polygon_complex2(self):
1820        """Test a concave and a complex poly with is_complex, to make sure it can detect
1821           self-intersection. This test uses more complicated polygons.
1822        """   
1823        concave_poly = [[0, 0], [10, 0], [11,0], [5, 5], [7,6], [10, 10], [1,5], [0, 10]]
1824        complex_poly = [[0, 0], [12,12], [10, 0], [5, 5], [3,18], [4, 15], [5, 7], [10, 10], [0, 10], [16, 12]]       
1825
1826        assert not is_complex(concave_poly)
1827        assert is_complex(complex_poly)
1828       
1829################################################################################
1830
1831if __name__ == "__main__":
1832    suite = unittest.makeSuite(Test_Polygon,'test')
1833    runner = unittest.TextTestRunner()
1834    runner.run(suite)
Note: See TracBrowser for help on using the repository browser.