Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2  Все   Вниз
  Печать  
Автор Тема: Алгоритм выделения в массиве элементов внутри контура  (Прочитано 54433 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Aleexeey
Постоялец

ru
Offline Offline

« : 10-12-2008 13:40 » 

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

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

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

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

0000111100111100000
0000122100122100000
1111122100122100000
1222222101122110000
1112222101222210000
0012222111222210000
0011222222222210000
0001222211111110000
0001111110000000000

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

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 10-12-2008 13:55 » 

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

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 10-12-2008 13:55 » 

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Aleexeey
Постоялец

ru
Offline Offline

« Ответ #3 : 10-12-2008 14:00 » 

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

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 10-12-2008 14:10 » 

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

ru
Offline Offline

« Ответ #5 : 10-12-2008 14:14 » 

Вад, спасибо за идею  Класс!, шас попробую!
Записан
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 10-12-2008 14:20 » 

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

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 10-12-2008 14:33 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
LightSin
The question title sounds to me the same as "Convert banana into a pistol"... :-)
Постоялец

ru
Offline Offline
id/fm105


« Ответ #8 : 10-12-2008 15:07 » 

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

Lost in the jungle: 1c, PIC AVR, C++, Python flask, (no Java) JS . for fun: Live For Speed S2 Drift Edition, TeeWorlds
LightSin
The question title sounds to me the same as "Convert banana into a pistol"... :-)
Постоялец

ru
Offline Offline
id/fm105


« Ответ #9 : 10-12-2008 15:18 » 



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

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


0000111100111100000

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

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

Lost in the jungle: 1c, PIC AVR, C++, Python flask, (no Java) JS . for fun: Live For Speed S2 Drift Edition, TeeWorlds
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #10 : 10-12-2008 15:28 » 

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

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Aleexeey
Постоялец

ru
Offline Offline

« Ответ #11 : 10-12-2008 16:31 » 

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

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


Записан
Aleexeey
Постоялец

ru
Offline Offline

« Ответ #12 : 10-12-2008 16:40 » 

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

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

ru
Offline Offline

« Ответ #13 : 10-12-2008 17:07 » 

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

         двигаться вверх  /\ = 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)
            { // нашел границу контура
             ...
            }
      }
}

э-э-э, что-то я туплю, как внедрить это направление?
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #14 : 10-12-2008 18:13 » 

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

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

Aleexeey
Постоялец

ru
Offline Offline

« Ответ #15 : 10-12-2008 18:20 » 

Алексей1153++, спасибо, сейчас посмотрю!
« Последнее редактирование: 11-12-2008 06:07 от Aleexeey » Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #16 : 10-12-2008 20:18 » 

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

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

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

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

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #17 : 11-12-2008 05:48 » 

Джон, а теперь разрушим стройное решенье Улыбаюсь


0000111100111100000
0000122100122100000
1111222100122100000
2222222101122110000
1122222101222210000
0012222111222210000
0011222222222210000
0001222211111110000
0001111110000000000

и что будем делать? Улыбаюсь

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

Странно всё это....
Aleexeey
Постоялец

ru
Offline Offline

« Ответ #18 : 11-12-2008 06:11 » 

LogRus, это точно,
    1) непрерывный
    2) без пересечений,
и вроде все!
Записан
Aleexeey
Постоялец

ru
Offline Offline

« Ответ #19 : 11-12-2008 06:20 » 

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

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

ru
Offline Offline

« Ответ #20 : 11-12-2008 06:42 » 

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

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

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

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

ru
Offline Offline
Сообщений: 13


« Ответ #21 : 11-12-2008 06:47 » 

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

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #22 : 11-12-2008 06:47 » 

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

и т.д.?
« Последнее редактирование: 11-12-2008 06:57 от Вад » Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #23 : 11-12-2008 06:54 » 

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

На строке с точкой определяем, где происходит пересечение строки с контуром. Если было нечётное количество пересечений, и затем шла точка, значит точка в контуре
« Последнее редактирование: 11-12-2008 06:57 от Алексей1153++ » Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #24 : 11-12-2008 06:59 » 

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

ru
Offline Offline
Сообщений: 13


« Ответ #25 : 11-12-2008 07:11 » 

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

только это тоже не поможет. Надо как-то определять вершины и все их учитывать, потому что будет случай, когда есть локальный максимум или минимум ...
« Последнее редактирование: 11-12-2008 07:12 от Алексей1153++ » Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #26 : 11-12-2008 07:16 » 

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

111111
101101
101101
100001
111111
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #27 : 11-12-2008 07:29 » 

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

Aleexeey
Постоялец

ru
Offline Offline

« Ответ #28 : 11-12-2008 07:33 » 

Точно! и опять, таки если в каком то направлении точка пересекается несколько раз,
или где-то пойдет по контуру!?
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #29 : 11-12-2008 07:39 » 

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

>>где-то пойдет по контуру!?
  отодвинуть фигуру от края "экрана" Улыбаюсь
Записан

Страниц: [1] 2  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines