algorithm - 确定一组点的 "inner domain"

Question

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

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

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

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

你有线索吗？

Ps:如果有帮助，我正在用 C++ 编写代码。

Answer 1

您正在查看的绿线称为 convex hull 的点集有 many good, efficient algorithms for computing it .它们中最好的运行时间为 O(n log h)，其中 h 是在船体上找到的点数，n 是点总数。作为一个完全无耻的 self 推销，我有 a C++ implementation of one of these algorithms 在我的个人网站上可用。

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

希望这对您有所帮助!