dom1n1k
@dom1n1k

Как лучше всего хранить диаграмму Вороного?

Алгоритм построения оставим за кадром - допустим, мы умеем это делать каким-либо образом, да хоть бы даже и вручную.

Но как лучше всего хранить готовую диаграмму, какую структуру данных использовать?
И не просто хранить, а чтобы потом быстро и удобно узнавать, в какую ячейку попала произвольная точка.
Она ведь (диаграмма) в общем случае лишена какой-то регулярности.
  • Вопрос задан
  • 153 просмотра
Пригласить эксперта
Ответы на вопрос 2
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
«Хранить диаграмму» нет смысла.

Я бы хранил только координаты точек и при запросе делал поиск ближайшего соседа. Ведь весь смысл диаграммы Вороного - в разбиении на области, где ближайший сосед - одна из контрольных точек.

Upd. Возможно, я ошибался и хранить диаграмму можно как binary tree, что даст более быстрый поиск ответа на принадлежность точки к области – обходом дерева. (или не даст?)
Ответ написан
Комментировать
@forspamonly2
если нужно быстро узнавать ближайшую точку к заданной, то можно хранить диаграмму воронного в виде растровой карты.

регулярная сетка, в каждой ячейке список ближайших точек. у большинства ячеек внутри полигонов диаграммы список будет из одного элемента, а на границах между полигонами - из нескольких.
чем выше разрешение карты, тем больше попаданий и меньше вычислений на каждую точку. при низком разрешении карты (если памяти мало), получится фильтр блума.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы