凸壳算法问题

因此，我必须使用分区/融合算法绘制一组随机点的凸包 .

我是'll join the two main functions used in the algorithm, my issue is that if there are multiple points with the same X but different Ys, if the top most (resp. bottom most) is included in the Hull, the ones abelow (resp. above) are also included when they shouldn'，导致像这样的案件：https://cdn.discordapp.com/attachments/521348023670931456/521431090590908439/unknown.png

我无法确定功能中的问题情况，所以如果有人能帮助我，我会非常感激 . 在这些中，“nuage”ArrayList是集群中所有点的列表，如果X相等，则按X然后Y排序 .

-------------------------------分区功能：

static void partition(ArrayList<Point> nuage, ArrayList<Point> convexe){
    convexe.clear();

    if(nuage.size() <= 3){
        convexe.addAll(nuage);
        if(nuage.size() == 3 && Area.triangle(convexe.get(0), convexe.get(1), convexe.get(2)) >= 0){
        Point p = convexe.get(1);
        convexe.remove(p);
        convexe.add(p);
    }
    return;
    }

    ArrayList<Point> subList1 = new ArrayList<Point>();
    ArrayList<Point> subList2 = new ArrayList<Point>();

    for(int i = 0; i < nuage.size()/2; i++)
        subList1.add(nuage.get(i));

    for(int i = nuage.size()/2; i < nuage.size(); i++)
        subList2.add(nuage.get(i));

    ArrayList<Point> convexe1 = new ArrayList<Point>();
    ArrayList<Point> convexe2 = new ArrayList<Point>();
    partition(subList1, convexe1);
    partition(subList2, convexe2);

    convexe.addAll( fusion(convexe1, convexe2) );
}

-----------------融合功能：

static ArrayList<Point> fusion(ArrayList<Point> subList1, ArrayList<Point> subList2){

    int iMax = 0;
    int iMin = 0;

    for( int i = 1; i < subList1.size(); i++){
        if(subList1.get(i).x > subList1.get(iMax).x)
        iMax = i;
    }

    int firstLink1 = iMax;
    int firstLink2 = iMin;
    boolean b = true;
    while(b){
        b = false;
        if(Area.triangle(subList2.get(firstLink2), subList1.get(firstLink1), subList1.get((firstLink1+1)%subList1.size())) > 0){
        firstLink1 = (firstLink1+1)%subList1.size();
        b = true;
        }
        if(Area.triangle(subList1.get(firstLink1), subList2.get(firstLink2), subList2.get((firstLink2-1+subList2.size())%subList2.size())) < 0){
            firstLink2 = (firstLink2-1+subList2.size())%subList2.size();
            b = true;
        }
    }

    int secondLink1 = iMax;
    int secondLink2 = iMin;
    b = true;
    while(b){
        b = false;
        if(Area.triangle(subList2.get(secondLink2), subList1.get(secondLink1), subList1.get((secondLink1-1+subList1.size())%subList1.size())) < 0){
        secondLink1 = (secondLink1-1+subList1.size())%subList1.size();
        b = true;
        }
        if(Area.triangle(subList1.get(secondLink1), subList2.get(secondLink2), subList2.get((secondLink2+1)%subList2.size())) > 0){
            secondLink2 = (secondLink2+1)%subList2.size();
            b = true;
        }
    }

    ArrayList<Point> env = new ArrayList();

    for(int i = 0; i <= secondLink1; i++)
        env.add(subList1.get(i));

    if(firstLink2 == 0){
        for(int i = secondLink2; i < subList2.size(); i++)
            env.add(subList2.get(i));

        env.add(subList2.get(0));
    }
    else{
        for(int i = secondLink2; i <= firstLink2; i++)
            env.add(subList2.get(i));
    }
    if(firstLink1 != 0){
        for(int i = firstLink1; i < subList1.size(); i++)
            env.add(subList1.get(i));
    }
   return env;

}