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

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


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

Откуда: Зеленоград, Москва, Россия
Сообщений: 19591
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
Сообщений: 42917
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
Сообщений: 42917
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
Сообщений: 42917
xMailer
mayton
xMailer, на каком языке собираешся кодить свою боевую задачу?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Берем любую непрямую вершину.
Если две соседних грани принадлежат разным квадратам, то она внутренняя, если одному то острая.
17 окт 19, 14:37    [21996585]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Я вот нарисовал многоугольник. Может по шагам показать как ты искал периметр и всё прочее?

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

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59122
mayton
Я вот нарисовал многоугольник. Может по шагам показать как ты искал периметр и всё прочее?

Картинка с другого сайта.

в ТС речь шла про набор прямоугольников.
Заверните ваш многоугольник в набор прямоугольников...
17 окт 19, 17:56    [21996819]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59122
xMailer
2. группировка всех координат, координаты с кол-вом однократным повторений в наборе - являются вершины, да работает, но возможно наличие не соприкасаемых прямоугольников, скрин 4 и тогда не будет работать
самое забавное, что это простейшее из решений, и его нужно лишь допилить под случай с несвязанными областями и только. Для начала определите все связанные области, обведите области по этой схеме - объединить все вершины, появляющиеся в связанной области только один раз.
Дальше - соединить между собой.
Тут, думаю, надо найти две области, наиболее близкие друг к другу, и соединить две самые близкие их вершины, по одной на область. И так делать пока все не будут соеденены.
17 окт 19, 17:59    [21996821]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Aklin
mayton
Я вот нарисовал многоугольник. Может по шагам показать как ты искал периметр и всё прочее?

Картинка с другого сайта.

в ТС речь шла про набор прямоугольников.
Заверните ваш многоугольник в набор прямоугольников...

Какая разница. Тут вопрос принципа. Или алгоритма.
17 окт 19, 18:16    [21996841]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59122
mayton
Aklin

Какая разница. Тут вопрос принципа. Или алгоритма.
Не совсем так.
У фигуры, состоящей из прямоугольников не может быть острых вершин, состоящих из вершин двух прямоугольников. В ТС вообще способ был написан: взять все вершины, повторяющиеся один раз. Для замкнутой фигуры этого достаточно.

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

Откуда:
Сообщений: 1846
Я полагаю что потребность была не в том, чтобы получить фигуру абы как, но кусочно-линейно связную.
Aklin
...Тут, думаю, надо найти две области, наиболее близкие друг к другу, и соединить две самые близкие их вершины, по одной на область. И так делать пока все не будут соеденены.
Тут сразу неск. вопросов.
а) "соединить две самые близкие их вершины" - т.е. предлагается мостик сделать из одной линии (~как на рис. Акины) ?
б) "две области, наиболее близкие" - а если нужная фигура круто серповидная, напр. фюзеляж и крыло под острым углом к нему? даже фигура с моим голубком может вызывать споры, если не знать её вн. структуру заранее.
в) "так делать пока все не" - кто такие все? компоненты связанности?
17 окт 19, 20:36    [21996918]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59122
exp98
а) "соединить две самые близкие их вершины" - т.е. предлагается мостик сделать из одной линии (~как на рис. Акины) ?
Начиная от одной острой вершины идем в бок, пока не найдем соседнюю острую, и соединяем их линией.


exp98
б) "две области, наиболее близкие" - а если нужная фигура круто серповидная, напр. фюзеляж и крыло под острым углом к нему? даже фигура с моим голубком может вызывать споры, если не знать её вн. структуру заранее.
нужно рисовать и смотреть, где эта схема не пройдет, на слух сложно сказать...


exp98
в) "так делать пока все не" - кто такие все? компоненты связанности?
именно
17 окт 19, 20:59    [21996936]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Aklin
Начиная от одной острой вершины идем в бок, пока не найдем соседнюю острую, и соединяем их линией.
Нарисовать нужно как раз это, поскольку я до сих пор не врубился в "острые вершины". Где и когда они живут?
А с соединением компонент всё просто словами. Есть, скажем фигура чел-ка, состоящая из огуречик + тыква + овалы ручек и ножек + овльчики ступней и кистей.
Фигурка может сучить ручками и ножками. В какой-то момент вдруг захочет почесать репу граблей. Вот что, прямо так в этот момент и соединить тыкву с граблей?
Вот я и говорил о внутренней структуре. Иногда её называют "скелетным графом". Ею м.б. направленный граф, соединяющий компоненты связности, все или только самые характерные для идентификации. Это только как пример.

Разговор можно отложить и на завтра, если есть желание, спешить некуда.
17 окт 19, 21:25    [21996950]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

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

Поэтому предлагаю поднять форк этого топика дабы обсудить проблемы тысячелетия а также женщин и машины.
17 окт 19, 22:36    [21996970]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
xMailer
Member

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

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

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

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

Вот постановка вопроса.

Координаты вещественные и сильно.
18 окт 19, 09:21    [21997086]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Дано - груз прямоугольных ящиков. Расчитать длину брезента чтоб обмотать груз ящиков
плотно. Чтоб не болталось на ветру.

Так?
18 окт 19, 10:02    [21997124]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
xMailer
Member

Откуда:
Сообщений: 62
mayton
Дано - груз прямоугольных ящиков. Расчитать длину брезента чтоб обмотать груз ящиков
плотно. Чтоб не болталось на ветру.
Так?

интересно, да, так. Есть типовой подход, типа задачи коммивояжёра.
18 окт 19, 10:26    [21997150]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Я чуть позже нарисую 2-3 частных случая укладки ящиков. А ты дай свою экспертную оценку как их обматывать. ОК?
18 окт 19, 10:29    [21997157]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59122
exp98
Нарисовать нужно как раз это, поскольку я до сих пор не врубился в "острые вершины". Где и когда они живут?

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


П.С.
я тут интересный пример придумал, когда два прямоугольника объеденены лишь одной вершиной. Тогда получается два внутренних угла, но по вышеозвученной характеристике они считаются прямыми.... Впрочем, все равно это решает вопрос, если учитывать только вершины, участвующие ОДИН раз.
18 окт 19, 11:23    [21997234]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59122
exp98
Нарисовать нужно как раз это, поскольку я до сих пор не врубился в "острые вершины". Где и когда они живут?

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


П.С.
я тут интересный пример придумал, когда два прямоугольника объеденены лишь одной вершиной. Тогда получается два внутренних угла, но по вышеозвученной характеристике они считаются прямыми.... Впрочем, все равно это решает вопрос, если учитывать только вершины, участвующие ОДИН раз.
18 окт 19, 11:23    [21997235]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59122
exp98
А с соединением компонент всё просто словами. Есть, скажем фигура чел-ка, состоящая из огуречик + тыква + овалы ручек и ножек + овльчики ступней и кистей.
Фигурка может сучить ручками и ножками. В какой-то момент вдруг захочет почесать репу граблей. Вот что, прямо так в этот момент и соединить тыкву с граблей?
Вот я и говорил о внутренней структуре. Иногда её называют "скелетным графом". Ею м.б. направленный граф, соединяющий компоненты связности, все или только самые характерные для идентификации. Это только как пример.

Разговор можно отложить и на завтра, если есть желание, спешить некуда.


Делайте тестовые сценарии, попробую написать, что придумал...
18 окт 19, 11:24    [21997238]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59122
xMailer
отсортировать по часовой


К слову, как быть с фигурами, у которых внутри дырка?


Насчет упорядочить, отсортировать по часовой - это как, найти периметр что ли?
18 окт 19, 11:27    [21997242]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Вообще ни понимаю как нам помогает знание периметра. Как нам помогает обход по- или простив- часовой.
Представте ящики стоят по форме подковы или буквы С.

Есть два одинаковы периметра. И есть симметрия. Ну ходите в любую сторону - решение задачи должно быть инвариантно.
18 окт 19, 11:33    [21997250]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
У меня были сомнения в моей правоте, посему извиняюсь перед автором за необоснованные подозрения. Но с моей стороны это был несколько намеренный троллинг))

Aklin
К слову, как быть с фигурами, у которых внутри дырка?
Вот! опередели. Это к постановке даже в форме ящиков.
Потом, не только дыры (лакуны). Тут как раз одноранговые вершины. Могут быть острова внутри материкового моря -- компонента связности внутри другой компоненты.

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

П.С. Не, ну надо же так назвать: прямой угол острым, тупой - внутренним. Ну тут откуда смотреть, можно и наоборот, 90 -- 270. Но уж 180 все бы поняли.
Случай, когда пересечение по вершине - штатный, разрыва нет.

Надо только помнить, что совпадения вершин условное, с некоторой точностью.
18 окт 19, 12:23    [21997304]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
xMailer
Упорядочить вершины по полярному кругу не получилось.
а) Почему?
б) если форма буквы С, но не кольцо, а спиральное кольцо (т.е. имеющее толщину), как отсеять по расстоянию "меньше определенного"?
18 окт 19, 12:31    [21997311]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Удивительно как обмотка ящиков может взбудоражить инженерный ум.
18 окт 19, 12:31    [21997312]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
exp98
помнить, что совпадения вершин условное, с некоторой точностью.
Я такие точки отождествлял на графе, как одну вершину.
18 окт 19, 12:33    [21997313]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Aklin
Делайте тестовые сценарии, попробую написать, что придумал...
Подожду пример от мэйтона )) Правда у него ожидается односвязная область.
18 окт 19, 12:35    [21997315]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Aklin
Member

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

Хотя нет, сложно будет при этом не задеть внутренний остров.
А дальше, если после обвода внутренних территорий не задели, несложно будет соединить остров к материку.

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


exp98
Надо только помнить, что совпадения вершин условное, с некоторой точностью.

Размер точности должен быть предопределен до запуска задачи объединения =)
18 окт 19, 13:06    [21997358]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Aklin
...определить, что внутри фигуры дырка, и ее тоже обвести ...
В данном топике лучше сначала услышать ТСа, мож только снаружи и надо.

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

А проблемка, где соединять (ближайшие точки или как-то иначе) иллюстрируется на фрагменте топограф. карты средиземноморья, включительно с частью Чёрного моря (отрезаем Новороссийск и далее Абхазский берег до Турции). Соединить Африку мостиком с Европой где? Гибралтар? Босфор? а мож в районе Куршской косы?
18 окт 19, 13:51    [21997420]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Извиняюсь за дидактичность:
Хочу ещё пару слов к постановке. Это одинаково относится и к вопросу ТС, и к моей цели.
Сейчас мы немножко в положении. Я перейду на терминологию рисунков.
+
Нам сказали: "Мы превратили полутоновый рисунок в ч/б. Качественно или плохо, это наша проблема.
Мы хотим теперь минимально оконтурить, чтобы вырезать только рисунок, отбросив лишнее. Вот вы нам оконтурьте, по своим соображениям, не зная исходной фигуры, на которую это д.б. похоже, не зная будущих способов использования вырезки, не зная в какой области на самом деле будет применён алгоритм.
А мы ваше качество оценим (наверное глазками), ибо мы знаем, что может быть, и примерно поймём, качественно это сделано или нет."

Пока получается ситуация конкурса алгоритмов. По закону о конкурсе (тендере) в старой редакции, объявитель не обязан объяснять, по каким критериям он выбрал победителя. Но то битва за баблосики ...

Если меньше лирики:
- модель (пусть даже их 2-3) должна быть обоснованно адекватна предметной области
- какие-то показатели качества д.б. (мы пока не уверены, на что ориентироваться, даже если не существует "рисунка"-оригинала, показатели качества могут исходить из представлений о предполагаемом использовании)
- какие-то формализованные ограничения д.б.
- оценка кол-ва точек (10^2, ^3, ... ^1000 ...)
- серийность задачи (если нужно только одинажды, то может ручками просто? а сказать, что автоматически).
18 окт 19, 13:54    [21997426]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
xMailer
Member

Откуда:
Сообщений: 62
exp98
xMailer
Упорядочить вершины по полярному кругу не получилось.
а) Почему?

центр для определения угла я определил как
xc = sum(x)/count(x)
yc = sum(y)/count(y)
вес для сортировки относительно центра
angle = atan2(cx - x, cy - y)

Такого рода сортировка будет корректно работать если центр xc,yc находится в примерном центре, в случае выгнутости фигуры у меня не заработало.

Отверстий в фигуре в данной задаче не предусматривается
18 окт 19, 15:26    [21997523]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Навскидку неск. подходов к показателям качества. От них же можно строить ограничения. Либо наоборот.
- числовой (%точек ...)
- площадной (%площади, макс и мин ширина/площадь разных участков)
- линейный (длина, ширина, периметр, их соотношения ...)
- статистический (М, Д, Д2, Д3 ... плотности, %ошибок, любые фантазии, вкл. корреляции чего-либо)
- когнитивный (похоже на ..., включает в себя ..., формируется из ...)
- оптимизационный (мин/макс некой ф-ции)
18 окт 19, 15:28    [21997525]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
xMailer, а зачем сортировка, послед-сть соединения вершин? а полученный граф из оставшихся точек на что?
Если полученное кач-во достаточно, то, определившись наобум с первой точкой, проложить путь на графе до всех соседей (из оставшихся). И так далее, по типу перебора в ширину.
А в глубину придётся "8"-ки специально обрабатывать.

С учётом 8-к сделать и нумерацию по мере прокладки на графе. В принципе она не линейно-кольцевая, а древовидно-кольцевая.

Кста, ещё показатель кач-ва. В мат-ке он называется что-то вроде индекс вектора вдоль участка кривой. Вычисляется как кол-во оборотов (касательной или нормали). + и - друг друга аннулируют. ИМХО, лучше вычислять "плавающий индекс", на нек-ром кол-ве точек, чтобы не прозевать сильно изъгибистые участки.
18 окт 19, 15:54    [21997543]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
xMailer,
правда я до сих пор не понял, как ограничение по радиусу помогает выявить нужные точки. По-моему, если константа, то только мешает. Взять синусоиду, пару периодов. Центр масс у неё в середине. При константе выкинем всё, что близко к центру, и как с ними тогда тогда соединиться?
Возможно, что выявить методом 1-ранговости все, а из них взять только дальние.

На графе от точки к точке двигаться по периметру. И кста, из графа лучше ничего не выкидывать.
18 окт 19, 16:04    [21997553]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
дополню
exp98
выявить методом 1-ранговости все, а из них взять только дальние.
Остальные окучить выпуклой оболочкой. Но это скорее всего не то, что нужно.
18 окт 19, 16:07    [21997556]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Aklin
Делайте тестовые сценарии, попробую написать, что придумал...
Можно потренироваться на этом рис. На тему выделения движущихся "объектов" У него отрезать нижнюю половину, бинаризовать, а тёмный треугольник под крылом допилить 2-мя способами:
- чтобы появился остров
- чтобы это оказалось полуостровом поизгибистей.
18 окт 19, 16:31    [21997582]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
xMailer,
мне показалось, что вы хотите ограничить снизу толщину фигуры. Например, чтобы не было слишком тонкой талии.
Метода радиус-векторов часто не прокатывает. Приходит мысль измерять толщину в целом кол-ве клеток (dx<x0 OR dy<y0). Но тогда это делается уже постфактум.
Детектировать нетрудно, а вот ... о способе исправления пока глубоко не задумывался.
18 окт 19, 21:12    [21997774]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
exp98
Aklin
Делайте тестовые сценарии, попробую написать, что придумал...
Подожду пример от мэйтона )) Правда у него ожидается односвязная область.

Эй. Что это за тоталиатор? Я ничего космического не обещал.

P.S. Soryan за остуствие. У меня полетел Wifi адаптер и я конфигурил новый. Какой-то китайский Netis.
Зато двухдиапазонный.
18 окт 19, 21:13    [21997775]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Dima T
Member

Откуда:
Сообщений: 14096
mayton
У меня полетел Wifi адаптер и я конфигурил новый

Ты же взрослый дядька со взрослым компом, протяни уже провод от роутера (перфоратор на прокат можно взять)
18 окт 19, 21:19    [21997781]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Уже пофиксил.
18 окт 19, 21:29    [21997787]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
По ящикам. На картинке есть груз ящиков по форме буквы Е.

Тривиальная упаковка говорит что надо исключить центральный ящик из привязки. Но мы видели
что в первом посту у автора есть сложная привязка которая учитывает экстремальные точки
внутренних ящиков.

Помогите определить включать ли внутренний ящик. И как.

К сообщению приложен файл. Размер - 56Kb
18 окт 19, 21:43    [21997797]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Из тех крох, что нам известны, у меня имхо, что надо бы к 2 вершинкам срединной перекладины притянуть.

1) Из тех же крох складывается имхо, что неплохим приближением будет метафора (нет, не раскроя листа) вырезания кучи заготовок из листа. С одной стороны надо бы их поплотнее уложить, с другой стороны и вырезанное и оставшаяся часть должны быть достаточо операбельны, не переломиться при переноске и т.п.
В частности поэтому узкая талия недопустима. Возможно заготовки одинаковой формы и дыр не предвидится.

2)Почему именно прямоуг-ки? хр3 - это вопрос. Автор нарисовал сетку, мэйтон - нет. Для сетки проще строить граф - вся разница. На самом деле для односвязной (пусть и с дырами) оласти у меня уже практически до конца сложилось в голове. Есть варианты,но они зависят от постановки. Поэтому именно к авторской задаче мой интерес уже испаряется. Её я считаю решённой, ну а кодить ... похожее уже кодил макет 5 лет назад, но тогда постановка была достаточная, и автор всерьёз интересовался.

3) Единственное, чего не могу ТСу однозначно рекомендовать - метод игнорирования слишком глубоких впадин. Вопрос фигня, но метод геометрический и итерационный, если делать по науке, сглаживая окрестностями с целью получить серединку хребта. Наверняка уже есть дискретные способы. Скажем, создать матрицу, охватывающую все точки по Х и У. Да и вообще, неплохо провести предварительный разведочный анализ исходной конфигурации заради параметров алгоритма, "эллипсоида рассеяния" фигуры, степени симметричости и пр.

4) Предполагая, что внутри нет дыр, что надо выдерживать достаточную толщину вырезки, что кол-во точек вменяемо и что даже дана сетка, а не фигурки (хотя последнее необязательно), степень извилистости в качестве тоже ограничения не определяется.
Используется сочетание дискретных и геометрических методов.

а) геометрию перевести в граф
б) построить полный контур, какой бы извилистый он не был. Например методом 1-ранговых вершин. Начать можно практически с любой точки (правда потом по мере выбрасывания вершин из пути придётся начало передвигать).
в) аналитически(не знаю уж как) или по мере обхода периметра замерять текущую ширину (тем самым методом (3)) и, если она маленькая удалиьт из пути именно эту вершину, вернуться к предыдущей и соединить её со след-щей. Соединение происходит по некому правилу (непосредственный отрезок или нет).
г) Может получиться, что оставшаяся часть фигуры вся недостаточно широкая, может даже откат к предыдущей вершине не поможет. Это уж как ТС решит.

Ну и да, случай самопересечения "8" надо правильно обрабатывать.

Можно поиском кратчайшего пути, разомкнув предварительно 2 соседние вершины. Однако придётся задать веса ребрам графа, а потом каждое решение поверять,насколько оно узкое,и вносить поправки в веса. Ну и рез-т не гарантируется.

Примерно так.


Как ещё вариант фигуры на карте 2-х Америк отрезать северные штаты США от южных, Отрезать всё, в южном полушарии или по Амазонке, убрать острова Кубу, Гаити и т.д (или сделать их полуостровами). Нарисовать сетку. Очень извилистый пример будет.
19 окт 19, 22:04    [21998099]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Афтор. Прокомментируй пожалуйста наши 2 последних сообщения.
20 окт 19, 23:51    [21998558]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
xMailer
Member

Откуда:
Сообщений: 62
Чтобы была законченность в теме решил написать выбранное решение, которое позволило решить мою задачу и для ящиков подойдет (в такой конфигурации как на рисунке).
Мне помог отслеживающий алгоритм "жука". По ссылке, да и в нете в основном его используют для обработки растра, но и в случае прямоугольников он отработал на ура, шаг отслеживания 0.5, кто прочитает про алгоритм поймет почему.
Всем спасибо!
22 окт 19, 22:42    [22000295]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Тоесть наши вопросы тебя уже не интересуют. Интересный ты собеседник. Ладно иди читай. Зачем тебе тогда
форум - непонятно.
22 окт 19, 23:02    [22000304]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3      [все]
Все форумы / Программирование Ответить