ReSQL.ru
     
powered by simpleCommunicator - 2.0.50     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска контура по набору координат
25 сообщений из 66, страница 2 из 3
  2  все
Алгоритм поиска контура по набору координат
    #39877725
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я вот нарисовал многоугольник. Может по шагам показать как ты искал периметр и всё прочее?
...
Рейтинг: 0 / 0
17.10.2019, 14:40
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39877846
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
maytonЯ вот нарисовал многоугольник. Может по шагам показать как ты искал периметр и всё прочее?


в ТС речь шла про набор прямоугольников.
Заверните ваш многоугольник в набор прямоугольников...
...
Рейтинг: 0 / 0
17.10.2019, 17:56
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39877848
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
xMailer2. группировка всех координат, координаты с кол-вом однократным повторений в наборе - являются вершины, да работает, но возможно наличие не соприкасаемых прямоугольников, скрин 4 и тогда не будет работатьсамое забавное, что это простейшее из решений, и его нужно лишь допилить под случай с несвязанными областями и только. Для начала определите все связанные области, обведите области по этой схеме - объединить все вершины, появляющиеся в связанной области только один раз.
Дальше - соединить между собой.
Тут, думаю, надо найти две области, наиболее близкие друг к другу, и соединить две самые близкие их вершины, по одной на область. И так делать пока все не будут соеденены.
...
Рейтинг: 0 / 0
17.10.2019, 17:59
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39877861
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AklinmaytonЯ вот нарисовал многоугольник. Может по шагам показать как ты искал периметр и всё прочее?


в ТС речь шла про набор прямоугольников.
Заверните ваш многоугольник в набор прямоугольников...
Какая разница. Тут вопрос принципа. Или алгоритма.
...
Рейтинг: 0 / 0
17.10.2019, 18:16
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39877881
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
maytonAklin
Какая разница. Тут вопрос принципа. Или алгоритма.Не совсем так.
У фигуры, состоящей из прямоугольников не может быть острых вершин, состоящих из вершин двух прямоугольников. В ТС вообще способ был написан: взять все вершины, повторяющиеся один раз. Для замкнутой фигуры этого достаточно.

Для произвольного многоугольника встает вопрос об исходной задаче. Не совсем понятно, что именно нужно обводить...
...
Рейтинг: 0 / 0
17.10.2019, 19:01
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39877901
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Я полагаю что потребность была не в том, чтобы получить фигуру абы как, но кусочно-линейно связную.
Aklin...Тут, думаю, надо найти две области, наиболее близкие друг к другу, и соединить две самые близкие их вершины, по одной на область. И так делать пока все не будут соеденены. Тут сразу неск. вопросов.
а) " соединить две самые близкие их вершины " - т.е. предлагается мостик сделать из одной линии (~как на рис. Акины) ?
б) " две области, наиболее близкие " - а если нужная фигура круто серповидная, напр. фюзеляж и крыло под острым углом к нему? даже фигура с моим голубком может вызывать споры, если не знать её вн. структуру заранее.
в) " так делать пока все не " - кто такие все? компоненты связанности?
...
Рейтинг: 0 / 0
17.10.2019, 20:36
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39877912
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
exp98а) " соединить две самые близкие их вершины " - т.е. предлагается мостик сделать из одной линии (~как на рис. Акины) ?Начиная от одной острой вершины идем в бок, пока не найдем соседнюю острую, и соединяем их линией.


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


exp98в) " так делать пока все не " - кто такие все? компоненты связанности?именно
...
Рейтинг: 0 / 0
17.10.2019, 20:59
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39877925
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
AklinНачиная от одной острой вершины идем в бок, пока не найдем соседнюю острую, и соединяем их линией.Нарисовать нужно как раз это, поскольку я до сих пор не врубился в " острые вершины ". Где и когда они живут?
А с соединением компонент всё просто словами. Есть, скажем фигура чел-ка, состоящая из огуречик + тыква + овалы ручек и ножек + овльчики ступней и кистей.
Фигурка может сучить ручками и ножками. В какой-то момент вдруг захочет почесать репу граблей. Вот что, прямо так в этот момент и соединить тыкву с граблей?
Вот я и говорил о внутренней структуре. Иногда её называют "скелетным графом". Ею м.б. направленный граф, соединяющий компоненты связности, все или только самые характерные для идентификации. Это только как пример.

Разговор можно отложить и на завтра, если есть желание, спешить некуда.
...
Рейтинг: 0 / 0
17.10.2019, 21:25
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39877943
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Поскольку автор оказался не-джентльменом и игнорирует вопросы я делаю предположение что задачу он для себя уже давно решил.

Поэтому предлагаю поднять форк этого топика дабы обсудить проблемы тысячелетия а также женщин и машины.
...
Рейтинг: 0 / 0
17.10.2019, 22:36
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878016
xMailer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
xMailer
Участник
Парни, ТС не слился, я тут и читаю периодически данный пост, дел просто за гланды, не нужно меня ругать.
Пока думаю над данным вопросом.

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

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

Координаты вещественные и сильно.
...
Рейтинг: 0 / 0
18.10.2019, 09:21
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878037
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Дано - груз прямоугольных ящиков. Расчитать длину брезента чтоб обмотать груз ящиков
плотно. Чтоб не болталось на ветру.

Так?
...
Рейтинг: 0 / 0
18.10.2019, 10:02
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878057
xMailer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
xMailer
Участник
maytonДано - груз прямоугольных ящиков. Расчитать длину брезента чтоб обмотать груз ящиков
плотно. Чтоб не болталось на ветру.
Так?
интересно, да, так. Есть типовой подход, типа задачи коммивояжёра.
...
Рейтинг: 0 / 0
18.10.2019, 10:26
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878061
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я чуть позже нарисую 2-3 частных случая укладки ящиков. А ты дай свою экспертную оценку как их обматывать. ОК?
...
Рейтинг: 0 / 0
18.10.2019, 10:29
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878126
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
exp98Нарисовать нужно как раз это, поскольку я до сих пор не врубился в " острые вершины ". Где и когда они живут?
В соединенных прямоугольниках есть вершины. Все вершины этих прямоугольников могут образовывать на внешнем периметре острый угол (тот, который торчит наружу, две соседних стороны принадлежат одному прямоугольнику, а сама вершина с другими вершинами не пересекается), когда два рядом стоящих прямоугольника образуют на периметре прямую линию, а сама вершина среди всех вершин прямоугольников встречается два раза) и внутренний (когда образуется не прямой и не острый угол, а сама вершина принадлежит трем прямоугольникам).


П.С.
я тут интересный пример придумал, когда два прямоугольника объеденены лишь одной вершиной. Тогда получается два внутренних угла, но по вышеозвученной характеристике они считаются прямыми.... Впрочем, все равно это решает вопрос, если учитывать только вершины, участвующие ОДИН раз.
...
Рейтинг: 0 / 0
18.10.2019, 11:23
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878127
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
exp98Нарисовать нужно как раз это, поскольку я до сих пор не врубился в " острые вершины ". Где и когда они живут?
В соединенных прямоугольниках есть вершины. Все вершины этих прямоугольников могут образовывать на внешнем периметре острый угол (тот, который торчит наружу, две соседних стороны принадлежат одному прямоугольнику, а сама вершина с другими вершинами не пересекается), когда два рядом стоящих прямоугольника образуют на периметре прямую линию, а сама вершина среди всех вершин прямоугольников встречается два раза) и внутренний (когда образуется не прямой и не острый угол, а сама вершина принадлежит трем прямоугольникам).


П.С.
я тут интересный пример придумал, когда два прямоугольника объеденены лишь одной вершиной. Тогда получается два внутренних угла, но по вышеозвученной характеристике они считаются прямыми.... Впрочем, все равно это решает вопрос, если учитывать только вершины, участвующие ОДИН раз.
...
Рейтинг: 0 / 0
18.10.2019, 11:23
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878128
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
exp98А с соединением компонент всё просто словами. Есть, скажем фигура чел-ка, состоящая из огуречик + тыква + овалы ручек и ножек + овльчики ступней и кистей.
Фигурка может сучить ручками и ножками. В какой-то момент вдруг захочет почесать репу граблей. Вот что, прямо так в этот момент и соединить тыкву с граблей?
Вот я и говорил о внутренней структуре. Иногда её называют "скелетным графом". Ею м.б. направленный граф, соединяющий компоненты связности, все или только самые характерные для идентификации. Это только как пример.

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

Делайте тестовые сценарии, попробую написать, что придумал...
...
Рейтинг: 0 / 0
18.10.2019, 11:24
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878132
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
xMailerотсортировать по часовой

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


Насчет упорядочить, отсортировать по часовой - это как, найти периметр что ли?
...
Рейтинг: 0 / 0
18.10.2019, 11:27
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878138
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вообще ни понимаю как нам помогает знание периметра. Как нам помогает обход по- или простив- часовой.
Представте ящики стоят по форме подковы или буквы С.

Есть два одинаковы периметра. И есть симметрия. Ну ходите в любую сторону - решение задачи должно быть инвариантно.
...
Рейтинг: 0 / 0
18.10.2019, 11:33
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878179
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
У меня были сомнения в моей правоте, посему извиняюсь перед автором за необоснованные подозрения. Но с моей стороны это был несколько намеренный троллинг))

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

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

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

Надо только помнить, что совпадения вершин условное, с некоторой точностью.
...
Рейтинг: 0 / 0
18.10.2019, 12:23
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878185
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
xMailerУпорядочить вершины по полярному кругу не получилось. а) Почему?
б) если форма буквы С, но не кольцо, а спиральное кольцо (т.е. имеющее толщину), как отсеять по расстоянию "меньше определенного"?
...
Рейтинг: 0 / 0
18.10.2019, 12:31
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878186
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Удивительно как обмотка ящиков может взбудоражить инженерный ум.
...
Рейтинг: 0 / 0
18.10.2019, 12:31
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878187
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
exp98помнить, что совпадения вершин условное, с некоторой точностью.Я такие точки отождествлял на графе, как одну вершину.
...
Рейтинг: 0 / 0
18.10.2019, 12:33
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878189
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
AklinДелайте тестовые сценарии, попробую написать, что придумал...Подожду пример от мэйтона )) Правда у него ожидается односвязная область.
...
Рейтинг: 0 / 0
18.10.2019, 12:35
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878219
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
exp98Могут быть острова внутри материкового моря -- компонента связности внутри другой компоненты.Ну это-то несложно. Как только определитесь с тем, какие фигуры связаны, а какие нет, нужно будет определить, что внутри фигуры дырка, и ее тоже обвести.

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

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


exp98Надо только помнить, что совпадения вершин условное, с некоторой точностью.
Размер точности должен быть предопределен до запуска задачи объединения =)
...
Рейтинг: 0 / 0
18.10.2019, 13:06
| Ответить | Цитировать | Написать  
Алгоритм поиска контура по набору координат
    #39878260
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Aklin...определить, что внутри фигуры дырка, и ее тоже обвести ...В данном топике лучше сначала услышать ТСа, мож только снаружи и надо.

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

А проблемка, где соединять (ближайшие точки или как-то иначе) иллюстрируется на фрагменте топограф. карты средиземноморья, включительно с частью Чёрного моря (отрезаем Новороссийск и далее Абхазский берег до Турции). Соединить Африку мостиком с Европой где? Гибралтар? Босфор? а мож в районе Куршской косы?
...
Рейтинг: 0 / 0
18.10.2019, 13:51
| Ответить | Цитировать | Написать  
25 сообщений из 66, страница 2 из 3
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска контура по набору координат
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39878057&tid=1339885]:
 0ms
get settings:
 10ms
get forum list:
 12ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 130ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 62ms
get tp. blocked users:
 2ms
others: 14ms
total:  252ms
созд. / загр.: 252ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]