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);

沃罗诺伊图

在这种情况下，如何确定点 (5,5) 是否在中心单元内？

我可以从每个单元格中创建一个多边形，并使用多边形算法中的一个点来找出答案，但我很想知道该库提供“免费”的东西。

4

3 回答 3

2

就像，@Magnus Hoff 评论说，离查询点最近的中心定义的单元格必须包含它（直到距离关系）。事实上，这是来自 Voronoi 单元的定义，即其成员比任何其他中心更靠近单元中心的点集。所以，这个查询真的不需要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;
}
于 2014-02-01T19:47:42.217 回答
0

您需要点定位测试，尤其是用于点定位测试的 kirkpatrick 数据结构，但它有点复杂。相反，您可以为每个 voronoi 单元格指定颜色并检查该点的颜色。

于 2015-11-17T22:03:10.467 回答
0

一个好的方法是让点站点由一些空间分区数据结构（例如 KD 树）支持，它提供了简单的（N-）最近邻搜索（实际上任何体面的 voronoi 图实现都应该已经这样做了）在点站点插入期间进行最近邻搜索）。

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

于 2021-01-30T20:13:47.790 回答