У меня есть черно-белое (бинарное) изображение. Он содержит набор черных пятен, окруженных белыми. Я пытаюсь написать программу на С#, которая найдет единственный путь, пересекающий всю затененную область, оставляя при этом как можно больше белой области. Это очень похоже на поиск траектории головки инструмента для 3D-принтера для любого заданного слоя; ему нужно заполнить твердые части, а переходить в пустое пространство только тогда, когда ему нужно добраться до другого отдельного шарика.
Например, вот тестовое изображение, которое я создал, которое включает в себя большинство проблем, с которыми я сталкиваюсь (для простоты только с двумя каплями):
Я хотел бы найти путь, который пересекал бы все черные области, но только один раз пересекал белую, чтобы прыгать между двумя фигурами (там, где они ближе всего). Я также хотел бы, чтобы путь был как можно короче.
Моя программа написана на C#, и я уже использую AForge для обработки изображений до этого момента, так что у меня уже есть это.
До сих пор самое близкое, что я получил, было с алгоритмом, похожим на заливку. Он начнется с угла и найдет ближайший пиксель (сначала по горизонтали, затем по вертикали), чтобы продолжить путь. Но пути не всегда вели повсюду, и пересечение обычно создавало длинный и в значительной степени посторонний путь. Я также пытался отслеживать края и двигаться внутрь, но это все еще не очень хорошо работало, когда у капли был непрямой путь. Поиск тоже ничего не дал; Я пытался искать что-то, связанное с алгоритмами 3D-печати, заливкой и т. д., но ничего не нашел.
Итак, как мне решить эту проблему?
