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

[orcpochta]

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

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

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

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

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

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

[undefined]

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

[orcpochta]

Сообщение от undefined

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

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

[undefined]

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

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

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

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

[orcpochta]

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

[mikleb]

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

[ripeLime]

Сообщение от mikleb

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

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

[Tertium Organum]

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

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