Checking if a point is inside a polygon
I would suggest using the Path
class from matplotlib
import matplotlib.path as mplPathimport numpy as nppoly = [190, 50, 500, 310]bbPath = mplPath.Path(np.array([[poly[0], poly[1]], [poly[1], poly[2]], [poly[2], poly[3]], [poly[3], poly[0]]]))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
Notes:
- 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
continue
or useand
.
Steps:
- Iterate over all the segments in the polygon
- Check whether they intersect with a ray going in the increasing-x direction
Using the 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 intersectdef 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[0].x, poly.corners[0].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.