Учитывая список отрезков, мне нужно составить список полилиний, сохраняя при этом количество полилиний минимальным.
Полилинии не должны посещать один и тот же край более одного раза.
Например, если бы мне дали 4 ребра прямоугольника, то одной полилинии было бы достаточно.
Если бы мне дали 6 ребер прямоугольника с крестом посередине, мне бы понадобились две ломаные линии, чтобы покрыть его.
Эта проблема очень похожа на проблему коммивояжера, поэтому я не уверен, что решение существует. Я могу жить с неоптимальным решением в этом случае.
Edit:
Производительность для нас важнее точности, поэтому в идеале мы хотели бы сгруппировать те, которые почти соединяются (на расстоянии 1-2 пикселя), в одну ломаную линию
Примеры:
вход для квадрата:
L (0, 0) - (0, 1), L (0, 1) - (1, 1), L (1, 1) - (1, 0), L (1, 0) - (0, 0 )
Ожидаемый результат: полилиния (0, 0), (0, 1), (1, 1), (1, 0), закрытие
ввод для квадрата с X:
L (0, 0) - (0, 1), L (0, 1) - (1, 1), L (1, 1) - (1, 0), L (1, 0) - (0, 0 ), L (0, 0) - (1, 1), L (1, 0) - (0, 1)
Один из возможных выходных данных: Polyline1 (0, 0), (0, 1), (1, 1), (1, 0), (0, 0), (1, 1) Polyline2 (1, 0), (0, 1)
- вход для линий, близких друг к другу:
L (0, 0) - (1, 0), L (2, 0) - (3, 0)
Идеальный результат: полилиния (0, 0), (3, 0)