Не зацикливайтесь на отдельных пикселях. Сфокусируйтесь на углах пикселей - точках, где встречаются четыре пикселя. Координаты этих углов будут работать как полуоткрытые координаты пикселей. Полуоткрытые границы включаются на нижней границе, но исключают на верхней границе, поэтому полуоткрытый диапазон от одного до трех равен {1, 2}.
Определение набора ребер - однопиксельных длинных линий (вертикальных или горизонтальных) между двумя пикселями. Затем сформируйте граф смежности - два ребра смежны, если они разделяют точку.
Затем определите связанные наборы ребер - подграфы, где каждая точка связана, прямо или косвенно, с любой другой. Логически, большинство связанных подграфов должны образовывать замкнутые циклы, и вы должны убедиться, что ВСЕ циклы считаются простыми замкнутыми циклами.
Одна проблема - это край вашего растрового изображения. Это может упростить ситуацию, если вы представите, что ваше растровое изображение представляет собой небольшую часть бесконечного растрового изображения, где каждый выходящий за пределы пиксель имеет значение 0. Включите края пикселей на краю растрового изображения на основе этого правила. Это должно гарантировать, что все петли закрыты.
Кроме того, рассмотрите те углы пикселей, где у вас есть четыре граничных ребра - то есть где шаблон пикселя является одним из ...
1 0 0 1
0 1 1 0
В этих случаях пиксели '1' следует рассматривать как часть отдельных многоугольников (в противном случае вы столкнетесь с усложнением правила намотки). Измените правила смежности в этих случаях так, чтобы вы в основном получили два связанных (прямоугольных) ребра, которые случайно соприкасаются в точке, но не считаются смежными. Они все еще могут быть связаны, но только косвенно, через другие края.
Кроме того, используйте дополнительные массивы флагов для определения краев пикселей, которые уже использовались в циклах - возможно, один для горизонтальных краев, один для вертикальных. Это должно упростить поиск всех циклов без повторной их оценки - вы сканируете свое основное растровое изображение и, обнаруживая соответствующий край, проверяете эти массивы перед сканированием, чтобы найти весь цикл. Когда вы сканируете цикл, вы устанавливаете соответствующие флаги (или номера идентификаторов цикла) в этих массивах.
Кстати, не думайте, что все эти шаги - это буквальные шаги построения структуры данных, а скорее как уровни абстракции. Ключевым моментом является осознание того, что вы выполняете операции graph . Вы могли бы даже использовать адаптер, который ссылается на ваше растровое изображение, но предоставляет интерфейс, подходящий для непосредственного использования некоторого алгоритма графа, как если бы он использовал специализированную структуру данных графа.
Чтобы проверить, является ли конкретный цикл дырой или нет, выберите (например) крайний левый вертикальный край пикселя (в цикле). Если пиксель справа заполнен, петля является границей многоугольника. Если пиксель слева заполнен, петля является дырой. Примечание. Хороший тестовый пиксель - это, вероятно, тот, который вы нашли, когда нашли первый край пикселя, перед тем как обвести контур. Это может быть не самый левый такой край, но он будет самым левым / самым верхним в этой строке сканирования.
Последняя проблема упрощается - определение, где края пикселей сходятся в прямые линии. Это, вероятно, может быть встроено в сканирование, которое в первую очередь идентифицирует цикл, но, вероятно, лучше всего найти угол перед началом сканирования. После этого каждая строка идентифицируется с помощью цикла «пока я могу продолжить трассировку в одном направлении», но следите за проблемами, касающимися двух полигонов, соприкасающихся в углу.
Попытка объединить все это может звучать как сложный беспорядок, но хитрость заключается в том, чтобы разделить проблемы на разные классы / функции, например, используя классы, которые предоставляют абстрактные представления нижележащих слоев, таких как ваше растровое изображение. Не беспокойтесь слишком сильно о накладных расходах на вызовы или оптимизации - встроенная и другая оптимизация компилятора должна справиться с этим.
Что было бы действительно интересно, так это более интеллектуальная трассировка, которую некоторые программы векторной графики делали уже некоторое время, где можно получить диагонали, кривые и т. Д.