给定代表二维多边形的点列表，我如何确定该点是否在多边形内。
请注意，多边形可以是凹的也可以是凸的。您还可以对点的顺序做出任何假设。
问问题
495 次
4 回答
7
执行此操作的最佳方法是从您的点向任何方向画一条线，并计算您越过对象边界的次数。如果您碰到边界的次数为偶数次，则您在对象外，如果是奇数次，则您在对象内。通常最容易沿着其中一个轴进行确定。
本质上，您只需要找到一种方法来确定您是否越过一个点。使用直线方程的斜率（m=(y1-y2)/(x1-x2), y=m*x(x-x1)+y1，并查看您是否在该点有效的边界内交叉。给定点之间直线的此等式，确定您的直线与该直线相交的位置，并确定它是否在线的范围。
顺便说一句，同样的方法适用于任意维度，只是确定是否击中面部变得更加困难。
为了展示几个例子，我画了一个简单的插图，展示了内部和外部发生的事情，即使是奇怪的形状。
顺便说一句，如果你撞到一个角落，它会计算你从内到外转换的次数。
于 2012-12-17T18:23:38.567 回答
2
选择多边形外的一个点。在你的和外面的点之间画一条线。如果线与多边形相交奇数次，则为内部，否则为外部。零路口也在外面。但是，这仅适用于非重叠多边形
于 2012-12-17T18:29:40.083 回答
1
这是许多解决方案的已知问题，只需谷歌即可。并阅读： http ://en.wikipedia.org/wiki/Point_in_polygon
于 2012-12-17T19:08:57.793 回答
0
从您的点取一条任意线，到您的多边形之外的任何点（即边界之外）。检查该线与多边形的边缘之一相交的次数。如果值为奇数，则该点在内部。
检查时，请注意穿过顶点的线，您的测试可能会指示两个边缘交叉。
于 2012-12-17T18:23:23.917 回答