I have a class describing a Point (has 2 coordinates x and y) and a class describing a Polygon which has a list of Points which correspond to corners (self.corners)
I need to check if a Point is in a Polygon
Here is the function that is supposed to check if the Point is in the Polygon. I am using the Ray Casting Method
def in_me(self, point): result = False n = len(self.corners) p1x = int(self.corners.x) p1y = int(self.corners.y) for i in range(n+1): p2x = int(self.corners[i % n].x) p2y = int(self.corners[i % n].y) if point.y > min(p1y,p2y): if point.x <= max(p1x,p2x): if p1y != p2y: xinters = (point.y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x print xinters if p1x == p2x or point.x <= xinters: result = not result p1x,p1y = p2x,p2y return result
I run a test with following shape and point:
PG1 = (0,0), (0,2), (2,2), (2,0) point = (1,1)
The script happily returns False even though the point it within the line. I am unable to find the mistake
I would suggest using the
Path class from
import matplotlib.path as mplPath import numpy as np poly = [190, 50, 500, 310] bbPath = mplPath.Path(np.array([[poly, poly], [poly, poly], [poly, poly], [poly, poly]])) bbPath.contains_point((200, 100))
(There is also a
contains_points function if you want to test for multiple points)
I’d like to suggest some other changes there:
def contains(self, point): if not self.corners: return False def lines(): p0 = self.corners[-1] for p1 in self.corners: yield p0, p1 p0 = p1 for p1, p2 in lines(): ... # perform actual checks here
- A polygon with 5 corners also has 5 bounding lines, not 6, your loop is one off.
- Using a separate generator expression makes clear that you are checking each line in turn.
- Checking for an empty number of lines was added. However, how to treat zero-length lines and polygons with a single corner is still open.
- I’d also consider making the lines() function a normal member instead of a nested utility.
- Instead of the many nested if structures, you could also check for the inverse and then
- Iterate over all the segments in the polygon
- Check whether they intersect with a ray going in the increasing-x direction
intersect function from This SO Question
def ccw(A,B,C): return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x) # Return true if line segments AB and CD intersect def intersect(A,B,C,D): return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D) def point_in_polygon(pt, poly, inf): result = False for i in range(len(poly.corners)-1): if intersect((poly.corners[i].x, poly.corners[i].y), ( poly.corners[i+1].x, poly.corners[i+1].y), (pt.x, pt.y), (inf, pt.y)): result = not result if intersect((poly.corners[-1].x, poly.corners[-1].y), (poly.corners.x, poly.corners.y), (pt.x, pt.y), (inf, pt.y)): result = not result return result
Please note that the
inf parameter should be the maximum point in the x axis in your figure.
I was trying to solve the same problem for my project and I got this code from someone in my network.
#!/usr/bin/env python # # routine for performing the "point in polygon" inclusion test # Copyright 2001, softSurfer (www.softsurfer.com) # This code may be freely used and modified for any purpose # providing that this copyright notice is included with it. # SoftSurfer makes no warranty for this code, and cannot be held # liable for any real or imagined damage resulting from its use. # Users of this code must verify correctness for their application. # translated to Python by Maciej Kalisiak <firstname.lastname@example.org> # 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" def is_left(P0, P1, P2): return (P1 - P0) * (P2 - P0) - (P2 - P0) * (P1 - P0) #=================================================================== # 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,) # 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] <= P and V[i+1] > P) # an upward crossing or (V[i] > P and V[i+1] <= P)): # a downward crossing # compute the actual edge-ray intersect x-coordinate vt = (P - V[i]) / float(V[i+1] - V[i]) if P < V[i] + vt * (V[i+1] - V[i]): # P < intersect cn += 1 # a valid crossing of y=P right of P 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,) # 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] <= P: # start y <= P if V[i+1] > P: # 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 (no test needed) if V[i+1] <= P: # 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