Credit: SpikedMath.com |

*inside*a polygon. Reader Sebastian V. pointed out the ray-casting alogrithm I used does not test to see if the point is on the edge of the polygon or one of the verticies. He was even nice enough to send a PHP script he found which uses an indentical ray-casting method and includes a vertex and edge test as well.

These two checks are relatively simple however whether they are necessary is up to you and how you apply this test. There are some cases where a boundary point would not be considered for inclusion. Either way now you have an option. This function could even be modified to optionally check for boundary points.

# Improved point in polygon test which includes edge # and vertex points def point_in_poly(x,y,poly): # check if point is a vertex if (x,y) in poly: return "IN" # check if point is on a boundary for i in range(len(poly)): p1 = None p2 = None if i==0: p1 = poly[0] p2 = poly[1] else: p1 = poly[i-1] p2 = poly[i] if p1[1] == p2[1] and p1[1] == y and x > min(p1[0], p2[0]) and x < max(p1[0], p2[0]): return "IN" n = len(poly) inside = False p1x,p1y = poly[0] for i in range(n+1): p2x,p2y = poly[i % n] if y > min(p1y,p2y): if y <= max(p1y,p2y): if x <= max(p1x,p2x): if p1y != p2y: xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x if p1x == p2x or x <= xints: inside = not inside p1x,p1y = p2x,p2y if inside: return "IN" else: return "OUT" # Test a vertex for inclusion poligono = [(-33.416032,-70.593016), (-33.415370,-70.589604), (-33.417340,-70.589046), (-33.417949,-70.592351), (-33.416032,-70.593016)] lat= -33.416032 lon= -70.593016 print point_in_poly(lat, lon, poligono) # test a boundary point for inclusion poly2 = [(1,1), (5,1), (5,5), (1,5), (1,1)] x = 3 y = 1 print point_in_poly(x, y, poly2)You can download this script here.

## No comments:

## Post a Comment