判断一个点是否在 Voronoi 单元内

Question

判断一个点是否在 Voronoi 单元内

5

有没有简单的方法来判断一个点是否在Voronoi单元内？

例如，以下代码生成类似于下面的图表：

using namespace boost::polygon;

point_data<int> p1(0, 0);
point_data<int> p2(-10, 10);
point_data<int> p3(-10, -10);
point_data<int> p4(10, -10);
point_data<int> p5(10, 10);

std::vector<point_data<int>> pts = { p1, p2, p3, p4, p5 };
construct_voronoi(pts.begin(), pts.end(), vd);

voronoi diagram

在这种情况下，我该如何确定点（5,5）是否在中心单元格内？

我可以将每个单元格创建为一个多边形，并使用点在多边形算法来找出，但我想知道库是否免费提供了类似的功能。

- André Wagner

可能最简单的方法是遍历所有多边形并验证中心点0,0是否在其中，并检查特定多边形中要检查的点是否在其中。 - cageman

1

我不确定您想要在示例数据中正好位于两个单元格边界上的点(5, 5)的哪个结果。无论如何，另一种方法是不使用点在多边形算法，而是检查测试点到定义每个 Voronoi 单元格的点的距离。距离最近的点告诉您您的测试点在哪个单元格中。 - Magnus Hoff

3个回答

0

你想进行点位置测试，特别是使用Kirkpatrick数据结构进行点位置测试，但这有点复杂。相反，你可以给每个Voronoi单元格涂上颜色，并检查该点的颜色。

- Micromega

0

一个好的方法是使用一些空间划分数据结构（如KD树）来支持点站，这提供了易于（N-）最近邻搜索（实际上，任何体面的Voronoi图实现在点站插入期间应该已经在进行最近邻搜索）。

因此，在图表旁使用自己的数据结构（树）：当点站插入到Voronoi图中时，将相同的点插入到树中。查询树以查找（N）最近的Voronoi站点。然后由您决定如何将该站点坐标映射到Voronoi单元对象。

- micycle

OP 是在询问如何测试一个点是否在给定的单元格中，而不是找到包含该点的单元格。 - Sneftel

最终结果是相同的：返回getContainingCell(point) == givenCell。 - micycle

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- thor · Accepted Answer

就像 @Magnus Hoff 评论的那样，由最接近查询点的中心定义的单元格必须包含它（直到距离相等为止）。实际上，这是 Voronoii 单元格的定义，即成员比任何其他中心更靠近单元格中心的点集。

因此，这个查询实际上不需要使用 boost::polygon 或半线算法：

//using namespace boost::polygon;
using namespace std;
#include <iostream>
#include <vector>
#include <limits>

template <typename T> 
using point_data = std::pair<T,T>;
point_data<int> p1(0, 0);
point_data<int> p2(-10, 10);
point_data<int> p3(-10, -10);
point_data<int> p4(10, -10);
point_data<int> p5(10, 10);

std::vector<point_data<int>> pts = { p1, p2, p3, p4, p5 };
//construct_voronoi(pts.begin(), pts.end(), vd);


double dist2(point_data<int> pt1,point_data<int> pt2) {
  return (pt1.first-pt2.first)*(pt1.first-pt2.first) + (pt1.first-pt2.second)* (pt1.first-pt2.second);
}

bool isInCell(point_data<int> point) {
  double d = numeric_limits<double>::max();

  point_data<int> ptClose;
  for (auto& pt:pts) {
    if (dist2(pt,point) < d)
      ptClose = pt;
  }
  return ptClose == point;
}

int main() {
  cout << isInCell(make_pair(5,5)) << endl;
}