Минимизация подъема пера в плоттере пера или подобном устройстве

Question

Я ищу ссылки на алгоритмы для черчения на механическом ручном плоттере.

В частности, у меня есть список прямых векторов, каждый из которых представляет линию для построения. Сначала я хочу удалить повторяющиеся векторы, чтобы каждая линия отображалась только один раз. Это достаточно просто.

Во-вторых, есть много векторов, которые пересекаются, иногда в конечных точках, но не всегда. Они могут быть нанесены в любом порядке, но я хочу найти порядок, который уменьшает количество раз, когда ручка должна быть поднята, предпочтительно до минимума, хотя я понимаю, что это может занять много времени, если вычисление вообще. Пересекающиеся векторы можно разбить на более мелкие векторы, если это поможет. Но, как правило, если ручка движется по прямой линии, лучше держать ее так долго, насколько это возможно. Таким образом, два параллельных вектора, соединенных друг с другом, могут быть объединены в один вектор и т. Д.

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

Спасибо

Neil

Answer 1

Проблема является примером китайской проблемы почтальона , которая является NP-полной задачей.Самая известная проблема с NP-завершением - Путешествующий продавец .Общим для всех NP-полных проблем является то, что все они могут быть переведены друг на друга.Не существует известных алгоритмов для решения любого из них за время, которое является полиномиально зависимым от числа узлов на входе, они являются неполиномиальными (NP).

Для вашего случая я бы предложил несколько простых эвристик,Не переусердствуйте, просто выберите что-нибудь очень простое, например, как можно длиннее по прямой линии, а затем поднимите ручку до ближайшей доступной начальной точки и продолжайте оттуда.