Поиск единственного пути для заполнения всех затененных областей изображения в C#

Question

У меня есть черно-белое (двоичное) изображение. Он содержит множество черных капель, окруженных белыми. Я пытаюсь написать C# -программу, которая найдет единственный путь для пересечения всей затененной области, при этом пропуская как можно большую часть белой области. Это очень похоже на поиск траектории головки инструмента для 3D-принтера для любого данного слоя; он должен заполнить твердые части, при этом переходя только в пустое пространство, когда ему нужно добраться до другого отдельного блоба.

Например, вот созданное мной тестовое изображение, которое включает в себя большинство проблем, с которыми я сталкиваюсь (для простоты всего два шарика):

Я хотел бы найти путь, который пересекает все черные области, но только один раз пересекает белые, чтобы перепрыгнуть между двумя фигурами (где они находятся ближе всего). Я также хотел бы, чтобы путь был максимально коротким.

Моя программа написана на C#, и я уже использую AForge для манипулирования изображениями до этого момента, поэтому у меня уже есть это доступно.

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

Итак, как мне решить эту проблему?

Answer 1

1. заполнение капель

   • они просто заполнены многоугольником
   • преобразовать их в набор замкнутого выпуклого многоугольника
   • или триангулировать это
   • затем визуализировать как заполнение замкнутого многоугольника + растеризация треугольника / выпуклого многоугольника
   • стенд использовать ту же растеризацию
   • так что вы получите набор горизонтальных / или вертикальных линий (зависит от того, как вы его кодируете)
   • так что просто соедините их вместе в одну полилинию
   • Есть и другие способы заполнения, но этот самый простой и подвержен ошибкам.

2. движения между каплями

   • это действительно TSP, который является законченным NP (см. ответ mcdowella)
   • обрабатывать все замкнутые полигоны как отдельные объекты
   • использовать эвристику (объединять капли в непосредственной близости)
   • ограничить длину движения в качестве критерия решения

Answer 2

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

Это говорит мне о том, что вы определяете наименьшее расстояние между всеми парами черных областей, а затем используете приближенное решение задачи коммивояжера на этой матрице расстояний. Поиск находит алгоритм наименьшего расстояния, описанный по адресу http://cgm.cs.mcgill.ca/~orm/mind2p.html. Алгоритмы аппроксимации TSP, которые приходят на ум, основаны на http://en.wikipedia.org/wiki/Minimum_spanning_tree и на битовых турах - например, в http://www.cs.helsinki.fi/u/jwkangas/daaa2013/sol-II.pdf.