Как получить очки вокруг клетки вороной?
Я пытаюсь получить точки, которые образуют многоугольник, чтобы заполнить его каким-то цветом. У меня есть набор точек, а затем я рассчитываю для него диаграмму Вороного. Результат таков:
Зеленые точки — это точки, которые я определяю, а синие точки — это рассчитанные вершины для диаграммы Вороного. Я хочу заполнить многоугольник, который генерируется определенной зеленой точкой, поэтому мне нужно знать, какие точки вокруг него, чтобы сформировать многоугольник и заполнить его.
Я читал о Алгоритм упаковки подарков а также Выпуклый корпус но это не то, что мне нужно. Есть ли алгоритмы, чтобы удовлетворить эту потребность? Я программирую на C ++, но любая помощь на Java или C # будет полезна.
Решение
Алгоритм упаковки подарков (который является алгоритмом выпуклой оболочки) предназначен для поиска наименьшего выпуклого многоугольника, который содержит набор точек на плоскости. Это не то, что вы хотите здесь.
Алгоритм фортуны является хорошим решением для нахождения фактических границ вашей диаграммы Вороного. Это не тривиальный алгоритм, но полный псевдокод предоставлен на связанной странице Википедии. Внизу страницы Википедии есть ссылки на реализации алгоритма Fortune на нескольких разных языках.
Другие решения
Ваша реализация алгоритма Fortune, кажется, вычисляет естественное вложение, которое можно использовать для извлечения списков ребер для граней. Вот критическая структура данных.
struct Halfedge
{
struct Halfedge *ELleft, *ELright;
struct Edge *ELedge;
int ELrefcnt;
char ELpm;
struct Site *vertex;
float ystar;
struct Halfedge *PQnext;
};
ELleft а также ELright представляется двусвязным списком, который содержит ребра, инцидентные определенной вершине или грани, отсортированные по углу. Если это лицо, ты золотой; в противном случае вы можете выполнить итерацию вокруг грани, обновив половину e до обратной стороны следующей половины ребра в (против) направлении по часовой стрелке относительно вершины назначения (то есть, наоборот ELleft).