二维点的天际线——分而治之算法

Question

我正在做一个项目，我必须找到不被集中的任何其他点支配的点的天际线。如果 x1<=x2 && y1<=y2，则点 A(x1,y1) 支配点 B(x2,y2)。 Here's an example

这是我的代码：

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;
}

These are the results.

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

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

**点根据它们的 x 值（升序）排序

Answer 1

好的，我明白逻辑错误了。它在这里：

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

当你删除一个点时，其余的点向左移动（据我理解remove意义），所以下一个（non-treated还）项目获得当前索引i并被排除在外进一步治疗。

最简单的解决方案 - 使用 while 循环并在删除发生时省略递增索引。

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

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

二维点的天际线——分而治之算法

Skyline of 2D points-Divide and conquer algorithm

java

algorithm

geometry

points

divide