一个点是否在多边形内部？

Question

4

给定一个表示二维多边形的点列表，如何确定该点是否在多边形内部。

请注意，多边形可以是凸多边形或凹多边形。您也可以对点的顺序做出任何假设。

- iBrAaAa

4个回答

2

选择多边形外的一个点。在您的点和外部点之间绘制一条线。如果该线与多边形相交奇数次，则在内部，否则在外部。零次交点也在外部。但是，这仅适用于非重叠多边形。

- user1910823

1

这是一个已知的问题，有很多解决方案，只需在谷歌上搜索即可。并阅读以下内容： http://en.wikipedia.org/wiki/Point_in_polygon

- OopsUser

0

从您的点到多边形外部的任意一点取一条任意线（即在边界之外）。检查该线与多边形边缘相交的次数。如果值为奇数，则该点在内部。

在检查时，要注意通过顶点的线，您的测试可能会指示两个边缘交叉。

- JasonD

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- PearsonArtPhoto · Accepted Answer

最佳的方法是从你所在的点画一条向任何方向的线，并数一下你穿过对象边界的次数。如果你穿过偶数次边界，那么你在对象外部，如果是奇数次，那么你在内部。通常最容易的方法是沿着其中一个轴进行这个决定。

实质上，你只需要找到一种方法来确定是否穿过了一个点。使用线段斜率公式 (m=(y1-y2)/(x1-x2) ,y=m*x(x-x1)+y1)，并查看您是否穿越了有效点的边界范围。给定这条线段的方程，确定您的线穿过这条线的位置，并确定它是否在这条线的范围内。

顺便说一下，同样的方法适用于任意维度，只不过变得更难以确定是否碰到面。

为了展示一些例子，我画了一张简单的插图，展示了内部和外部发生的情况，即使是奇怪的形状也适用。

顺便说一句，如果你碰到一个角落，它会计算你从内部到外部的转换次数。 enter image description here