Есть сетка, содержащая числа 0 и 255. 0- это пустая ячейка, 255- ячейка по которой "можно пройти".
Дается точка. Задача- найти координаты границы внешнего контура, который содержит эту точку. Методы обхода могут быть 4-х шаговый и 8-и шаговый. 
4-х шаговый, это когда от точки мы можем "пойти" вверх, вниз, влево, вправо.
8-и шаговый- от точки по всем направлениям.

Если входная точка 0, то ничего не делать.

Как найти просто все точки контура я знаю. А надо найти именно внешние точки.
Помогите плз...

Это сообщение отредактировал(а) SoWa - 25.3.2007, 15:31

а рисуночек можно?

И по точнее, что значит


контур же непрерывен. какую границу нужно найти? или контур прямоугольный?

0   255   255   255   255 0 0
0   255   255   255   255 0 0
0   255   255   255   0     0 0
0     0      0        0     0     0 0

Допустим, начинаем в точке 1,1
Контур это координаты точек, кторые образуют ломаную, ограничивающую все точки, вошедшие в контур. Ну как заливка в графических редакторах. Только мне надо не залить, а найти границу заливки.

В этом случае будут клетки с координатами
1,0 _ 2,0 _ 3,0 _ 4,0 _ 1,1 _ 1,2 _ 2,2 _ 3,2 _ 4,1

Добавлено через 1 минуту и 22 секунды
Их то и надо найти. Вот как бы из залички получить контур, ведь заливка 8-и шаговой системой может быть пористая.

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

Добавлено через 1 минуту и 34 секунды
ну и стоит перед всеми этими действиями добавить рамочку цвета 0

Я такую задачу уже решал и вот как:
1. Сначала будем выбирать точки по Х.
    1.1 Устанавливаем флаг=Матрица[0][0] 
    1.2 Делаем цикл по Х (переменная i)
       1.2.1 Если значение Матрица[ i ][ j ] != флаг:
             1.2.1.1 Меняем флаг на Матрица[ i ][ j ]
             1.2.1.2 Изменяем Матрица[ i ][ j ] = 128 (или любое другое значение);  
    1.3 Повторяем шаг 1.2 для каждой строки матрицы

2. Делаем то же самое, только для точек по Y (для столбцов)
3. Всё, что в Матрице = 128 - контур

Надеюсь, не сильно запутал )))

Могу написать пример на Delphi7, если нужно

Bitter, можно Дельфийский код, а то запутано 
maxim1000, как всегда гениально! Одно НО- это жд 4-х шаговой системы проедет. А для 8-и нет. Потому что может быть пора, которую мы не зальем цифрой 128. А вообще это плюс ;)

это подойдёт для любого соседства: хоть 8, хоть 4, хоть 6
главное, чтобы одно и то же использовалось и в заливке, и в выделении границы

Нет, вот такая фигура(для простоты 1 и 0)
0 0 0 0 0 0 0
0 1 1 1 1 1 1
0 1 0 1 0 1 1
0 1 1 1 1 1 1
0 0 0 0 0 0 0

начнм в (3,3)
и точка (2,2) это пора. Если мы будем смотреть точку (5,2) то она по твоему условию тоже окажется контурной. Или ты предлагал даже поры заливать?

Вот код обхода контура по 8-соседям на С++.
Это классический обход "жучком": он не требует нанесения пометок на растр, осматривает только точки границ и их соседей. 
Для текущей точки контура, проверяем соседей и берем первую же точку, которая удовлетворяет условию принадлежности к границе. Чтобы все сошлось, нужно правильно выбрать начальную точку осмотра (а это зависит от предыдущей). В общем, см. код. Предикат IsOk должен отвечать на вопрос, является ли точка непустой.
Граница, вроде бы, получается 4-связная.


Присоединённый файл ( Кол-во скачиваний: 10 )
 trace.rar 2,00 Kb

ааааа... в этом смысле
тогда надо поточнее описать, что подразумевается под внешним контуром
предварительно - заливаем из какой-нибудь точки на рамочке цветом 64 и ищем клеточки цвета 128 с соседями 64, правда, если один контур будет вложен в другой, таких точек не будет
тогда можно делать так:
1. заливаем цветом 128, смотрим, есть ли соседи с 64
2. если есть - значит, задача решена - этот контур внешний
3. если нет, то заливаем область 255 тоже цветом 128, т.к. она, на самом деле, внутренняя
4. находим область вокруг неё цвета 0 и тоже заливаем
5. повторяем 2..4 для каждого слоя
так рано или поздно доберёмся до внешнего слоя...

Ага, точно!
Спасибо большое!

//А еще я нашел забавную штуку "Алгоритм Жука(Колорадского :hehe)"

Вот код, который обещал:



Вот пример:


Присоединённый файл ( Кол-во скачиваний: 7 )
 Kontur.rar 7,52 Kb

а вот как пример работает )))


Присоединённый файл ( Кол-во скачиваний: 21 )
 Primer.JPG 55,58 Kb