Не могу понять решение HDU 2823

Question

Не могу понять решение HDU 2823

Следующий фрагмент кода был взят из Вот. Это решение этой проблемы HDU 2823.

#define eps 1e-9
double rc(point pp[],point qq[],int n,int m)
{
int q=0;
int p=0;
for(int i=0;i<n;i++)
if(pp[i].y-pp[p].y<-eps)
p=i;
for(int i=0;i<m;i++)
if(qq[i].y-qq[q].y>eps)
q=i;
pp[n]=pp[0];
qq[m]=qq[0];
double tmp,ans=1e99;
for(int i=0;i<n;i++)
{
while((tmp=cross(pp[p+1],qq[q+1],pp[p])-cross(pp[p+1],qq[q],pp[p]))>eps)
q=(q+1)%m;
if(tmp<-eps)
ans=min(ans,dist_p_to_seg(qq[q],pp[p],pp[p+1]));
else
ans=min(ans,dist_seg_to_seg(pp[p],pp[p+1],qq[q],qq[q+1]));
p=(p+1)%n;
}
return ans;

}

pp[] а также qq[] два разных выпуклых корпуса. p самая высокая точка pp выпуклый корпус и q самая низкая точка qq выпуклый корпус.

Я не могу понять эту строку:

while((tmp=cross(pp[p+1],qq[q+1],pp[p])-cross(pp[p+1],qq[q],pp[p]))>eps)
q=(q+1)%m;

Чего он пытается добиться?

0

c++computational-geometry convex-hull raycasting

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Функция cross (a, b, c) находит определитель следующей матрицы,

| a.x a.y 1 |
| b.x b.x 1 |  = 2 * A
| c.x c.y 1 |

Где А это подписанный площадь треугольника а, б, в.
Знак определителя также говорит нам, если 3 точки ориентированы по часовой стрелке или против часовой стрелки. смотрите здесь для объяснения

Давайте перепишем так,

triA ← cross(pp[p+1],qq[q+1],pp[p])
triB ← cross(pp[p+1],qq[q],pp[p])

// This is equivalent to,
// just to make it a bit clearer
triA ← cross(pp[p], pp[p+1],    qq[q+1])
triB ← cross(pp[p], pp[p+1],    qq[q])

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

Если да, выберите следующую точку в qq как q и продолжай. -i.e. выберите q так что перпендикулярное расстояние q со стороны <p, p+1> сводится к минимуму

Как только это локально минимизируется для данной стороны <p, p+1>Повторите это для всех сторон pp, На каждом шаге соблюдайте минимальное расстояние между ток Стороны.

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

Интуиция, лежащая в основе таких идей, хорошо иллюстрируется в этой статье.
«Решение геометрических задач с помощью вращающихся штангенциркулей»
— Туссен Г.

1