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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

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

Поэтому предлагаю поднять форк этого топика дабы обсудить проблемы тысячелетия а также женщин и машины.
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
Сообщений: 42891
Дано - груз прямоугольных ящиков. Расчитать длину брезента чтоб обмотать груз ящиков
плотно. Чтоб не болталось на ветру.

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

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

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

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

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

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


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

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

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


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

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

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


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

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


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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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