Форум Flasher.ru - Вопрос по областям Вороного.

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- - Вопрос по областям Вороного. (http://www.flasher.ru/forum/showthread.php?t=116193)

Вопрос по областям Вороного.

В этом форуме часто отсылают к следующей статье(точнее к ее переводу):
http://noregret.org/tutor/n/collision/ - где в частности дано следующее определение:

Цитата:

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

- с ним все понятно, а вот дальше сказано:

Цитата:

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

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

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

видимо, имеется ввиду проверка принадлежности центра окружности какой-либо зоне Вороного.

Цитата:

Сообщение от undefined (Сообщение 765895)

видимо, имеется ввиду проверка принадлежности центра окружности какой-либо зоне Вороного.

Это бесспорно, да, но как осуществляется эта проверка? И как описываются эти зоны, чтобы потом можно было осуществлять проверки?

Цитата:

но как осуществляется эта проверка?

не проверял, но вроде должно быть верно:
-Выбираем точку из множества
-Ставим затравку, считая, что ячейкой Вороного для данной точки будет вся плоскость.
-Проводим отрезки от точки до всех остальных точек множества
к каждому отрезку проводим серединный перпендикуляр
-Каждый перпендекуляр разбивает плоскость на 2 полуплоскости, надо выбрать ту полуплоскость где НЕ находится наша точка и вычесть полученное множество из текущей ячейки, т.о. на каждом шаге ячейка по площади будет становится все меньше и после обработки последнего отрезка получим готовую ячейку Вороного для данной точки.
Далее повторяем вышенаписаное для всех точек множества.

Цитата:

И как описываются эти зоны, чтобы потом можно было осуществлять проверки?

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

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

Вообще то определить принадлежность точки области вороного вершины или ребра, очень просто, нужно просто посчитать пару скалярных произведений

Цитата:

Сообщение от mikleb (Сообщение 769814)

А можно по подробней ?

блин ну что за загадочность!! все только и твердят, ячейки вороного - да раз плюнуть!
Ктонть знает куда именно плюнуть то? Найденные мной исходники (сам бы написал но не знаю в чем суть метода) - это далеко не пара скалярных произведений!

кстати сравнивать не обязательно расстояния до углов, достаточно их квадраты и тогда не надо вычислять тяжелые корни