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

Это сообщение отредактировал(а) DemonVex - 30.5.2009, 15:46

Присоединённый файл ( Кол-во скачиваний: 30 )
 2009_05_30_153126_cr.png 3,00 Kb

есть такая процедура - скелетизация (skeletonization)
в результате для замкнутого контура получится последовательность точек, каждая из которых имеет по два соседа, так что пройтись будет довольно-таки просто: запоминаем, откуда пришли, и туда не идём, тогда остаётся ровно один сосед, куда и нужно идти

Немного другой метод знаю. Суть там в поворотах налево или направо. Начинаем в точке контура. Если черная, то поворачиваем влево, если белая, то вправо. Таким образом змейкой обходим контур.

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

Это сообщение отредактировал(а) DemonVex - 31.5.2009, 08:31

а мне, кстати, метод, описанный cardinal больше нравится 
скелетизация требует прохода по всему изображению несколько раз, оптимизировать, конечно, можно, но так или иначе будет выполняться значительно больше работы

во втором методе будет обработано ровно столько точек, сколько нужно, не нужно будет дополнительной памяти (для скелетизации без неё у меня обойтись не получалось)

так что если анализ не пойдёт дальше обхода контура, то лучше вторым методом
скелетизация будет полезна, если нужен более широкий анализ, например, где происходят ветвления линий

Попробую реализовать второй алгоритм. Посмотрю на устойчивость в этой задаче.

Это сообщение отредактировал(а) DemonVex - 31.5.2009, 13:43

maxim1000, 
Для скелетизации не нужно проходить все изоброжение много раз. Есть волновой алгоритм скелетизации.
http://ocrai.narod.ru/vectory.html

Причем позовершению работы будем иметь не только скелет, но и обойденный контур.

Рекомендую правосторонний (левосторонний) обход. Принцип элементарный. Сканируем матрицу пикселов пока не встречаем черный (но сами остаемся на белом). Дальше начинаем обход
1. Запоминаем свои координаты.
2. Если можно двигаться в текущем направлении, то перемещаемся на один пиксель (двигаемся только по белым точкам) и поворачиваемся (на месте, просто изменяем направление) по часовой стрелке на 90 градусов. А в противном случае (если двигаться не можем) то поворачиваемся на 90 градусов против часовой стрелки.
3. После каждого перемещения, проверяем не вернулись ли мы в исходную точку. Если нет, то переходим к пункту 2, иначе конец.
Все.
Реализуется в 5 строчек.

LOD77 расписал по пунктам то, что я предложил пару постов выше...