Рассчитать максимальное расстояние по полилинии, используя ограниченное количество точек
Проблема в следующем: у меня есть ломаная линия, которая обычно состоит из 1000-10000 точек. Мне нужно рассчитать максимальное расстояние вдоль полилинии, используя максимум 5 промежуточных точек. Формально: я ищу точки A,B,C,D,E, где расстояние FirstPointOfThePolyline-ABCDE-LastPointOfThePolyline максимально.
Результат должен быть точным, предположения не подходят для работы.
Я уже нашел алгоритм, который гарантированно даст лучший результат, но, поскольку он просматривает каждую точку, он довольно медленный:
(Показано только за 3 балла)
Array of points - P
Start point - P[0]
Finish point P[max]
1) create an array D0, where D0[x] = distance(P[x], P[0])
2) create an array D1, where D1[x] = max(D0[a] + distance(P[x], P[a])) over a in 0..x
- Array D1 now contains for every point 'x' maximum distance over 1 turnpoint to the point 'x'
3) create an array D2, where D2[x] = max(D1[a] + distance(P[x], P[a])) over a in 0..x
- Array D2 now contains for every point 'x' maximum distance over 2 turnpoints
4) Compute BestDistance = max(D2[a] + distance(P[max], P[a])) over a in 0..max
Моя идея, чтобы сделать это быстрее, заключалась в том, чтобы сделать ломаную линию более простой, например, сохранить только каждую десятую точку, быстро найти точки АЕ с алгоритмом в этом "исключенном списке", а затем во втором раунде взять все точки в пределах заданного радиуса этих AE указывает и снова запускает алгоритм, используя только точки в этих кругах. Этот метод намного быстрее, но предполагает, что реальные точки AE будут где-то поблизости от 5 точек, найденных в первом раунде, что иногда оказывается ложным утверждением.
Я искал несколько алгоритмов упрощения полилиний, которые могли бы помочь, но я не уверен на 100%, решит ли это мою проблему.
Итак, настоящий вопрос:
Я бы либо
1.) Алгоритм упрощения полилиний, который ускоряет работу вышеупомянутого алгоритма, но при этом гарантирует оптимальное решение
ИЛИ ЖЕ
2.) Если некоторые из вас, ребята, знают совершенно другой алгоритм, который решает проблему точно и быстро, я тоже открыт для него:)
Я знаю, что проблема может быть решена, так как я видел программное обеспечение, которое делает это менее чем за 1 секунду на моем ПК (который является довольно обычным компьютером), я просто не знаю, как это работает:)
Мне нужно сделать это в C#, но, конечно, любой псевдокод приветствуется:)
Заранее спасибо.
Ура, Ласло