看不懂HDU 2823的解决办法

Question

以下代码片段摘自 here. It is the solution of this problem 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

函数 cross(a, b, c) 正在寻找以下矩阵的行列式，

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

其中 A 是三角形 a、b、c 的符号面积。行列式的符号也告诉我们 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])

所以它检查由船体pp的一侧形成的三角形与qq上的最低点是否小于由同一侧形成的三角形并且来自qq的下一个最高点。

如果是，select下一个在qq里点q然后继续。 -IE。 select a q 使 q 与边 <p, p+1> 的垂直距离最小化。

一旦给定边 <p, p+1> 的局部最小化，对 pp 的所有边重复此操作。在每一步保持当前边之间的最小距离。

这是一种有点不稳定的方法来寻找两个凸包之间的最小间隔。直觉是正确的——正确的是它很容易理解（这个想法，不是有问题的代码），对于凸多边形非常普遍，并且非常有用的各种问题（请参阅下面的参考资料）；但是，我觉得可以用一种更有效和更容易理解的方式来编写。

这篇论文很好地说明了这些想法背后的直觉 "Solving Geometric Problems with the Rotating Calipers" -- 图桑 G.

看不懂HDU 2823的解决办法

Can't understand the solution of HDU 2823

c++

computational-geometry

raycasting

convex-hull