二维点分治算法的天际线

Question

我正在做一个项目，在那里我必须找到天际线的点，而不是主导的任何其他点的集合。A点A(x1，y1)控制着B点(x2，y2)如果x1<=x2 & y1<=y2.下面是一个例子

这是我的密码：

public static ArrayList<Point> findSkyline(ArrayList<Point> pointsList){
    if (pointsList.size()<=1){
        return pointsList;
    }

    ArrayList<Point> leftSkylinePoints=new ArrayList<>();
    ArrayList<Point> rightSkylinePoints=new ArrayList<>();
    ArrayList<Point> leftPoints=new ArrayList<>();
    ArrayList<Point> rightPoints=new ArrayList<>();

    for (int i=0;i<pointsList.size()/2;i++){
        leftPoints.add(pointsList.get(i));
    }
    for (int i=pointsList.size()/2;i<pointsList.size();i++){
        rightPoints.add(pointsList.get(i));
    }

    leftSkylinePoints=findSkyline(leftPoints);
    rightSkylinePoints=findSkyline(rightPoints);

    int minY=1001;
    for (int i=0;i<leftSkylinePoints.size();i++){
        if (leftSkylinePoints.get(i).y<minY){
            minY=leftSkylinePoints.get(i).y;
        }
    }
    for (int i=0;i<rightSkylinePoints.size();i++){
        if (rightSkylinePoints.get(i).y>=minY){
            rightSkylinePoints.remove(i);
        }
    }

    System.out.println("MINY: "+minY);

    System.out.print("Left: ");
    for (int i=0;i<leftSkylinePoints.size();i++){
        System.out.print("("+leftSkylinePoints.get(i).x+","+leftSkylinePoints.get(i).y+") ");
    }
    System.out.println();
    System.out.print("Right: ");
    for (int i=0;i<rightSkylinePoints.size();i++){
        System.out.print("("+rightSkylinePoints.get(i).x+","+rightSkylinePoints.get(i).y+") ");
    }
    System.out.println();
    System.out.println();


    leftSkylinePoints.addAll(rightSkylinePoints);
    return leftSkylinePoints;
}

这些都是结果。

如您所见，点(6,2)似乎在天际线上，但不应该是因为它应该在第二个for循环中被删除。有人知道为什么会这样吗？谢谢!

*为了更多的积分，我得到了更多不该出现的东西，但现在我想知道这种情况。

**点按x值(升序)排序。

Answer 1

好吧，我理解逻辑缺陷。它就在这里：

 for (int i=0;i<rightSkylinePoints.size();i++){
       if (rightSkylinePoints.get(i).y>=minY){
           rightSkylinePoints.remove(i);

当您移除一个点时，其余部分将向左移动(据我所理解的remove意义)，因此下一个(尚未处理)项将获得当前索引i，并将其排除在进一步的处理之外。

最简单的解决方案-使用while循环和省略增量索引，如果发生删除。

另一种方法-从较大的索引循环到较低的索引(似乎这样的方向不应该破坏算法)

 for (int i=rightSkylinePoints.size() -1; i >=0; i--)