Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Задаются координаты вершин многоугольника в порядке обхода
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Julia_L Julia_L вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.09.2005
По умолчанию Задаются координаты вершин многоугольника в порядке обхода - 26.09.2005, 23:57

Доброго всем времени суток. Есть такая хитрая задачка :
Задаются координаты вершин многоугольника в порядке обхода, если есть самопересечния, то залить области получившиеся в рез-те самоперес-ий разными цветами. Пример: Звезда и каждая её часть отдельным цветом.
Подскажите пожалуйста как решить ?
Ответить с цитированием
  (#2 (permalink)) Старый
yureckor yureckor вне форума
Member
 
Сообщений: 462
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.03.2004
По умолчанию 27.09.2005, 09:52

математические методы можно придумать, но можно по программерски
рисуешь многоугольник, делаешь цикл сканирования точек по экрану, если цвет фона то запускаешь заливку, если это не фон (уже залито или контур) то дальше. После заливки изменяешь цвет, которым будешь заливать в следующий раз.
Ответить с цитированием
  (#3 (permalink)) Старый
Julia_L Julia_L вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.09.2005
По умолчанию 27.09.2005, 12:38

легко сказать залей...а как вы это представляете в Pascal'е или C++, это ведь вам не Paint !! что заливать если неизвестны координаты той области в которой находится сканируемая точка?? если же заливать по точкам то трудно будет определить в какой части каким цветом заливать , так как пересечений может быть беспорядочное множество... а вообще я думаю тут без математики не обойтись... вот только как ?
Ответить с цитированием
  (#4 (permalink)) Старый
yureckor yureckor вне форума
Member
 
Сообщений: 462
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.03.2004
По умолчанию 27.09.2005, 17:23

Цитата:
легко сказать залей...а как вы это представляете в Pascal'е или C++, это ведь вам не Paint !!
алгоритм заливки области легко найти

Цитата:
что заливать если неизвестны координаты той области в которой находится сканируемая точка??
мда...

Цитата:
а вообще я думаю тут без математики не обойтись... вот только как ?
Думать надо когда алгоритм разрабатываешь. Если спрашиваешь на форуме, то тогда думать надо над ответом.
Ответить с цитированием
  (#5 (permalink)) Старый
igora112 igora112 вне форума
Новичок
 
Сообщений: 9
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.09.2005
По умолчанию 27.09.2005, 19:10

вообще-то нужно точно определиться: нужно получить на выходе множество областей (математическое решение) и потом рисовать и красить или же искать графическое решение (заливка областей). заливка на вид попроще будет, если память не изменяет, то бывают
встроенные функции заливки областей именно уже отрисованных на экране (как в паинте). да, и еще, важно знать ограничения на координаты отрезков. если координаты - это произвольные действительные (дробные) числа, то графический метод неприменим, а если координаты целые числа, скажем, от 0 до размера экрана по X и Y в пикселах, то можно и графически задачу решить...
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Julia_L Julia_L вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.09.2005
По умолчанию 27.09.2005, 20:26

Любителей краснословить и придираться к фразам попрошу оставить свои амбиции при себе и читать сообщения внимательней. Мне нужно хоть что-то внятное по теме... а то что в сети есть системы поиска это я и сама знаю.
Ответить с цитированием
  (#7 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 27.09.2005, 20:38

Цитата:
Originally posted by Julia_L
[b]Любителей краснословить и придираться к фразам попрошу оставить свои амбиции при себе и читать сообщения внимательней. Мне нужно хоть что-то внятное по теме... а то что в сети есть системы поиска это я и сама знаю.
Julia_L, пожалуйста, сбавь тон.
Коллеги, давайте жить дружно!

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

Если это не по теме, то постарайся переформулировать постановку задачи. Если по теме - напиши, на чём следует остановиться подробнее.
Ответить с цитированием
  (#8 (permalink)) Старый
Julia_L Julia_L вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.09.2005
По умолчанию 27.09.2005, 21:42

Вся сложность заключается в поиске координат областей. Допустим точки самопересечений многоугольников найдены, дальше тупик..
Нужен конкретный алгоритм поиска.
Ответить с цитированием
  (#9 (permalink)) Старый
igora112 igora112 вне форума
Новичок
 
Сообщений: 9
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.09.2005
По умолчанию 28.09.2005, 13:39

если я правильно понял, то мы уже имеем множество отрезков из которых состоит закрашиваемая фигура, тогда, например, рекурсивно:

1. выделяем самый большой многоугольник, объемлющий в себе все остальные отрезки и состоящий из данных отрезков. выполняем для него шаг 2.

2. проверяем, содержит ли данный n-угольник путь, разбивающий его на 2 части. если нет, то смело закрашиваем его и возвращаемся на уровень выше. если содержит, то по очереди выполняем шаг 2 для каждого из двух полученных многоугольников...
Ответить с цитированием
  (#10 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 28.09.2005, 17:21

Было бы очень хорошо, если можно сначала нарисовать на чем-либо многоугольник, а потом сканировать изображение. Тогда можно просто просматривать построчно и рисовать разноцветные линии между каждыми двумя точками цвета многоугольника.
Ответить с цитированием
  (#11 (permalink)) Старый
Olesya Olesya вне форума
Member
 
Сообщений: 1,485
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.06.2002
По умолчанию 28.09.2005, 17:41

Как на меня логично было найти поначалу токи пересечиния. Это не проблема. Эти точки будут узловыми. Таким образом приходим к свому роду транспортной задачи. Исходя из этих точек можно найти все фигуры (обходя по контрурах). Придется написать рекурсивную ф-ю.
Таким образом можно найти все многоуголтьники. Закраска труда не составит.
Ответить с цитированием
  (#12 (permalink)) Старый
devel0per devel0per вне форума
Member
 
Сообщений: 55
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.09.2005
По умолчанию 28.09.2005, 23:12

Цитата:
Originally posted by Julia_L
[b]Неделю бьюсь головой об стол.....
А надо было просто немного подумать...
Вот тебе конкретный пример (на Билдере), который определяет области с границей чёрного цвета и заливает их разными цветами:
Код:
//------------------------------------------------
TColor Colors[7]={clAqua,clRed,clPurple,clGreen,clSilver,clBlue,clYellow};
WORD Line[Image1->Width]={0};
BYTE Area[1000]={0};
bool IsLine;
WORD CurArea, CurColor=0;
//------------------------------------------------
CurArea=-1;
for (int y=0; y<Image1->Height; ++y) for (int x=0; x<Image1->Width; ++x)
        if (Image1->Canvas->Pixels[x][y]==clBlack)
        {
                Line[x]=0;
                IsLine=true;
        }
        else
        {
                if ((IsLine)||(x==0)) Area[++CurArea]=0;
                if (Line[x])
                {
                        WORD i=Area[CurArea], j=CurArea-Line[x]+1;
                        if (i==0) Area[CurArea]=j; else if (i!=j)
                        {
                                i=CurArea-i; while (Area[i]) i-=Area[i];
                                j=CurArea-j; while (Area[j]) j-=Area[j];
                                if (i<j) Area[j]=j-i;
                        }
                }
                Line[x]=CurArea+1;
                IsLine=false;
        }
//------------------------------------------------
CurArea=-1;
for (int y=0; y<Image1->Height; ++y) for (int x=0; x<Image1->Width; ++x)
        if (Image1->Canvas->Pixels[x][y]==clBlack) IsLine=true; else
        {
                if ((IsLine)||(x==0))
                {
                        int i=++CurArea;
                        Area[i]=Area[i]?Area[i-Area[i]]:CurColor++;
                }
                Image1->Canvas->Pixels[x][y]=Colors[Area[CurArea]];
                IsLine=false;
        }
//------------------------------------------------
Для работы необходимо небольшое кол-во памяти, но зато происходит всего два прохода по изображению. Осталось только нарисовать многоугольник...
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Julia_L Julia_L вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.09.2005
По умолчанию 28.09.2005, 23:15

Допустим есть массив координат вершин многоугольника и точек самопересечения. Как из него выделить все многоугольники?
Ответить с цитированием
  (#14 (permalink)) Старый
devel0per devel0per вне форума
Member
 
Сообщений: 55
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.09.2005
По умолчанию 28.09.2005, 23:17

Просто нарисуй нужный тебе многоугольник и примени к рисунку приведённый код. Вот и всё
Ответить с цитированием
  (#15 (permalink)) Старый
Julia_L Julia_L вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.09.2005
По умолчанию 28.09.2005, 23:29

devel0per - Спасибо тебе большое, но мне нужно эту задачку на Pascal'e или С++ решить, а там нужно обязательно искать координаты всех многоугольников, так что эта не катит =((
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Определение направления обхода в замкнутом контуре ~erwin~ Алгоритмы 18 07.02.2011 19:24
Устаранить зачыкливание в процедуре обхода графа в глубину. savelev Pascal 0 26.12.2010 11:47
маршрут обхода слонов _Студент_ Prolog 0 12.12.2010 23:29
Реализация обхода графа KYC1989 Prolog 22 16.12.2009 21:15
Разработать программу обхода шахматной доски bIRKA Lisp 0 19.05.2009 20:55
Подскажите анонимайзер для обхода Firewall. sarsed Любые вопросы от новичков 1 28.10.2008 08:32
Выпуклость многоугольника как реализовать Shturmovik Delphi 5 30.10.2006 14:41
Обход невыпуклого многоугольника AntonZima Алгоритмы 9 04.10.2006 03:24
Метод грэхама обхода выпуклой оболочки оля-kzn Алгоритмы 3 01.06.2006 03:53
Площадь многоугольника на Visual C++ DEMONIK-13 Visual C++ 2 31.05.2006 05:00
Как вычислить площадь произвольного многоугольника DEMONIK-13 Вопросы начинающих программистов 3 30.05.2006 21:02
Триангуляция произвольного многоугольника Сергей_Ф Программирование графики 1 06.05.2004 03:10



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов