Невозможно понять решение HDU 2823

Question

Следующий фрагмент кода был взят из here. Это решение этой проблемы 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; 

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

Answer 1

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

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

где А является подписано площади треугольника а, б, в. Знак детерминанта также указывает нам, если 3 точки ориентированы по часовой стрелке или по часовой стрелке. see here for an explanation

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

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. На каждом шаге держите минимальное расстояние между токами .

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

Интуиция позади таких идей хорошо иллюстрируется в этой статье "Solving Geometric Problems with the Rotating Calipers" - Туссен G.