划分和征服船体算法

Question

你好我今天的问题是细分并弄清楚如何实际编码我已设法完成步骤(1)和(2)的算法的LOWER TANGENT部分,但我现在仍然坚持步骤(3).

划分和征服凸出的船体

船体(S):

(1)如果| S | <= 3,然后在O(1)时间内通过强力计算凸包并返回.

(2)否则,将点集S划分为两组A和B,其中A由具有最低x坐标的一半点组成,B由具有最高x坐标的一半点组成.

(3)递归计算HA = Hull(A)和HB = Hull(B).

(4)通过计算HA和HB的上下切线并丢弃位于这两个切线之间的所有点,将两个船体合并成一个共同的凸包H.

http://www.cs.wustl.edu/~pless/506/l3_1.gif

寻找下切线

LowerTangent(HA; HB):

(1)让a成为HA最右边的一点.

(2)设b是HB的最左边.

(3)虽然ab不是HA和HB的下切线

(a)虽然ab不是HA的下切线,但a = a - 1(顺时针方向移动).

(b)虽然ab不是HB的下切线,但是b = b + 1(逆时针方向移动b).

(4)返回ab.

引用自:http://www.cs.wustl.edu/~pless/506/l3.html 这个解释是描述我的问题的最佳解释.

Lexisort和convexHull的功能尚未包括在内,因为它们正在工作,DC船体算法已被包含在内以提供上下文.

我目前的代码:

public static int [][] dcHull(int [][]merged){

    if(merged.length <= 3)
        return convexHull(merged);

    else {

        lexiSort(merged);
        //split(P, A, B);
        //SPLIT
        double p = merged.length;
        int A;
        int B;

        if (p%2 == 0){//EVEN
            A = (int) (p/2);
            B = (int) (p/2);
        }
        else//ODD
            A = (int) (1+(p/2));
            B = (int) (p/2);



        int arrayA[][] = new int[A][2]; 
        int arrayB[][] = new int[B][2];

        for (int i=0; i<A; i++){
            arrayA[i][0] = merged[i][0];
            arrayA[i][1] = merged[i][1];
        }

        for (int i=0; i<B; i++){
            arrayB[i][0] = merged[i+A][0];
            arrayB[i][1] = merged[i+A][1];
        }

        for ( int i=0; i<arrayA.length; i++){
            System.out.println( "Merged array A Coordinates: " + arrayA[i][0] +", " + arrayA[i][1]);}
        for ( int i=0; i<arrayB.length; i++){
            System.out.println( "Merged array B Coordinates: " + arrayB[i][0] +", " + arrayB[i][1]);}

        lowerT(arrayA, arrayB);
        //upperT(arrayA, arrayB);


        return merged(dcHull(convexHull(arrayA)), dcHull(convexHull(arrayB)));

    }

}

public static int[][] lowerT(int [][] hulla, int [][]  hullb){

    int a = 0;
    int b = 0;

    //LOWER TANGENT
    //(1) Let a be the rightmost point of HA .
    for (int i=0; i<hulla.length; i++){
        if (a < hulla[i][0]){
            a = hulla[i][0];
        }
    }
    //(2) Let b be the leftmost point of HB .
    for (int i=0; i<hullb.length; i++){
        if (b < hullb[i][0]){
            b = hullb[i][0];
        }
    }
    for (int i=0; i<hullb.length; i++){
        if (b > hullb[i][0]){
            b = hullb[i][0];
        }
    }

在完成HA的HA和b之后,代码完成但是我不理解(3)或更准确地说是如何使用我拥有的元素对其进行编码.

(1)让a成为HA最右边的一点.

(2)设b是HB的最左边.

还有一种称为右转的代码方法我认为是有用的:"较低的相切是一种可以通过船体上两个顶点和相邻顶点的方向测试进行局部测试的条件."

我只是不确定如何把它放在一起.

public static boolean rightTurn(int [][] rt, int counter) //AxBxC = (Bx-Ax)(Cy-Ay)-(By-Ay)(Cx-Ax)
{
    int ax = rt[counter-2][0];
    int bx = rt[counter-1][0];
    int cx = rt[counter][0];

    int ay = rt[counter-2][1];
    int by = rt[counter-1][1];
    int cy = rt[counter-0][1];
    int result =(bx-ax)*(cy-ay)-(by-ay)*(cx-ax);

    if (result < 0){                            // Result = VE+ (Right Turn), 0, VE- (Left Turn)

        return true;                                                    //VE- = TRUE = Right Turn
    }

    else return false;                                                  //VE+ = FALSE = Left Turn
}

Answer 1

第一,

//(2) Let b be the leftmost point of HB .
for (int i=0; i<hullb.length; i++){
    if (b < hullb[i][0]){
        b = hullb[i][0];
    }
}
for (int i=0; i<hullb.length; i++){
    if (b > hullb[i][0]){
        b = hullb[i][0];
    }
}

似乎有一个剩下的复制品.

现在,让我们尝试改变"但我不理解(3)或更准确地说是如何使用我拥有的元素对其进行编码".

(a)虽然ab不是HA的下切线,但a = a - 1(顺时针方向移动).

因此,您需要测试直线是否与HA的切线相等.这里的几何情况简化了测试.基本原则当然是HA的凸性.所考虑的直线L总是通过HA的顶点,比如v,以及HB的vertwx,比如b.令两个相邻顶点为u和w,标记为使得u,v,w是边界的顺时针部分.有三种可能性,1.u和w都位于L之上或之上,然后,通过凸性,L是HA的下切线; 2.之一ü和瓦特位于上方或上大号,下面的其他; 3.两个位于下方大号.

当且仅当路径bvw在v处向左转弯时,w位于L下方.当且仅当路径bvu在v处向左转弯时,u位于L下方.

您需要一个功能来检查路径ABC是否在B处左转(以小于180°的角度).你rightTurn有要点,但错误的参数,因为你要测试的一个点属于另一个船体.并且测试你的标志是否正确,它很容易滑到那里.

因此,当v的两个邻居中的任何一个位于通过b和v的直线下方时,将v替换为其顺时针邻居并再次检查.在挑选邻居时要注意数组边界.

经过几个步骤后,您发现了一条与HA相比较低的直线,但通常不是HB的直线.

(b)虽然ab不是HB的下切线,但是b = b + 1(逆时针方向移动b).

这是类似的,但随着方向的改变.的点p HB的边界上位于通过直线下方一个(HA的顶点)和b(HB的考虑顶点)当且仅当该路径PBA使得在左转弯b.

在HB的边界上挑选逆时针邻居,直到发现HB的下切线绕HA的边界上的顶点a旋转线,使得HB的下切线不再是HA的下切线(看图片你链接).

所以回到3(a).这将使线绕b旋转,可能太多,以至于它不再是HB的下切线.3(b)再次.
迭代直到找到两者的切线较低.

aIndex = findRightmostA();
bIndex = findLeftmostB();
while(!(lowerTangentA (aIndex, bIndex) && lowerTangentB(aIndex, bIndex))){
    aIndex = findLowerTangentA(aIndex, bIndex);
    bIndex = findLowerTangentB(aIndex, bIndex);
}

lowerTangentA(aIndex, bIndex){
    ux = hulla[aIndex+1][0];
    uy = hulla[aIndex+1][1]; // array bounds!
    ax = hulla[aIndex][0];
    ay = hulla[aIndex][1];
    wx = hulla[aIndex-1][0];
    wy = hulla[aIndex-1][1];
    bx = hullb[bIndex][0];
    by = hullb[bIndex][1];
    return !(leftTurn(bx,by,ax,ay,ux,uy) || leftTurn(bx,by,ax,ay,wx,wy));
}

找到两个船体的上切线是类似的.尝试抽象切线检查是值得的,这样您就可以对所有检查使用相同的功能(下限/上限,HA/HB).