1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| import sys
from collections import namedtuple
Pt = namedtuple('Pt', 'x, y')
Edge = namedtuple('Edge', 'a, b')
Polygon = namedtuple('Polygon', 'name, edges')
_eps = 0.00001
_huge = sys.float_info.max
_tiny = sys.float_info.min
def ray_intersect_seg(p, edge):
""" takes a point p=Pt() and an edge of two endpoints a,b=Pt() of a line segment returns boolean
"""
a, b = edge
if a.y > b.y:
a, b = b, a
if p.y == a.y or p.y == b.y:
p = Pt(p.x, p.y + _eps)
if (p.y > b.y or p.y < a.y) or (
p.x > max(a.x, b.x)):
return False
if p.x < min(a.x, b.x):
intersect = True
else:
if abs(a.x - b.x) > _tiny:
m_red = (b.y - a.y) / float(b.x - a.x)
else:
m_red = _huge
if abs(a.x - p.x) > _tiny:
m_blue = (p.y - a.y) / float(p.x - a.x)
else:
m_blue = _huge
intersect = m_blue >= m_red
return intersect
def _odd(x): return x % 2 == 1
def is_point_inside(p, poly_list):
ln = len(poly_list)
return _odd(sum(ray_intersect_seg(p, edge)
for edge in poly_list.edges))
def poly_print(polygon):
print("\n Polygon(name='%s', edges=(" % polygon.name)
print(' ', ',\n '.join(str(e) for e in polygon.edges) + '\n ))')
if __name__ == '__main__':
polys = [
Polygon(name='square', edges=(
Edge(a=Pt(x=0, y=0), b=Pt(x=10, y=0)),
Edge(a=Pt(x=10, y=0), b=Pt(x=10, y=10)),
Edge(a=Pt(x=10, y=10), b=Pt(x=0, y=10)),
Edge(a=Pt(x=0, y=10), b=Pt(x=0, y=0))
)),
Polygon(name='square_hole', edges=(
Edge(a=Pt(x=0, y=0), b=Pt(x=10, y=0)),
Edge(a=Pt(x=10, y=0), b=Pt(x=10, y=10)),
Edge(a=Pt(x=10, y=10), b=Pt(x=0, y=10)),
Edge(a=Pt(x=0, y=10), b=Pt(x=0, y=0)),
Edge(a=Pt(x=2.5, y=2.5), b=Pt(x=7.5, y=2.5)),
Edge(a=Pt(x=7.5, y=2.5), b=Pt(x=7.5, y=7.5)),
Edge(a=Pt(x=7.5, y=7.5), b=Pt(x=2.5, y=7.5)),
Edge(a=Pt(x=2.5, y=7.5), b=Pt(x=2.5, y=2.5))
)),
Polygon(name='strange', edges=(
Edge(a=Pt(x=0, y=0), b=Pt(x=2.5, y=2.5)),
Edge(a=Pt(x=2.5, y=2.5), b=Pt(x=0, y=10)),
Edge(a=Pt(x=0, y=10), b=Pt(x=2.5, y=7.5)),
Edge(a=Pt(x=2.5, y=7.5), b=Pt(x=7.5, y=7.5)),
Edge(a=Pt(x=7.5, y=7.5), b=Pt(x=10, y=10)),
Edge(a=Pt(x=10, y=10), b=Pt(x=10, y=0)),
Edge(a=Pt(x=10, y=0), b=Pt(x=2.5, y=2.5))
)),
Polygon(name='exagon', edges=(
Edge(a=Pt(x=3, y=0), b=Pt(x=7, y=0)),
Edge(a=Pt(x=7, y=0), b=Pt(x=10, y=5)),
Edge(a=Pt(x=10, y=5), b=Pt(x=7, y=10)),
Edge(a=Pt(x=7, y=10), b=Pt(x=3, y=10)),
Edge(a=Pt(x=3, y=10), b=Pt(x=0, y=5)),
Edge(a=Pt(x=0, y=5), b=Pt(x=3, y=0))
)),
]
test_points = (Pt(x=5, y=5), Pt(x=5, y=8),
Pt(x=-10, y=5), Pt(x=0, y=5),
Pt(x=10, y=5), Pt(x=8, y=5),
Pt(x=10, y=10))
print("\n TESTING WHETHER POINTS ARE WITHIN POLYGONS")
for poly in polys:
poly_print(poly)
print(' ', '\t'.join("%s: %s" % (p, is_point_inside(p, poly))
for p in test_points[:3]))
print(' ', '\t'.join("%s: %s" % (p, is_point_inside(p, poly))
for p in test_points[3:6]))
print(' ', '\t'.join("%s: %s" % (p, is_point_inside(p, poly))
for p in test_points[6:]))
|