Алгоритм выделения в массиве элементов внутри контура

[Aleexeey]

Здрасте, уважаемые члены форума.
подкиньте хотя-бы идейку в правильном направлении, а то запарился.
Проблема такая:

дан массив, например такой:

0000111100111100000
0000100100100100000
1111100100100100000
1000000101100110000
1110000101000010000
0010000111000010000
0011000000000010000
0001000011111110000
0001111110000000000
уф, устал  ну теперь видно красный контур

в нем нужно определить какая ячейка находится внутри этого периметра, а что вне!
т. е. должно получиться так:

0000111100111100000
0000122100122100000
1111122100122100000
1222222101122110000
1112222101222210000
0012222111222210000
0011222222222210000
0001222211111110000
0001111110000000000

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

[Вад]

Есть мысль идти обходить контур в любом направлении и считать правые и левые повороты. В какую сторону поворотов будет больше - та сторона внутренняя.

[Sla]

преобразовать строку в массив

[Aleexeey]

хотя бы возиметь представление псевдокода что-то не могу это реализовать  , уж запарился. 

[Вад]

Aleexeey, находишь первую точку на контуре, запоминаешь её и далее шагаешь по контуру, пока не достигнешь точки старта. Попутно запоминаешь направление движения, и если оно изменяется (а оно может измениться только под прямым углом вправо или влево) - вычисляешь, в какую сторону был совершён поворот, инкрементируешь счётчик.
Когда поймёшь, с какой стороны от контура находится внутренняя область, можно заполнять эту область 2ками рекурсивно.

[Aleexeey]

Вад, спасибо за идею  , шас попробую!

[Вад]

Есть второе решение, ещё проще Расширить границу - т.е. добавить по 1 справа, слева, сверху и снизу. А затем отмечать точки рекурсивно из любого угла - тогда все внешние точки окажутся отмечены, остальные - внутренние.
Первое, кстати, страдает одним недостатком: сложные внутренние области (если контур "восьмёркой").

[Sla]

Задача аналогична задаче заливке контура

два вида границ - контур и "граница" массива
залить цветом - заливать волной до границ.

[LightSin]

мысль одна ... .  у тебя массив получается 2 ух мерный в общем какая разница над разбить его по строкам
0000111100111100000
теперь намути цикл
примерн такой
 for перечелсяем каждую 0 000111100111100000)
потом условие иф 1   то х=номер массива иль переменной в цикле:
эт у нас левый край теперь нужен правый еще раз в томже цикле верней после 1 услов иф 1 то y=номер массива
а теперь переберай все элементы тоесть выводи на экран иль новый массив от  a [ x ]  до  a [ y ] 
гглавн массив четк задать for от х до y там прост если будет 1 и следом 1 чтоб не чего не брал а в остальных случаях 1---0---1 а надеюсь просек

[LightSin]

хмм а можно еще тип проще
 
 не помню точн фунцию на  смену цвета шрифта найдеш:)

разделяем твой массив на строки


0000111100111100000

пускаем For от начало до конца
и в цикле тип
if 1 нашли цифру
делаем тип условие так выгледить должно
если цвет  красный то делаем белый
если цвет белый то делаем красный
надеюсь догнал
 там  кода массив на экран кидаеш через cout<< тоесть режим цвета спец настройки

в общем смотря что те над если ток вывести на экран то эт кул

[Джон]

А я согласен со Славой. В строке до границы ничего не меняется, потом заливаем всё пока граница не поменяется. Условие границы - переход 0 в 1 и 1 в 0.
         

[Aleexeey]

LightSin я подобно уже делал, такой алгоритм, в некоторых случаях,
не может распознать некоторые формы т. е. отделить внешнюю от внутренней, или я ошибаюсь?

Вот например, как с заливкой в этой ситуации, если читать построчно:
0000100100100100000 (вторая строка моего примера)
идут по очереди 0, 1, 0, 1 - как узнать какой ноль заменить двойкой!
т. е. должна строка стать такой:
0000122100122100000

[Aleexeey]

Sla преобразовать строку в массив, это не задача 

эта заливка контура как может выглядеть в псевдокоде?
я так понимаю, это как в Paint заливка, тока как она выглядит в коде?
Просто меня смущает определение нуля, какой он внешний или внутри контура.

[Aleexeey]

Вад
вот кусок наброска:

         двигаться вверх  /\ = 3
двигаться налево=2 <-| |-> двигаться направо=0
            двигаться вниз \/ =1

Код:

int body[171] = {
0,0,0,0,1,1,1,1,0,0,1,1,1,1,0,0,0,0,0,
0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,
1,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,0,0,1,0,1,1,0,0,1,1,0,0,0,0,
1,1,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,
0,0,1,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,
0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
0,0,0,1,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,
0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0}; // это тот-же массив

Код:

int trend = 0; // начальное направление ->
int lengthX = 19; // количество ячеек по оси X
int lengthY = 9; // количество ячеек по оси Y
for (int posY = 0; posY < lengthY; posY++) // цикл движения по оси Y
{
      for (int posX = 0; posX < lengthX; posX++) // цикл движения по оси X
      {
            int value = body[posX*(posY+1)]; // получаю значение массива
            if (value == 1)
            { // нашел границу контура
             ...
            }
      }
}

э-э-э, что-то я туплю, как внедрить это направление?

[Алексей++]

Aleexeey, вот это тебе поможет рисовать, а может и алгоритмы повыдергаешь
https://club.shelek.ru/download.php?id=251

правда там заливка не до определённого цвета, а заливка области

[Aleexeey]

Алексей1153++, спасибо, сейчас посмотрю!

[Джон]

Просто меня смущает определение нуля, какой он внешний или внутри контура.

Всё очень просто. Если у тебя контур, то границ толщиной в единицу быть не может. Значит условие такое:

переход 0 в 1 - начало границы первый же после него переход 1 в 0 начало внутренней части контура (заливка). заливаем до границы 0 в 1. Цикл замкнулся.

зы Да забыл написать, за картинки в первом посте - респект.  Долго трудился?

[Антон (LogRus)]

Джон, а теперь разрушим стройное решенье


0000111100111100000
0000122100122100000
1111222100122100000
2222222101122110000
1122222101222210000
0012222111222210000
0011222222222210000
0001222211111110000
0001111110000000000

и что будем делать?

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

[Aleexeey]

LogRus, это точно,
    1) непрерывный
    2) без пересечений,
и вроде все!

[Aleexeey]

Алексей1153++, я посмотрел программу, изучил приложенную справку, все клева! 
Просто супер, только заливка игнорируя все цвета, беспощадно все заливает,
(мож ее назвать clear или clean, и добавить заливку цвета? типа этой темы  )

И еще вопрос не по теме, как в форуме применять? горю желанием галерею картинок разместить 

[Aleexeey]

Джон, это выход! такое условие на самом деле определит верно!
А как в такой ситуации:

0001000
    |/\|
    \  \
     \  переход из 1 в ноль
      переход из нуля в 1

ну тут например разобрались использовав доп. перем., а теперь:

0000000000000000000000
0000001110001110011100 - алгоритм точно зальет эти нули
0000001010001010010100 - здесь ОК (условие выполняется)
0000001011111011110100 - вроде тоже
0000001000000000000100 - здесь ОК
0000001111111111111100 - вроде тоже
0000000000000000000000

[Алексей++]

Aleexeey, подробности тут https://forum.shelek.ru/index.php/topic,885.0.html  ) Проект давний и поэтому с корявым кодом, если появится желание - переписывай исходники )

[Вад]

А если поместить на край и добавить единиц?
0000000000000000
1110001110011100
1011011010010100
1001110011110100
1000000000000100
1111111111111100

и т.д.?

[Алексей++]

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

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

[Вад]

Алексей1153++, вот это больше похоже на правду Но что считать пересечением? Ведь во 2й строке моего примера нет точек, лежащих внутри.

[Алексей++]

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

только это тоже не поможет. Надо как-то определять вершины и все их учитывать, потому что будет случай, когда есть локальный максимум или минимум ...

[Вад]

А как быть с контуром

111111
101101
101101
100001
111111

[Алексей++]

а ещё вариант: не только строку просканировать, но и столбец Если в обоих случаях истина, то точка внутри

[Aleexeey]

Точно! и опять, таки если в каком то направлении точка пересекается несколько раз,
или где-то пойдет по контуру!?

[Алексей++]

>>точка пересекается несколько раз
 - это как ? )

>>где-то пойдет по контуру!?
  отодвинуть фигуру от края "экрана"