发现如果一个点是Voronoi单元内 [英] Finding out if a point is inside a voronoi cell

问题描述

有没有一种简单的方法来找出是否一个点是Voronoi单元内的？

Is there a simple way to find out if a point is inside a voronoi cell?

例如，下面的code产生类似下图：

For example, the following code generates something like the diagram below:

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）是中央细胞内？

In this case, how can I found out if the point (5,5) is inside the central cell?

我可以创建一个多边形出每个细胞，并找出使用多边形算法点 ，但我想知道图书馆提供一些免费。

I could create a polygon out of each cell and find out using a point in polygon algorithm, but I'm interested in knowing the library offers something "for free".

推荐答案

一样，@Magnus霍夫评价，由最靠近中心查询点定义的单元格必须包含它（最多距离的关系）。在实际上，这是从一个Voronoii细胞的定义，即，点集的成员是比任何其他中心更靠近小区中心。
所以，这个查询真的不需要的boost ::多边形或半年线的算法：

Like, @Magnus Hoff commented, the cell defined by the closest center to your query point must contain it (up to distance ties). In fact, this is from the definition of a Voronoii cell, i.e. the point set whose members are closer to the cell center than to any other centers. So, this query really doesn't require boost::polygon or the half-line algorithm:

//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;
}

这篇关于发现如果一个点是Voronoi单元内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！