5

ポイントがボロノイセル内にあるかどうかを調べる簡単な方法はありますか?

たとえば、次のコードは次の図のようなものを生成します。

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 がコメントしたように、クエリ ポイントに最も近い中心で定義されたセルには、それが含まれている必要があります (距離の関係まで)。実際、これはボロノイ セルの定義によるものです。つまり、メンバーが他のどの中心よりもセルの中心に近い点集合です。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 データ構造が必要ですが、少し複雑です。代わりに、各ボロノイ セルに色を付けて、ポイントの色を確認できます。

于 2015-11-17T22:03:10.467 に答える