Как получить точки вокруг ячейки Вороного?

Я пытаюсь получить точки, которые образуют многоугольник, чтобы заполнить его каким-либо цветом. У меня есть набор точек, и я вычисляю для него диаграмму Вороного. Результат таков:

Диаграмма Вороного

Зеленые точки — это точки, которые я определяю, а синие точки — расчетные вершины диаграммы Вороного. Я хочу заполнить многоугольник, созданный определенной зеленой точкой, поэтому мне нужно знать, какие точки находятся вокруг него, чтобы сформировать многоугольник и заполнить его.

Я прочитал об алгоритме упаковки подарков и Выпуклая оболочка, но это не то, что мне нужно. Существуют ли какие-либо алгоритмы для удовлетворения этой потребности? Я программирую на C++, но любая помощь по Java или C# будет полезна.


c++ algorithm polygon voronoi
person Andres    schedule 28.05.2013    source источник
comment
Функция Matlab voronoi(x,y) дает вам всю необходимую информацию.   -  person David    schedule 28.05.2013
comment
Я делаю это на C++, поэтому Matlab не альтернатива, мне нужен алгоритм для написания в моей программе.   -  person Andres    schedule 28.05.2013
comment
С++ вызывает матлаб (через COM) без проблем, дело в том, хотите ли вы погрузиться в черный ящик.   -  person David    schedule 28.05.2013
comment
Существует ли независимая от платформы автономная библиотека С++? Потому что потом я буду распространять свою программу и не смогу везде установить Matlab. Я не слишком много знаю о Matlab, поэтому я спрашиваю.   -  person Andres    schedule 28.05.2013
comment
если вы хотите развернуть его на другом ПК, это больше не вариант. Хоть и осуществимо, но очень громоздко и отнимет у вас много времени. Оставь это.   -  person David    schedule 28.05.2013
comment
Да, но мне нужно развернуть его на другом ПК :/   -  person Andres    schedule 28.05.2013
comment
@Andres: как вы вычисляете вершины диаграммы Вороного? Если у вас есть доступ к источнику, вы можете изменить его, чтобы сохранить эти вершины для вас, связанные с точками, которые их породили.   -  person André Neves    schedule 28.05.2013
comment
Я использую эту библиотеку skynet.ie/~sos/mapviewer/voronoi.php Итак, у меня есть доступ к исходному коду, но я понятия не имею, как он работает :/   -  person Andres    schedule 28.05.2013
comment
@Andres Попробуйте это › Начните с зеленой точки, растяните, чтобы понять окружность многоугольника, как воздушный шар, заполняющий свою площадь со временем; когда закончите, извлеките точки многоугольника из окружности   -  person Khaled.K    schedule 29.05.2013

Ответы (2)


arrow_upward
1
arrow_downward

Алгоритм подарочной упаковки (который представляет собой алгоритм выпуклой оболочки) предназначен для поиска наименьшего выпуклого многоугольника, содержащего набор точек на плоскости. Это не то, что вы хотите здесь.

Алгоритм Фортуны — хорошее решение для определения фактических границ диаграммы Вороного. Это нетривиальный алгоритм, но полный псевдокод представлен на связанной странице Википедии. Внизу страницы Википедии есть ссылки на реализации алгоритма Fortune на нескольких разных языках.

person Timothy Shields    schedule 28.05.2013
comment
проверьте en.wikipedia.org/wiki/Fortune's_algorithm псевдокод находится здесь, и код C здесь ect.bell-labs.com/who/sjf/voronoi. смола - person Ph.T; 28.05.2013
comment
@Ph.T У меня уже есть именно эта ссылка в моем ответе. Разве ты этого не видел? - person Timothy Shields; 28.05.2013
comment
Извините, Тимоти только сейчас увидел, я не нажимал на ссылку, чтобы быть искренним.. хорошая работа - person Ph.T; 28.05.2013
comment
@Ph.T Ха-ха, нет проблем - я просто был сбит с толку, почему вы комментируете ту же самую ссылку. :) - person Timothy Shields; 28.05.2013
comment
Алгоритм, который я использую, - это алгоритм удачи, который генерирует загруженное мной изображение, но дает мне точки многоугольника, но я не знаю, с каким сайтом он связан, и это то, что мне нужно. Я искал алгоритм, потому что его немного сложно реализовать или я не могу его полностью понять:/ - person Andres; 28.05.2013
comment
Алгоритм @Andres Fortune находит всю необходимую информацию во время работы. Это должно быть само собой разумеющимся: на изображении нарисованы граничные линии и граничные вершины. Если проблема в том, что вы возвращаете эти границы без соответствующих точек генерации для каждого граничного сегмента, тогда вам придется внедрить непосредственно в свою реализацию некоторое поведение, чтобы сохранить эту информацию во время работы алгоритма. - Это нетривиальная задача - больше, чем вы можете ожидать от ответа Stack Overflow. Граничные лучи C_pq, упомянутые на странице Википедии, являются началом. - person Timothy Shields; 28.05.2013

arrow_upward
0
arrow_downward

Ваша реализация алгоритма 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).

person David Eisenstat    schedule 29.05.2013
comment
Хорошо, я изучал исходный код и вижу его. Я видел другие библиотеки Voronoid, такие как blog.ivank.net/fortunes-algorithm-and -implementation.html, сгенерированная диаграмма Вороного не всегда верна, но у меня есть такая информация. Похоже, мне нужна структура: struct Halfedge *PQhash - person Andres; 30.05.2013