Выяснение, находится ли точка внутри клетки вороного

Question

Выяснение, находится ли точка внутри клетки вороного

Есть ли простой способ выяснить, находится ли точка внутри клетки вороного?

Например, следующий код генерирует что-то вроде диаграммы ниже:

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) внутри центральной ячейки?

Я мог бы создать многоугольник из каждой ячейки и выяснить, используя Точка в алгоритме многоугольника, но мне интересно знать, что библиотека предлагает что-то «бесплатно».

5

boost c++voronoi

Решение

Другие решения

Вам нужен тест местоположения точки, особенно структура данных kirkpatrick для проверки местоположения точки, но это немного сложнее. Вместо этого вы можете назначить цвет каждой ячейке вороной и проверить цвет в точке.

1

Источник

Accepted Answer

Например, @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;
}

2