algorithm - 查找多边形内的任意点

Question

问题:

如何找到多边形内的任何点，该点与边的距离至少为epsilon(以避免数值问题)。

解释:

我想找到解决方案的问题与通常的是多边形内的点问题不同。我想这可能更简单，或者建立在对多边形点算法(例如光线转换)的答案之上。

该过程可以从选取多边形 (min+max)/2 的伪中点开始。这一点可以通过光线转换或类似的东西来测试。如果该点不在另一个点内，则随机选择每个轴的 min 和 max 之间的某处。

我们所说的多边形具有不规则的形状，由几十到一百个顶点定义。不会有 self 交集。如果我在多边形的边缘附近选择一个点，我会担心数值问题，因此必须添加该点不是非常靠近边缘的要求。它不需要特别高效的计算，只要不是疯狂的低效即可。

这可以用一种简单、优雅的方式解决吗？

我正在使用 Lua。

Answer 1

在多边形上选择一个在某个方向上是极端的点，例如y 坐标最大的点。沿平分直线的方向移动一小段距离，从该点到它两侧的点。检查您是否在多边形中，如果不在，则减少移动的距离。

如果有关系并且它两侧的点具有相同的 y 坐标，您将不得不尝试在两侧测试点。