Python 检查点是否在多边形内
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16625507/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Checking if a point is inside a polygon
提问by Helena
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
我有一个描述一个点的类（有 2 个坐标 x 和 y）和一个描述多边形的类，它有一个对应于角的点列表（self.corners）我需要检查一个点是否在一个多边形中
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
脚本愉快地返回 False 即使它在行内。我找不到错误
回答by Ulrich Eckhardt
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
continueor useand.
- 一个有 5 个角的多边形也有 5 条边界线，而不是 6 条，你的循环是一次性的。
- 使用单独的生成器表达式可以清楚地表明您正在依次检查每一行。
- 添加了检查空行数。但是，如何处理零长度线和具有单个角的多边形仍然是开放的。
- 我还考虑使 lines() 函数成为普通成员而不是嵌套实用程序。
- 除了许多嵌套的 if 结构之外，您还可以检查反向然后
continue使用and.
回答by P.R.
I would suggest using the Pathclass from matplotlib
我建议使用Path来自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_pointsfunction if you want to test for multiple points)
（contains_points如果要测试多个点，还有一个功能）
回答by dccsillag
Steps:
脚步：
- Iterate over all the segments in the polygon
- Check whether they intersect with a ray going in the increasing-x direction
- 迭代多边形中的所有线段
- 检查它们是否与沿 x 递增方向行进的射线相交
Using the intersectfunction from This SO Question
使用此 SO 问题中的intersect功能
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[0].x, poly.corners[0].y), (pt.x, pt.y), (inf, pt.y)):
result = not result
return result
Please note that the infparameter should be the maximum point in the x axis in your figure.
请注意，inf参数应为图中 x 轴的最大点。
