monday2000
Silver Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Разобрался я с этим rectangularizeAreas. Алгоритм оказался довольно изощрённым. 
Он работает с чёрно-белой маской автозон. Суть примерно такая:
Алгоритм работает не с отдельными пикселями, а с "пятнами" - размером в 32-битное слово. Так и быстрей, и проще.
Обходит в бесконечном цикле всю маску - дойдя до конца переходит на начало и так бесконечно.
Внутри цикла: находит все пятна, внутри каждого из которых есть хотя бы один пиксель зоны. Строит глобальный список пятен.
Одновременно пробует увеличить каждое пятно в 1,5 раза - во все стороны - и смотрит, не пересекается ли увеличенное пятно с каким-нибудь соседним. Если пересекается - то 2 этих пятна сливаются в одно, и результат кладётся в глобальный список пятен, если нет - то идёт дальше.
При этом при каждом акте слияния устанавливается глобальный флаг "слияние произошло". Этот флаг служит условием выхода из бесконечного цикла: когда рано или поздно слияния перестанут происходить - то бесконечный цикл прервётся, и это будет окончанием работы алгоритма.
Только защиты от зацикливания я не увидел - впрочем, вариант полного отсутствия слияний выглядит невероятным.
Ясно, что такой алгоритм правильно сохранит количество зон на скане: допустим, если было 2 авто-зоны - то он их не сольёт в одну.
Что мне в нём не очень нравится - так это то, что полученный контур всегда заметно больше, чем исходная зона. Это определяется как микронеровностями контура исходной зоны, так и самим характером алгоритма, где минимальная оперируемая единица - это не один пиксель, а 16 (приращение пятна).
Потом бывают ещё такие картинки, которые хотя и прямоугольные, но количество углов у них больше 4-х.
Такие картинки алгоритм выделяет простым прямоугольником - а в некоторых книгах их немало. |
Всего записей: 2841 | Зарегистр. 13-01-2005 | Отправлено: 20:25 18-03-2013 | Исправлено: monday2000, 20:34 18-03-2013 |
|
