Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
1

Сортировка по контуру

08.01.2014, 17:37. Просмотров 1549. Ответов 37
Метки нет (Все метки)

Здравствуйте, подскажите, пожалуйста, алгоритмы или соответствующую литературу, по которым можно отсортировать точки, задающие односвязный контур на плоскости в общем случае, т.е. не обязательно выпуклый.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2014, 17:37
Ответы с готовыми решениями:

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

Резка по контуру
Здравствуйте. Нужна помощь. Есть некий объект. Необходимо создать контур, а потом экспортировать...

Распознавание по контуру
Всем привет. У меня возникла идея попробовать написать программу для своих нужд, но язык я знаю...

Интеграл по замкнутому контуру
Всем привет!:) Подскажите пожалуйста как продолжить мысль дальше, хочу победить этот интеграл. Он...

Интеграл по замкнутому контуру
\oint_{|z|=0.1}^{}\frac{cos2z-1+2z^2}{z^4 sh\frac{\pi z}{3}} Итак, определил тип особой точки z=0...

37
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
02.02.2014, 19:05  [ТС] 2
upd
Для примера
0
Миниатюры
Сортировка по контуру  
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
02.02.2014, 21:02 3
в чем отличие вашей задачи от задачи "отсортируйте массив чисел по возрастанию"?
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
03.02.2014, 13:39 4
Нет здесь никакой сортировки, автор имел ввиду "найти последовательность точек контура" (если не так - поправит).

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

напр в точке 1 возможны ходы с расстояниями 5, 7, 10 ... В первый раз идем к ближайшей (точке с расстоянием 5). Альтернативы 7/5 и 10/5, этот относительный вес известен для всех пройденных точек. Выбираем наименьший (среди всех) и пробуем дальше.

А вообще чувствуется что задача хорошо известна, наверняка можно разгуглить
1
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
03.02.2014, 16:15 5
Вот тут есть несколько алгоритмов для построения выпуклых контуров, думаю можно найти простой и попробовать его переделать для невыпуклых контуров
http://algolist.manual.ru/maths/geom/convhull/
Почему-то алгоритмы непосредственно для невыпуклых я сейчас не нашел.
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
03.02.2014, 17:34 6
Цитата Сообщение от wingblack Посмотреть сообщение
Почему-то алгоритмы непосредственно для невыпуклых
попробуйте формализовать задачу, решение которой ищите, и сразу поймете, почему ничего не нашли.
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
03.02.2014, 21:50  [ТС] 7
Igor3D,wingblack, Гуглил, но нашел только для выпуклых контуров, огромное количество примеров и методов, но для выпуклых контуров

и да, это совсем не сортировка массива по возрастанию)

Добавлено через 16 минут
Цитата Сообщение от salam Посмотреть сообщение
попробуйте формализовать задачу, решение которой ищите, и сразу поймете, почему ничего не нашли.
salam, в смысле Вы знаете как решить или как свести к сортировке массива?
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
03.02.2014, 21:58 8
AndrSlav, в смысле я не могу понять, что за задачу вы пытаетесь решить. перед поиском решения сначала нужно строго формализовать условие. пожалуйста, сделайте это для вашей задачи, тогда кто-то сможет вам помочь.

Добавлено через 3 минуты
хотя бы просто такое условие, чтобы была ясна суть.
1
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
03.02.2014, 22:05  [ТС] 9
Есть массив точек в 2D (на плоскости, рис.1), нужно их отсортировать так, чтобы при рисовании линии в соответствии с их порядком получилась замкнутая односвязная область (рис.2).
0
Миниатюры
Сортировка по контуру  
Mysterious Light
Эксперт по математике/физике
4082 / 1995 / 405
Регистрация: 19.07.2009
Сообщений: 3,012
Записей в блоге: 21
03.02.2014, 22:30 10
Найдите центр масс, сделайте его центром полярной системы координат, отсортируйте точки по углу:
http://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
x_c = \frac1N\sum_{i=1}^N x_i \\<br />
y_c = \frac1N\sum_{i=1}^N y_i \\<br />
r_i = \sqrt{(x_i-x_c)^2 + (y_i-y_c)^2} \\<br />
\varphi_i = \rm{arctg}\frac{x_i-x_c}{r_i}<br />

Контур, который получится после соединения, будет замкнутым и самонепересекающимся.
Вам такое подходит?
1
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
03.02.2014, 22:33  [ТС] 11
Цитата Сообщение от Igor3D Посмотреть сообщение
напр в точке 1 возможны ходы с расстояниями 5, 7, 10 ... В первый раз идем к ближайшей (точке с расстоянием 5). Альтернативы 7/5 и 10/5, этот относительный вес известен для всех пройденных точек. Выбираем наименьший (среди всех) и пробуем дальше.
Минимальное расстояние тоже пробовал, но не подходит. На рисунке во вложении обведенные точки на минимальном расстоянии, но не должны соединяться.
0
Миниатюры
Сортировка по контуру  
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
03.02.2014, 22:36  [ТС] 12
Mysterious Light, Этот алгоритм тоже не всегда работает(. Пример- во вложении.
0
Изображения
 
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
03.02.2014, 22:46  [ТС] 13
p.s. и в предыдущем примере тоже не будет работать.
pp.s. Mysterious Light, действительно, контур будет замкнутый и не пересекающийся, но очевидно, что он будет не тем, что надо, будут сплошные зигзаги.
0
Mysterious Light
Эксперт по математике/физике
4082 / 1995 / 405
Регистрация: 19.07.2009
Сообщений: 3,012
Записей в блоге: 21
03.02.2014, 23:16 14
Цитата Сообщение от AndrSlav Посмотреть сообщение
действительно, контур будет замкнутый и не пересекающийся, но очевидно, что он будет не тем, что надо, будут сплошные зигзаги.
Как сформулировали задачу, такое решение и было предложено. Обратите особое внимание на мудрое сообщение от salam:
Цитата Сообщение от salam Посмотреть сообщение
AndrSlav, в смысле я не могу понять, что за задачу вы пытаетесь решить. перед поиском решения сначала нужно строго формализовать условие. пожалуйста, сделайте это для вашей задачи, тогда кто-то сможет вам помочь.
P.S. никому же не ведомы Ваши критерии "тот что надо" и "не тот что надо" для контуров. Формализуйте задачу.
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
03.02.2014, 23:26  [ТС] 15
Mysterious Light, дополнительно к вышеуказанным условиям- контур должен быть максимально гладким, насколько возможно.
Я плохо умею формулировать мысли, это у меня давнишняя проблема)
0
Mysterious Light
Эксперт по математике/физике
4082 / 1995 / 405
Регистрация: 19.07.2009
Сообщений: 3,012
Записей в блоге: 21
03.02.2014, 23:44 16
Тогда я предлагаю формулировку:

Найти замкнутый контур, имеющий наименшую длину. Таким образом, длина будет мерой гладкости.
Эта задача является частным случаем (точнее, модификацией) задачи коммивояжёра. Одно из возможных стохастических решений — метод отжига.
1
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
03.02.2014, 23:57  [ТС] 17
Интересно, не слышал про такую задачу, почитаю.
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
04.02.2014, 00:30 18
На хабре как раз читал про отжиг.
http://habrahabr.ru/post/210942/
http://habrahabr.ru/search/?q=%D0%BE%D1%82%D0%B6%D0%B8%D0%B3

Если мои измышления будут тут полезны, то я понял метод отжига так:
ищем любой циклический маршрут, включающий все вершины
далее в цикле
в маршруте пытаемся поменять две вершины местами, если длина маршрута при этом уменьшается - оставляем новый маршрут.
или с заданной вероятностью вместо этого меняем местами две вершины без учета длинны маршрута.
повторять до определенного предела, например до ограничения максимального числа итераций.
можно повторить несколько раз для выбора наиболее короткого маршрута из найденных.
1
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
04.02.2014, 00:41  [ТС] 19
Как-то пока мне метод отжига не очень нравится- взял от балды коэффициент, посчитал, посмотрел результат, еще подогнал, время остановки вообще непонятно как выбрать, не надежно как-то, буду дальше разбираться.
p.s. На рисунке в статье видно, что в некоторых местах можно путь и покороче сделать (6 по горизонтали, 1 по вертикали, например). Метод хорош, если достаточен результат, похожий на верный.
pp.s. Метод перебора, конечно, идеален с точки зрения результата, но Вселенной уже не будет, когда посчитает. Хотя, для небольшого количества точек и метод перебора подойдет)
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2014, 11:27 20
Да нормально все сформулировано, ну может неудачно использован термин "сортировка". Кстати - однозначное решение здесь не гарантируется

Цитата Сообщение от AndrSlav Посмотреть сообщение
Минимальное расстояние тоже пробовал, но не подходит. На рисунке во вложении обведенные точки на минимальном расстоянии, но не должны соединяться.
Вот я и предлагаю когда заклинит - пробовать др ход. А критерий можно подобрать - напр ф-ция от расстояния и изменения угла. Ясно что в каких-то случаях этот алгоритм будет месить очень долго. Зато для простых контуров - быстрый ответ

Добавлено через 11 минут
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Как сформулировали задачу, такое решение и было предложено. Обратите особое внимание на мудрое сообщение от salam:


P.S. никому же не ведомы Ваши критерии "тот что надо" и "не тот что надо" для контуров. Формализуйте задачу.
Без проблем, предлагаю такую формулировку

построить простой полигон имея множество точек на плоскости
На всякий случай сообщаю что термин "простой полигон" означает полигон без само-пересечений но который может быть и не выпуклым (concave)
1
04.02.2014, 11:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.02.2014, 11:27

Вычислить интеграл по контуру
помощью вычетов вычислить данный интервал по контуру \oint_{L}(coszdz)/((z-3i)^2*(z+4i)); ...

Вычислить интеграл по контуру
\oint_{L}\frac{dz}{(z^3+z)(z+3)} где L\; :|z|=2

Интеграл по замкнутому контуру
Всем здравствуйте! Не знаю, как проинтегрировать по замкнутому контуру в Mathematica....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru