Подскажите алгоритм поиска полостей

Различные геометрические алгоритмы.
Matew
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 894
Зарегистрирован: 28.06.2004 (Пн) 17:44
Откуда: Дальний Восток, г. Ха

Подскажите алгоритм поиска полостей

Сообщение Matew » 23.07.2008 (Ср) 2:09

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

[Хакер] :: Тема перенесена в раздел "Алгоритмы"
Вложения
Пример.JPG
Пример
Пример.JPG (8.1 Кб) Просмотров: 4135
Алкоголь и сканеры-ваши враги! Не верите-смотрите аватару :-)

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Сообщение Хакер » 23.07.2008 (Ср) 3:14

Matew
Ничего не понял. Что нужно определить? По заданной точке, определить, какой полости она принадлежит? Или определить множество всех точек, входящих в полость, в которой находится заданная точка?

Или для всей картинки найти такие (любые) точки чтобы в каждой полости принадлежала одна и только одна точка? (Например, такое может потребоваться, если нужно напечатать что-нибудь внутри каждой полости (номер её, скажем) -- нужно узнать координаты)

З.Ы. Отрезки это импосты? :wink:
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Proxy
Профессор VB наук
Профессор VB наук
Аватара пользователя
 
Сообщения: 2941
Зарегистрирован: 31.08.2007 (Пт) 4:41

Сообщение Proxy » 23.07.2008 (Ср) 3:24

http://helper10.narod.ru/alg9.htm Это заливка
Follow the white rabbit.

Matew
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 894
Зарегистрирован: 28.06.2004 (Пн) 17:44
Откуда: Дальний Восток, г. Ха

Сообщение Matew » 23.07.2008 (Ср) 3:36

Хакер писал(а):Или для всей картинки найти такие (любые) точки чтобы в каждой полости принадлежала одна и только одна точка? (Например, такое может потребоваться, если нужно напечатать что-нибудь внутри каждой полости (номер её, скажем) -- нужно узнать координаты)

Именно так. С единственно поправкой, если только одну точку найти не удастся, то допускается и несколько (это повлияет только на скорость алгоритма).
Хакер писал(а):З.Ы. Отрезки это импосты? :wink:

Да :) . Нужно остеклить.

З.Ы. (добавочка) мне было бы интересно сравнить мой алгоритм нахождения номер полости(на самом деле меня интересуют номера отрезов вокруг полости) по произвольной точке с вашими, т.ч. можете предлагать и такие.
Последний раз редактировалось Matew 23.07.2008 (Ср) 3:44, всего редактировалось 1 раз.
Алкоголь и сканеры-ваши враги! Не верите-смотрите аватару :-)

Matew
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 894
Зарегистрирован: 28.06.2004 (Пн) 17:44
Откуда: Дальний Восток, г. Ха

Сообщение Matew » 23.07.2008 (Ср) 3:40

Proxy, закрасить я могу. Мне нужно понять, что закрашивать...
Алкоголь и сканеры-ваши враги! Не верите-смотрите аватару :-)

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Сообщение Хакер » 23.07.2008 (Ср) 3:40

Решение мне представляется очевидным (потому что я уже делал такое :) ), только хочу уточнить один момент:

Г-образных импостов (или импостов, сходящихся концами в одну точку (а не упирающихся своим торцом в какой-то другой импост или раму, как это обычно бывает) ведь не будет?

Т.е., если отойти от реальности, ничего похожего на логотип Мерседеса не будет?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Matew
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 894
Зарегистрирован: 28.06.2004 (Пн) 17:44
Откуда: Дальний Восток, г. Ха

Сообщение Matew » 23.07.2008 (Ср) 3:42

Хакер, нет. Это слишком сложно. Только упирающиеся во что-либо.
Алкоголь и сканеры-ваши враги! Не верите-смотрите аватару :-)

Proxy
Профессор VB наук
Профессор VB наук
Аватара пользователя
 
Сообщения: 2941
Зарегистрирован: 31.08.2007 (Пт) 4:41

Сообщение Proxy » 23.07.2008 (Ср) 3:50

А не существует более совершенных алгоритмов? Как это WINDOWS делает? По какому алгоритму?
Follow the white rabbit.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Сообщение Хакер » 23.07.2008 (Ср) 4:02

Proxy
Ты не в теме. Windows ничего такого не делает.

Matew
А какой формат данных, в котором представлены "отрезки"?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Matew
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 894
Зарегистрирован: 28.06.2004 (Пн) 17:44
Откуда: Дальний Восток, г. Ха

Сообщение Matew » 23.07.2008 (Ср) 4:10

Хакер,
Примерно так:
Код: Выделить всё
Public Type Impost
    Imp1 As Byte '  номер импоста в который упирается текущий(если упирается)
    Imp2 As Byte ' с другой стороны
     KoordImp1 As POINTAPI ' Абсолютная координата(обычно в середине)
    KoordImp2 As POINTAPI '  для направления(для вектора)
    arr() As POINTAPI ' координаты углов имопоста(т.е. 4 точки - 2 в начале и 2 в конце) можно считать их координатами пересечения с чем-либо
'....
End Type
Алкоголь и сканеры-ваши враги! Не верите-смотрите аватару :-)

Matew
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 894
Зарегистрирован: 28.06.2004 (Пн) 17:44
Откуда: Дальний Восток, г. Ха

Сообщение Matew » 23.07.2008 (Ср) 4:13

Proxy, расскажи свою задачу, а там можно сказать, как ее сделать с помощью обычных АПИ.
Алкоголь и сканеры-ваши враги! Не верите-смотрите аватару :-)

Proxy
Профессор VB наук
Профессор VB наук
Аватара пользователя
 
Сообщения: 2941
Зарегистрирован: 31.08.2007 (Пт) 4:41

Сообщение Proxy » 23.07.2008 (Ср) 5:08

Хакер Не не не, я про апишную заливку :D Просто получилось так, что я опять говорю криво как-то)
Follow the white rabbit.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Сообщение Хакер » 23.07.2008 (Ср) 5:13

Очень неудачный формат хранения данных.

Ну ладно, опишу общий принцип:

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

Отрезки, из которых состоит рама (самые внешние отрезки) считаем по опеределению отрезками нулевого порядка.

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

Формула, по которой расчитывается порядок отрезка:
Код: Выделить всё
Edge.Order = Max(Edge.Imp1.Order, Edge.Imp2.Order) + 1

здесь функция Max(a, b) -- возвращает максимальное из двух переданных значений. Imp1 и Imp2 -- отрезки, в которые упирается данные (а любой отрезок, не принадлежащей раме, всегда во что-либо упирается).

Следующая иллюстрация показывает, как расставляются порядки отрезков:
Изображение


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

Рама -- тоже регион, и её порядок, согласно правилу определения порядка региона -- 0.

Импост I является девайдерным по отношению к региону R тогда и только тогда, когда порядок импоста на 1 больше порядка региона.

Если говорить о иллюстрации, то все импосты первого порядка (красные) являются девайдерными для рамы. Никакие другие импосты (зелёные и фиолетовые) девайдерными по отношению к раме назвать нельзя.

Теперь вводим такое понятие как подрегион. Подрегион является таким же регионом, и таким же образом имеет свой порядок.

Регион R1 является подрегионом для региона R0, если одной из его сторон является импост, являющийся девайдерным для региона R0.

Следующая иллюстрация показывает деление на подрегионы:
Изображение

Далее: если регион не содержит внутри себя девайдерных импостов, то такой регион считается конечным. На иллюстрации конечными явлются все (крмое одного) регионы третьего порядка, и один регион второго порядка. Получаем координаты вершит таких регионов, суммируем все их и делим на количество вершнин.

Получившиеся точки для каждого региона будут находиться в его центре. Получится примерно следующее:
Изображение


А теперь, внимание, примеры конфигураций, на которых мой алгоритм обломается. В этих случаев все импосты имеют одинаковый порядок, однако этот порядок не имеет смысла и нет ни одного импоста первого порядка:
Изображение

Но я почти полностью уверен, что инструмент, с помощью которого в программе размечается окно, не позволит нарисовать такие окна, хотя технически их легко можно сделать.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Matew
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 894
Зарегистрирован: 28.06.2004 (Пн) 17:44
Откуда: Дальний Восток, г. Ха

Сообщение Matew » 24.07.2008 (Чт) 3:30

Хакер, спасибо. Сделаю.
2 All, как я уже писал, мне было бы интересно сравнить мой алгоритм нахождения номера отрезов, ограничивающих полость по произвольной точке внутри нее с вашими алгоритмами, т.ч. если есть желающие предложить подобные - буду очень рад. Особенно интересует скорость работы.
Алкоголь и сканеры-ваши враги! Не верите-смотрите аватару :-)

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Сообщение Хакер » 24.07.2008 (Чт) 3:57

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


Алгоритм предполагает, что используется с предыдущим алгоритмом. Все понятия также переносятся сюда:

Дана точка.
Проводишь из этой точки луч в любую сторону. Математически определяешь, в какой (первый по ходу луча) отрезок упирается этот луч.


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

Если такой регион 1 -- это и есть регион, в котором находится точка.
Если регионов больше одного, то:
LABEL:
Берёшь угол, образованный всеми ранее построенными лучами (сразу после постройки первого луча образуется один развёрнутый угол величиной 360 градусов), строишь новый луч, являющийся бисектриссой этого угла (в первый раз, когда существует только один луч, эта биссектриса будет смотреть в другую сторону, во второй раз, биссектриса будлет перпендикулярна двум лучам, в третий раз, будет делить попалам один из прямых углов и т.д.).

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

Если в конечном счёте остался только один регион, это и есть тот регион, в котором находится точка. Если в же осталось более одного региона, то goto LABEL

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

На псевдокоде алгоритм можно описать так:


Код: Выделить всё
variable ArrRegions As Array

Ray = BuildRandomBeam() // Строит "случайный" луч
arrRegions = GetIntersectedEdge(Ray)
Do
   If arrRegions.Count = 0 Then
       return arrRegions.Item(0)   
   End if

   Ray = BuildBisectrissRay()
   Edge = GetIntersectedEdge(Ray) // Получаем отрезок, который пересекли лучем

   arrNewRegions = GetFiniteRegionsWithSpecifiedEdge(Edge) // Получаем все конечные регионы, в состав которых входит отрезок Edge

   arrRegions = GetOnlyMatches(arrRegions, arrNewRegions) // Возвращает только те элементы, которые есть в обоих массивах
Loop     
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Сообщение Хакер » 24.07.2008 (Чт) 4:16

Ну и вот картинка, чтобы легче понять процесс было:

Изображение


Обращаю внимание, что при на рисунке при нахождении отрезка, пересекающегося с лучем, находится маленький отрезок (подотрезок большого (импоста, упирающегося обоими концами в раму) отрезка.

Алгоритм также отлично будет работать, если находить не маленький отрезок, а брать весь отрезок. Единственный побочный эффект -- придётся перебирать большее кол-во конечных регионов (в функции GetOnlyMatches), и, в некоторых редких случаях, потребуется большее кол-во попыток.[/img]
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.


Вернуться в Геометрия

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList