找到一个多边形内的任意点。

问题:

如何在多边形内找到_任意_一个点,使得该点距离多边形边缘至少为 epsilon(以避免数值问题)。

解释:

我想找到的解决方案与通常的“点是否在多边形内”问题不同。我想这可能会更简单,或者建立在“点在多边形内”算法(例如射线投射)的答案之上。

该过程可以通过选择多边形的伪中心点 (min + max) / 2 开始。该点可以通过射线投射或类似方法进行测试。如果该点不在多边形内,则会在每个轴的 min 和 max 之间随机选择另一个点。

我们正在讨论的多边形具有不规则的形状,由数十到百个顶点定义。不会有自交。如果我选择靠近多边形边缘的点,则会出现数值问题,因此必须添加一个要求,即该点不太靠近边缘。它不需要特别计算效率,只是不要过于低效。

这能够简单而优雅地解决吗?

我正在使用 Lua。

点赞
用户240457
用户240457

选择一个凸多边形中某个方向的极值点,例如 $y$ 坐标最大的点。依据该点到其两侧点的连线的平分线方向移动一个短距离。检查你是否位于凸多边形内,如果不是,则减少移动距离。

如果两侧的点具有相同的 $y$ 坐标,你需要尝试在两侧进行测试。

2015-11-26 18:44:42