Как я могу эффективно оптимизировать количество координат в 2D-пути?

Question

Я работаю с большим количеством координат в 2D-среде. Координаты моделируют путь.

Вот пример:

path = [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (2,2), (1,2), (0,2)]

Я хочу оптимизировать этот путь, удалив лишние координаты. Часто координаты перемещаются по прямой на оси X или Y. Следовательно, все точки между «угловыми» координатами могут быть удалены с пути.

Этот путь будет эквивалентен указанному выше:

path = [(0,0), (3,0), (3,2), (0,2)]

Вот изображение для описания Желаемая оптимизация:

Координаты всегда будут располагаться прямо на одной из осей. Диагональные линии можно игнорировать.

Было бы здорово, если бы кто-нибудь дал мне подсказку о том, как добиться этого эффективным способом. Мне нужно многократно запускать алгоритм оптимизации, поскольку путь генерируется процедурно.

Answer 1

Алгоритм Rahmer-Douglas-Peucker во многих случаях подходит для уменьшения количества точек на маршруте 2D.

Пример в python:

#  pip install rdp

from rdp import rdp

path = [[0,0], [1,0], [2,0], [3,0], [3,1], [3,2], [2,2], [1,2], [0,2]]

rdp(path)

#  output: [[0, 0], [3, 0], [3, 2], [0, 2]]

Проект проекта rdp home

Answer 2

Итак, я пришел к следующему решению: каждый раз, когда я добавляю новую точку к пути, я проверяю, равны ли значения X или Y значениям двух предыдущих точек. Если это правда, я могу удалить среднюю из трех точек.

private void RedundancyCheck()
{
    if (this.Points.Length < 3)
    {
        return;
    }
    var last = this.Points[this.Points.Length-1];
    var secondLast = this.Points[this.Points.Length-2];
    var thirdLast = this.Points[this.Points.Length-3];

    if ( (last.x == secondLast.x && last.x == thirdLast.x)
        || (last.y == secondLast.y && last.y == thirdLast.y) )
    {
        RemovePoint(this.Points.Length-2);
    }
}

Этот алгоритм работает довольно быстро, и мне удалось уменьшить количество координат с ~ 450'000 до ~ 3300 , (конечно это зависит от координат)