Области вороного

[NaOH]

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

Вопрос: Как узнать в какой области Вороного находится центр окружности ?

[TOTAL]

NaOH в сообщении #230915 писал(а):

Чтобы не делать лишних подщётов для этого, слышал, используются области Вороного

Чтобы найти области Вороного, придется делать подсчеты.
Так что ничего не сэкономите, находите обычным способом.

[NaOH]

TOTAL в сообщении #230917 писал(а):

NaOH в сообщении #230915 писал(а):

Чтобы не делать лишних подщётов для этого, слышал, используются области Вороного

Чтобы найти области Вороного, придется делать подсчеты.
Так что ничего не сэкономите, находите обычным способом.

Вообще мне надо найти столкновение круга с четырёхугольником.
Схема рисунка из первого поста:
1 2 3
4 | 5
6 7 8
Проблема в том, что надо проверять столкновение круга с вершинами четырёхугольника, но проверять их надо только тогда, когда центр окружности находиться в области 1,3,6 или 8, иначе проверяем только условие накладываются проекции фигур на обоих осях или нет.

Вопрос: Как узнать, находиться ли центр окружности в области 1,3,6 или8 ?

[TOTAL]

NaOH в сообщении #230984 писал(а):

Вопрос: Как узнать, находиться ли центр окружности в области 1,3,6 или8 ?

Не можете узнать совсем или хотите сэкономить?

Вот так, например:

if (x_0 < x < x_1) then
не находится
elseif (y_0 < y < y_1) then
не находится
else
находится
endif

[Circiter]

2NaOH

Цитата:

Проблема в том, что надо проверять столкновение круга с вершинами четырёхугольника, но проверять их надо только тогда, когда центр окружности находиться в области 1,3,6 или 8, иначе проверяем только условие накладываются проекции фигур на обоих осях или нет
...
Вопрос: Как узнать в какой области Вороного находится центр окружности ?

Кажется, вы не совсем понимаете смысл использования областей Вороного.

Определение того, в какой области Вороного находится центр подвижного объекта (окружности) как раз и осуществляют проверяя наложение линейных оболочек объектов в "базисе" на сторонах стационарного объекта.

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

Если же перекрывается только одна проекция (или по вертикали или по горизонтали), то значит столкновения нет.

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

Так, например, если у окружности центр суть вектор $\vec{a}$, а в прямоугольнике центр $\vec{b}$, то пары вида $(sgn(a_x-b_x),sgn(a_y-b_y))$, то есть, например, $(-,-)$, или $(+,-)$, и сопоставляются областям Вороного.

По вашей иллюстрации, e.g. для случая $(+,+)$ ближайшей к центру окружности является верхняя правая вершина прямоугольника (только одна). И в худшем случае (если проекции на координатные оси не перекрываются вообще) вам придется определить комбинацию знаков и проверить пересечение окружности с соответствующей вершиной (просто вычислив расстояние и сравнив его с радиусом окружности).

Понятно, что необязательно брать именно центры, нужно просто иметь возможность оценить взаимное расположение объектов.

Как видите, вопреки мнению TOTAL'а, набор областей Вороного (т.н. диаграмма Вороного) является "виртуальной" концепцией и почти не требует предварительных расчетов (оптимальные реализации подразумевают явное построение диаграмм, для этого существуют вкусные $O(n)$-алгоритмы). Но вам все равно стоит взвесить все pro et contra и выбрать наилучшее решение (может быть стоит обратить внимание на BSP или OBB-деревья, благо публикаций с ключевыми словами collision detection существует огромное количество)