Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
 Алгоритм поиска контура по набору координат  [new]
xMailer
Member

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

Буду благодарен любой информации.
Спасибо!

+ скрины
скрин 1
Картинка с другого сайта.
скрин 2
Картинка с другого сайта.
скрин 3
Картинка с другого сайта.
скрин 4
Картинка с другого сайта.
Модератор: Для картинок есть тэг [ img ]


Сообщение было отредактировано: 16 окт 19, 14:53
16 окт 19, 14:47    [21995549]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10985
xMailer
1. поиск выпуклой оболочки (Грэхем, Джарвис) - не годится, см скрин 3
В принципе доточить под свои требования, но для этого их нужно сформулировать - в каких случаях нужно достраивать вогнутые области, а в каких нет.


xMailer
2. группировка всех координат, координаты с кол-вом однократным повторений в наборе - являются вершины, да работает, но возможно наличие не соприкасаемых прямоугольников, скрин 4 и тогда не будет работать
Многосвязные области в любом случае будут неправильно обрабатываться, лучше их сразу разбивать на односвязные.
16 окт 19, 15:03    [21995592]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 19590
xMailer
возможно наличие не соприкасаемых прямоугольников, скрин 4
Непонятен критерий, по которому выполняется обрисовка... глядя на скрины 2 и 3, я бы провёл контур как-то так

К сообщению приложен файл. Размер - 10Kb
16 окт 19, 15:40    [21995653]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
xMailer
Member

Откуда:
Сообщений: 62
Соколинский Борис
В принципе доточить под свои требования, но для этого их нужно сформулировать - в каких случаях нужно достраивать вогнутые области, а в каких нет.

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

Akina
Непонятен критерий, по которому выполняется обрисовка... глядя на скрины 2 и 3, я бы провёл контур как-то так

отмена, cancel - был описан частный случай, решил не заморачиваться, согласен вариации могут быть
16 окт 19, 15:57    [21995676]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
xMailer, я-бы разбил задачу на 2 части.

1) Объединение прямоугольников в более крупные
2) Построение оболочки по любому из алгоритмов описанных в wiki
https://ru.wikipedia.org/wiki/Выпуклая_оболочка

Кстати когда мы дойдем до обсуждения реализации (а мы дойдем) может так оказаться что нужная
библиотека уже есть и там подобные задачи уже решены. Соотв возникает другой вопрос.

Что тебе надо на самом деле сделать? Продемонстрировать преподавателю как ты хорошо выучил ГИГМ ?
Или реально сделать боевую задачу ? Это разные подходы будут.
16 окт 19, 16:06    [21995687]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
xMailer
Member

Откуда:
Сообщений: 62
mayton
Что тебе надо на самом деле сделать? Продемонстрировать преподавателю как ты хорошо выучил ГИГМ ?
Или реально сделать боевую задачу ? Это разные подходы будут.

это боевая задача, я не студент
16 окт 19, 16:09    [21995693]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
xMailer, на каком языке собираешся кодить свою боевую задачу?
16 окт 19, 16:15    [21995697]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
xMailer
Member

Откуда:
Сообщений: 62
mayton
xMailer, на каком языке собираешся кодить свою боевую задачу?

серверный, пока php. Если Вы про использование opencv - растровый путь не рассматриваю.
16 окт 19, 16:21    [21995706]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
xMailer
mayton
xMailer, на каком языке собираешся кодить свою боевую задачу?

серверный, пока php. Если Вы про использование opencv - растровый путь не рассматриваю.

Я и не предлагаю OpenCV.

Координаты прямоугольников у тебя целые или вещественные?
16 окт 19, 16:32    [21995713]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10985
xMailer
там же как правило отбор ведется по правилу самая правая при движении против часовой или дополнить расстоянием и отбирать самую близкую правую
Нет. Если речь об алгоритме Грэхема, то там правило выпуклое/невыпуклое определяется для всех точек контура, последовательность обхода значения не имеет.
В Вашем примере правильный контур содержит одну невыпуклую точку. Хотелось бы понять причину по которой она там оказалась, желательно формализованную.
16 окт 19, 17:18    [21995772]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
MBo
Member

Откуда:
Сообщений: 70
xMailer, посмотри на alpha-shapes.
При их построении задаются определённые критерии - может, для твоих условий их можно подобрать.
16 окт 19, 19:41    [21995832]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59112
Я в специализированных алгоритмах не секу, я бы делал так
все вершины бывают острые, прямые или внутренние
взять острую вершину и соединять с соседними прямыми или внутренними до тех пор, пока не дойдем до следующей острой. Таким образом соединим все острые

это что касается замкнутых фигур.
для разделенных нужно будет
а) определить две раздельных фигуры
б) найти две ближайшие между ними острые вершины
в) исполнить вышеозвученный алгоритм
16 окт 19, 20:14    [21995840]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59112
Aklin
взять острую вершину и соединять с соседними прямыми или внутренними до тех пор, пока не дойдем до следующей острой. Таким образом соединим все острые
"соединять", это значит начинать от острой вершины, переходя по внешнему периметру к соседним прямым или внутренним до тех пор, пока не упремся в следующую острую.
16 окт 19, 20:16    [21995841]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Да. Только с точностью наоборот.

Только после построения выпуклой оболочки мы можем решить какая вершина острая или нет.

До этого - мы имеем список гребаных координат.
16 окт 19, 22:57    [21995918]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1843
ТС м.б. не договаривает. Например, нам показали банальный зуум растра, а задача на самом деле м.б. в замыкании контура в растре. И могут иметься нежелательные изолированные точки ............ и т.п. Тогда это - допиливанием морфинга.

Для приведённой ТСом постановки.
Я бы допиливал выпуклую оболочку. Возможно это имелось ввиду под "острыми углами" и т.п., но я не догнал и пишу своё видение.
Для прямоуг-ков, можно находить изолированные циклы графа.
Построив вып-ю об-ку вокруг найденных циклов, можно начинать стягивать резинку между ними.
Когда все циклы окажутся стянутыми, можно начать стягивать каждый цикл.
Формальные правила для стягивания не приведены. А в принципе, если при стягивании надо касаться каждого ближайшего выпуклого угла квадратиков, то достаточно перебором с шагом по углу. Если не каждого, то ........

Но ТС (не в обиду сказано), возможно, недостаточно продумал возможные ситуации.
17 окт 19, 01:05    [21995962]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
ТС так и не ответил про вещественные координаты. По сути много оптимизаций свершаются просто переходя
от векторной графики напрмер к растровой. Или квантизируя или упрощая саму постановку. Как в комьютерных
играх. Зачем хранить координаты каждого кирпича или плитки. Когда нам известна формула где может стоять кирпич и известен
номер этого кирпича в этой декартовой системе координат.

Да и вообще постановка сырая. Грумить ее и обсуждать.

Ди вогнутая область на последней картинке. Это - небрежность?
17 окт 19, 10:42    [21996172]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1843
Думаю да, небрежность. Происходящая от сырой постановки.
Я ведь столкнулся с подобной же задачей в растре, когда пытался выделить контур в прямоугольнике со своими любимыми самолётиками и птичками. Только в моём случае мне показалось не комильфо делать это в МЛ, а на что-то более низкое перейти (напр. ВБА) ради только этой задачи надо уже морально настраиваться. Когда-нибудь настроюсь.

По вопросу концепции, модели, постановки. Была задача о мыльных плёнках. Здесь можно назвать задачей о презервативе на изломистом предмете, натянуть так, чтобы не лопнул. Т.к. в этом случае поверхностного натяжения нет, его должны заменять формальные правила и ограничения.
Я не предлагаю полностью оптимизационную постановку. Это д.б. задача минимизации в каком то смысле отдельных участков. Например там, где выпуклость надо менять на впуклость. Но как ему надо, знает только ТС.

И как всегда, побуждаешь чел-ка заняться проектироваием топ-даун, поскольку без концепции модель трудно построить, а он оказывается самым умным и обижается (имхо).
17 окт 19, 13:48    [21996515]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1843
Забыл, выше у меня читать не дословно "изолированные циклы графа". Имел ввиду компоненты связности. Их выделяют последовательным построением остовных деревьев.
17 окт 19, 13:55    [21996523]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
exp98, я думаю что он уже продублировал свой вопрос на ответах.мейл.ру или тостере и смылся.

Эдакий себе It-фишинг. Где клюнет - там и рыбка.

Никакого дискурса нет. Мдя...
17 окт 19, 13:57    [21996526]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Посмотрел на картинку и предлагаю:

если у всех квадратиков определены углы, то
1. найти все правые крайние углы из всех углов, которые лежат на одной горизонтали.
2. ранжировать эти углы сверху вниз
3. найти все нижние крайние углы из всех углов, которые лежат на одной вертикали.
4. ранжировать эти углы справа налево.

Аналогично для левой стороны и для верха.

И соединяем все полученные углы.

А дальше, по результата осмотра полученной картинки принимать дальнейшие решения:
сглаживание, разбивка контуров и т.д.
17 окт 19, 14:00    [21996532]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1843
Добавлю. Ограничения для минимизации нужны, иначе (навеяно недавними мыслями мэйтона) может получиться что-то типа кривой Гильберта)), когда внутри имеется архипелаг.
17 окт 19, 14:02    [21996535]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1843
mayton, ну мы-то можем кое-какие правила и без него сформулировать. Как раз я бы потм когда-нить воспользовался. Например ширина моста между связываемыми островами. Должен ли мост исходить обязательно из одной, крайней клетки ...
До какой степени изгибаться вовнутрь ...
17 окт 19, 14:13    [21996548]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Никакая у него не выпуклая оболочка. Если ему скрин 3 не подходит значит у него просто - многогранник
которые соединяет экстремальные точки контура всех прямоугольников.
17 окт 19, 14:17    [21996556]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59112
mayton
Да. Только с точностью наоборот.

Только после построения выпуклой оболочки мы можем решить какая вершина острая или нет.

До этого - мы имеем список гребаных координат.

Не сказал бы.
Для начала находим периметр.
Дальше берем непрямую вершину. Найдем среднюю точку отрезка, соединяющего две соседних вершины. Если эта точка внутри множества, ограниченного нашим периметром, то вершина острая.
17 окт 19, 14:35    [21996583]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

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

Берем любую непрямую вершину.
Если две соседних грани принадлежат разным квадратам, то она внутренняя, если одному то острая.
17 окт 19, 14:37    [21996585]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
Все форумы / Программирование Ответить