algorithm - 确定一组点的“内部域”

Question

我有一组 (x, y) 点，我想从这些点中插入这组点“内部”的任何点的值。（下图中黄色区域）。

问题是我没有找到任何好的方法：

1. 找到将成为我的插值点边界的多边形（绿线）
2. 测试该点是否在多边形内。我找到了Point in Polygon算法，但我不确定在某个范围内获取所有点并测试它们是否属于多边形是一个好主意。我想找到一种方法让我测试比 (max(x)-min(x))*(max(y)-min(y)) 更少的点，理想情况下是一种知道哪些点的方法做我的迭代。

编辑：在第二部分我迭代图像中的所有点（像素），我想做的只是迭代黄色字段中的点。

你有铅吗？

Ps：如果有任何帮助，我正在用 C++ 编码。

Answer 1

您正在查看的绿线称为点集的凸包，并且有许多好的、有效的算法可以计算它。它们中最好的运行时间为 O(n log h)，其中 h 是在船体上找到的点数，n 是点的总数。作为一种完全无耻的自我推销，我在我的个人网站上提供了其中一种算法的 C++ 实现。

至于你的第二个问题——一旦你有了凸包，就很容易确定哪些点纯粹在多边形内部，而不是在凸包上。只需制作所有点的哈希表，然后遍历凸包并删除包中包含的所有点。哈希表中剩下的是包含在多边形内但不在边界上的点集。

希望这可以帮助！