Построить оптимальную полилинию

Question

У меня есть задача построить ломаную линию с наименьшим количеством сечений из заданного набора точек в 2-мерном пространстве, но все, что я могу найти, - это алгоритм наилучшего соответствия. Любые предложения, пожалуйста? (Мне не нужно решение, просто направление к правильному решению, я все еще хочу найти его сам)

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

Это просто, но довольно масштабно и, вероятно, не оптимизировано. Input - массив списков несортированных точек, которые должны l ie на ломаной линии; output - координаты оптимальных вершин полилинии; использование -

ArrayList<Point> polyline = optimize(points);

По сути, это:

1. Сортировка точек по значению X
2. Переносит первую точку в новый массив, который в начале пуст
3. Удаляет эту первую точку из старого массива
4. Извлекает последнюю точку из нового массива
5. "Связывает" ее со всеми остальными точками
6. Находит линию (секунду точка), которая включает в себя наибольшее количество других точек
7. Добавляет новую найденную точку в новый массив
8. Удаляет новую найденную точку и все точки, лежащие на линии из старого массива
9. Повторите цикл, начиная с шага 4.

Если у вас есть какие-либо лучшие решения, пожалуйста, поделитесь со мной!