algorithm - 点在多边形内吗？

Question

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

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

Answer 1

执行此操作的最佳方法是从您的点向任意方向画一条线，并计算您越过对象边界的次数。如果你碰到边界的次数是偶数次，那么你就在物体外面，如果是奇数次，你就在里面。通常最容易沿着其中一个轴进行确定。

本质上，您只需要找到一种方法来确定您是否越过了一个点。使用线性方程的斜率 (m=(y1-y2)/(x1-x2), y=m*x(x-x1)+y1, and看看你是否越过该点有效的边界。给定点之间线的这个等式，确定你的线在哪里穿过这条线，并弄清楚它是否在线的范围内。

顺便说一句，同样的方法适用于任意维度，只是确定你是否击中了脸变得更加困难。

为了展示几个例子，我画了一个简单的插图，展示了内部和外部发生的事情，甚至是一个奇怪的形状。

顺便说一下，如果你撞到一个角，它会计算你从内到外的转换次数。