Checking if a point is inside a polygon
59,932
Solution 1
I would suggest using the Path
class from matplotlib
import matplotlib.path as mplPath
import numpy as np
poly = [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)
Solution 2
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
.
Author by
Helena
Updated on April 20, 2021Comments
-
Helena about 3 years
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[0].x) p1y = int(self.corners[0].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
-
Martin Burch about 9 yearsFor this to work, you must first
import numpy as np
-
Christophe Roussy almost 8 yearsAnyone checked performance of
contains_points
against a pure Python implementation ? -
h345k34cr almost 7 yearsThis is incorrect, doesn't work for point [2, 5] with polygon [8, 6], [11, 10], [16, 5], [11, 3] Edit: The issue is probably that the ray goes directly through a point of the polygon, causing two polygon line segments to be toggling
result
, turning it back to its previous state -
Maciek about 6 yearsSomething's wrong, using array = [[100,100],[200,100],[200,200],[100,200],[100,100]] it gives False for point 100,100 and true for point 200,200
-
nda over 5 yearsWhy the variable name 'bbPath'? if (Does 'bb' abbreviate something?): what does 'bb' abbreviate?
-
P.R. over 5 years
bb
means bounding box even though the polygon very like wont be a box :) -
josch about 3 years@Maciek the answer to your question is in the docs: "The result is undefined for points exactly at the boundary"
-
josch about 3 years@ChristopheRoussy yes, benchmarks are at stackoverflow.com/questions/36399381