确定一组点的"内部域"

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++实现.

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

希望这可以帮助!