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

Question

[dom1n1k]

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

Но как лучше всего хранить готовую диаграмму, какую структуру данных использовать?
И не просто хранить, а чтобы потом быстро и удобно узнавать, в какую ячейку попала произвольная точка.
Она ведь (диаграмма) в общем случае лишена какой-то регулярности.

Comments

[Александр]

Как вводится произвольная точка для определения?

[dom1n1k]

Координатами на плоскости, какие ещё варианты могут быть?

Answer 1

[Сергей Соколов]

«Хранить диаграмму» нет смысла.

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

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

Answer 2

[forspamonly2]

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

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