Я работаю с большим количеством координат в 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)]
Вот изображение для описания Желаемая оптимизация:
Координаты всегда будут располагаться прямо на одной из осей. Диагональные линии можно игнорировать.
Было бы здорово, если бы кто-нибудь дал мне подсказку о том, как добиться этого эффективным способом. Мне нужно многократно запускать алгоритм оптимизации, поскольку путь генерируется процедурно.