java - 构建最佳折线

Question

我的任务是从二维空间中给定的一组点构建一条具有最少部分的折线，但我能找到的只是最佳拟合算法。请问有什么建议吗？ (我不需要解决方案，只是一个正确解决方案的方向，我还是想自己找到)

Answer 1

如果有人正在寻找解决方案，这是我的尝试:

private static ArrayList<Point> optimize(ArrayList<Point> p) {
        ArrayList<Point> polyline = new ArrayList<Point>();
        p = sort(p);
        polyline.add(p.get(0));
        p.remove(0);
        while(!p.isEmpty()) {
            Point curr = polyline.get(polyline.size() - 1);
            int max = 0;
            int maxIndex = maxPointsIndex(p, curr);
            if(maxIndex == -1) {
                polyline.add(p.get(0));
                p.remove(0);
            } else {
                polyline.add(p.get(maxIndex));
                Point second = p.remove(maxIndex);
                p = removeBetweenPoints(p, curr, second);
            }
        }
        return polyline;
    }

    private static ArrayList<Point> removeBetweenPoints(ArrayList<Point> p, Point f, Point s) {
        ArrayList<Point> temp = new ArrayList<Point>();
        for(int i = 0; i < p.size(); i++) {
            if(!between(f, s, p.get(i))) {
                temp.add(p.get(i));
            }
        }
        return temp;
    }

    private static int maxPointsIndex(ArrayList<Point> p, Point curr) {
        int max = 0;
        int maxIndex = -1;
        for(int i = 0; i < p.size(); i++) {
            int amount = 0;
            for(int j = 0; j < p.size(); j++) {
                if(i != j) {
                    if(between(curr, p.get(i), p.get(j)))
                        amount++;
                }
            }
            if (amount > max) {
                max = amount;
                maxIndex = i;
            }
        }
        return maxIndex;
    } 

    private static boolean between(Point f, Point s, Point c) {
        int dxc = c.x - f.x;
        int dyc = c.y - f.y;
        int dxl = s.x - f.x;
        int dyl = s.y - f.y;
        int cross = dxc * dyl - dyc * dxl;
        if (cross != 0)
              return false;
        boolean answer;
        if (Math.abs(dxl) >= Math.abs(dyl)) {
            if(dxl > 0)
                answer = f.x <= c.x && c.x <= s.x;
            else
                answer = s.x <= c.x && c.x <= f.x;
        }
        else {
            if(dyl > 0)
                answer = f.y <= c.y && c.y <= s.y;
            else
                answer = s.y <= s.y && c.y <= f.y;
        } 
        return answer;
    }

    private static ArrayList<Point> sort(ArrayList<Point> p) {
        boolean swapped;
        do {
            swapped = false;
            for(int i = 1; i < p.size(); i++) {
                if(p.get(i).x < p.get(i-1).x) {
                    swapped = true;
                    Point temp = p.get(i);
                    p.set(i, p.get(i-1));
                    p.set(i-1, temp);
                }
            }
        } while (swapped);
        return points;
    }

它很简单，但相当庞大，而且可能没有优化。输入 - 应位于折线上的未排序点的数组列表；输出 - 最佳折线顶点的坐标；用法 -

ArrayList<Point> polyline = optimize(points);

它的作用基本上是:

1. 按 X 值对点进行排序
2. 将第一个点插入新数组，该数组开头为空
3. 从旧数组中删除第一个点
4. 从新数组中获取最后一个点
5. 将其“连接”到所有其他点
6. 查找包含最多其他点的线(第二个点)
7. 将新发现的点添加到新数组
8. 从旧数组中删除新找到的点和所有位于线上的点
9. 重复第 4 步的循环。

如果您有更好的解决方案请与我分享!