-
Notifications
You must be signed in to change notification settings - Fork 0
/
Point in Polygon Updated.py
76 lines (56 loc) · 2.72 KB
/
Point in Polygon Updated.py
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
#!/usr/bin/env python
# a Point is represented as a tuple: (x,y)
#===================================================================
# is_left(): tests if a point is Left|On|Right of an infinite line.
# Input: three points P0, P1, and P2
# Return: >0 for P2 left of the line through P0 and P1
# =0 for P2 on the line
# <0 for P2 right of the line
# See: the January 2001 Algorithm "Area of 2D and 3D Triangles and Polygons"
from datetime import datetime
start=datetime.now()
def is_left(P0, P1, P2):
return (P1[0] - P0[0]) * (P2[1] - P0[1]) - (P2[0] - P0[0]) * (P1[1] - P0[1])
#===================================================================
# cn_PnPoly(): crossing number test for a point in a polygon
# Input: P = a point,
# V[] = vertex points of a polygon
# Return: 0 = outside, 1 = inside
# This code is patterned after [Franklin, 2000]
def cn_PnPoly(P, V):
cn = 0 # the crossing number counter
# repeat the first vertex at end
V = tuple(V[:])+(V[0],)
# loop through all edges of the polygon
for i in range(len(V)-1): # edge from V[i] to V[i+1]
if ((V[i][1] <= P[1] and V[i+1][1] > P[1]) # an upward crossing
or (V[i][1] > P[1] and V[i+1][1] <= P[1])): # a downward crossing
# compute the actual edge-ray intersect x-coordinate
vt = (P[1] - V[i][1]) / float(V[i+1][1] - V[i][1])
if P[0] < V[i][0] + vt * (V[i+1][0] - V[i][0]): # P[0] < intersect
cn += 1 # a valid crossing of y=P[1] right of P[0]
return cn % 2 # 0 if even (out), and 1 if odd (in)
#===================================================================
# wn_PnPoly(): winding number test for a point in a polygon
# Input: P = a point,
# V[] = vertex points of a polygon
# Return: wn = the winding number (=0 only if P is outside V[])
def wn_PnPoly(P, V):
wn = 0 # the winding number counter
# repeat the first vertex at end
V = tuple(V[:]) + (V[0],)
# loop through all edges of the polygon
for i in range(len(V)-1): # edge from V[i] to V[i+1]
if V[i][1] <= P[1]: # start y <= P[1]
if V[i+1][1] > P[1]: # an upward crossing
if is_left(V[i], V[i+1], P) > 0: # P left of edge
wn += 1 # have a valid up intersect
else: # start y > P[1] (no test needed)
if V[i+1][1] <= P[1]: # a downward crossing
if is_left(V[i], V[i+1], P) < 0: # P right of edge
wn -= 1 # have a valid down intersect
return wn
vertex_set = [(0,10),(10,10),(10,0),(0,0)]
Point=(0,0)
print cn_PnPoly(Point, vertex_set)
print datetime.now()-start