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

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

08.01.2014, 17:37. Просмотров 1551. Ответов 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
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
04.02.2014, 11:29 21
Цитата Сообщение от AndrSlav Посмотреть сообщение
Как-то пока мне метод отжига не очень нравится- взял от балды коэффициент, посчитал, посмотрел результат, еще подогнал, время остановки вообще непонятно как выбрать, не надежно как-то, буду дальше разбираться.
p.s. На рисунке в статье видно, что в некоторых местах можно путь и покороче сделать (6 по горизонтали, 1 по вертикали, например). Метод хорош, если достаточен результат, похожий на верный.
pp.s. Метод перебора, конечно, идеален с точки зрения результата, но Вселенной уже не будет, когда посчитает. Хотя, для небольшого количества точек и метод перебора подойдет)
Метод отжига удобен когда нужно найти пусть не самый кротчайший, но короткий путь, в случае когда вершин очень много и оптимальные алгоритмы будут работать достаточно долго. В статьях написано все правильно, в отличие от моего описания. Вероятность случайного перехода нужна чтобы алгоритм не застрял на каком-то маршруте, которые можно бы было и дальше оптимизировать. Но в том виде как я его описал даже не понятно как он вообще может застрять.

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

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

Так - на правах мозгового штурма.
2
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2014, 12:00 22
Цитата Сообщение от wingblack Посмотреть сообщение
Или как другое предложение - построить выпуклую фигуру, а потом дорабатывать её до контура по всем точкам, а правил можно много придумать - ближайшая точка к отрезку, ближайшая точка к точке уже включенной в контур, угол между отрезками, и другие, и их комбинация
Построить вмещающий выпуклый полигон - без проблем. Ну и дальше что? Опять приходим к какой-то "разумной эвристике", зачем же вводить подзадачу "вмещающий"? Так, чтобы побольше нагородить?
0
Mysterious Light
Эксперт по математике/физике
4082 / 1995 / 405
Регистрация: 19.07.2009
Сообщений: 3,012
Записей в блоге: 21
04.02.2014, 12:05 23
Цитата Сообщение от Igor3D Посмотреть сообщение
Да нормально все сформулировано, ну может неудачно использован термин "сортировка". Кстати - однозначное решение здесь не гарантируется
[...]
Без проблем, предлагаю такую формулировку
построить простой полигон имея множество точек на плоскости
На всякий случай сообщаю что термин "простой полигон" означает полигон без само-пересечений но который может быть и не выпуклым (concave)
Ну так предложенное мною решение как раз это и делает, вот только ТС это не понравилось, говорит, много зигзагов, неэстетично. Так что именно с формулировкой-то и проблема.

wingblack сформулировал второй критерий — изменение угла, направления в траектории.
Понятно, что речь идёт о переупорядочивании точек, каждой перестановке соотв. замкнутый маршрут, и среди всех таких замкнутых самонепересекающихся маршрутов мы хотим (и это ТС не сразу объяснил) выбрать самый-самый. Для этого нам нужна мера хорошести маршрута.
1) Длина пути. Чем меньше длина, тем лучше.
2) Изменение направления. Просто просуммироать все углы (по модулю), на которые при прохождении нужно повернуться. Чем меньше суммарный угол поворотов, тем плавнее кривая.

Из возможных алгоритмов:
1. Перебор. С отсечениями и прочей оптимизацией.
2. Стохастические методы: геналгоритмы, отжиг и др. Конечно, за конечное время вероятность найти абсолютно оптимальное решение не 100%, но обычно довольно быстро алгоритм находит приемлемое решение.
3. Эвристика. Например, я заметил, что у Вас такая траектория вырисовывается по-человечески однозначно, и точки лежат недалеко друг от друга. Стало быть, можно взять, например, полный перебор, но на перебираемые варианты наложить такое условие:
у каждой точки маршрута справа и слева должны быть точки из числа 10 (например) близжайших к ней.
Тогда сложность перебора будет не факториальная, а экспоненциальная... ну хоть так-то...
1
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
04.02.2014, 14:58 24
Igor3D, скажите тогда, устраивает ли вас алгоритм, возвращающий при любых входных данных тройку точек, образующих треугольник. Если нет, то какому пункту условия он противоречит.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2014, 15:59 25
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Ну так предложенное мною решение как раз это и делает, вот только ТС это не понравилось, говорит, много зигзагов, неэстетично. Так что именно с формулировкой-то и проблема.
Поверьте, когда появляется противное словечко "concave" - это автоматически означает что "центр масс" неприменим. Не получите Вы полигона без само-пересечений. Кстати взвешенный центр точек не есть центр масс.

Цитата Сообщение от Mysterious Light Посмотреть сообщение
у каждой точки маршрута справа и слева должны быть точки из числа 10 (например) близжайших к ней.Тогда сложность перебора будет не факториальная, а экспоненциальная... ну хоть так-то...
А нас никто не гонит, можно начать и с 3 точек, а по мере необходимости пополнять. И создать кеш ближайших - детская забава. С этой точки зрения тупенький "алгоритм с развратом" привлекателен.

Цитата Сообщение от salam Посмотреть сообщение
Igor3D, скажите тогда, устраивает ли вас алгоритм, возвращающий при любых входных данных тройку точек, образующих треугольник. Если нет, то какому пункту условия он противоречит.
Можно долго играть в схоластику, но логикой ее считать не следует. Четкая постановка всегда нужна, но доходить до абсурда не надо. Типа "вот будет хороший вопрос - будет и ответ" - и пусть спрашивающий бьется в потугах, а я покритикую. Только все это уже проходили и знают что ответа у "тщательно формализующего" как не было - так и не будет
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
04.02.2014, 16:13 26
Igor3D, я не меньше вашего добиваюсь прагматизма, но я искренне не понимаю, как можно придумывать алгоритм для построения объекта, свойств которого мы не знаем. может быть и правда мне одному не понятна какая-то простая истина. Я пытаюсь это устранить, задавая вам вопросы. Например, последний. Результатом его обсуждения могло быть либо то, что мне намекнут, чего я не понял, либо мы договоримся, что этот ужасный объект должен содержать все точки множества. Это уже был бы, лично для меня, шаг вперед.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2014, 17:41 27
Цитата Сообщение от salam Посмотреть сообщение
, либо мы договоримся, что этот ужасный объект должен содержать все точки множества. Это уже был бы, лично для меня, шаг вперед.
(полигон - вполне официальный термин, лучше использовать его)

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

- найти максимум в массиве содержащем N элементов.

Теперь, следуя предложенной методе: "А я вот нашел максимум по первым двум" - ну мало ли, было сказано "содержащем", а что по всем надо искать - такого не говорили!!! А можно еще углубляться в детали типа "а какой же максимум имеется ввиду?" Словом - во всем надо знать меру.

Возвращаясь к задаче - вопрос о "хорошести" найденного полигона не стоял и не стоит. "Найти простой (без само-пересечений) - и все. Легко показать что решение может быть не единственным, поэтому кто там "лучший" - уже др задача.
0
Mysterious Light
Эксперт по математике/физике
4082 / 1995 / 405
Регистрация: 19.07.2009
Сообщений: 3,012
Записей в блоге: 21
04.02.2014, 18:15 28
Цитата Сообщение от Igor3D Посмотреть сообщение
Возвращаясь к задаче - вопрос о "хорошести" найденного полигона не стоял и не стоит. "Найти простой (без само-пересечений) - и все. Легко показать что решение может быть не единственным, поэтому кто там "лучший" - уже др задача.
Сортировка по контуру
Отсортированные по полярному углу (центр координат в центре масс) точки, если их соединить по порядку, а также последний с первым, образуют замкнутый полигон без самопересечений. То, что этот полигон не самопересекается, следует из того, что любые два отрезка заметают непересекающиеся углы (т.е. если соединить концы каждого отрезка с центром координат, то никакие два образованных треугольника не пересекаются кроме как по стороне).
ТС сказал:
Цитата Сообщение от AndrSlav Посмотреть сообщение
действительно, контур будет замкнутый и не пересекающийся, но очевидно, что он будет не тем, что надо, будут сплошные зигзаги.
Поэтому именно о "лучшем" непересек. замкнутом полигоне идёт речь, а не о каком-либо вообще.
Притом, как я понимаю, речь идёт о полигоне, который проходит все точки, и только их имеет своими вершинами.

Впрочем, пусть ТС нас рассудит, ведь это его задача.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2014, 18:48 29
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Сортировка по контуру
Отсортированные по полярному углу (центр координат в центре масс) точки, если их соединить по порядку, а также последний с первым, образуют замкнутый полигон без самопересечений. То, что этот полигон не самопересекается, следует из того, что любые два отрезка заметают непересекающиеся углы (т.е. если соединить концы каждого отрезка с центром координат, то никакие два образованных треугольника не пересекаются кроме как по стороне).
Наверное Вы хотели сказать "замкнутая полилиния", т.к. полигон и так всегда замкнут. Но с чего Вы взяли что средневзвешенный центр обязательно лежит внутри полигона? Он может с успехом быть снаружи - и тогда Ваша полилиния не замкнется. Заметим что для convex это прекрасно проходит - и центр всегда внутри, и замыкается, и полигон получается верный.

Ну и понятно что это "звезда" со сколь угодно острыми лучами. Формально да - тоже полигон, но очевидно это совсем не то что хотел ТС. Конечно можно упираться (дескать, нет постановки и все такое) - но это ничего нового не вносит. ТС показал вполне нормальные, житейские контуры, интуитивно мы мгновенно понимаем ожидаемый результат - поэтому не будем придираться
0
Mysterious Light
Эксперт по математике/физике
4082 / 1995 / 405
Регистрация: 19.07.2009
Сообщений: 3,012
Записей в блоге: 21
04.02.2014, 19:02 30
Цитата Сообщение от Igor3D Посмотреть сообщение
Но с чего Вы взяли что средневзвешенный центр обязательно лежит внутри полигона? Он может с успехом быть снаружи - и тогда Ваша полилиния не замкнется. Заметим что для convex это прекрасно проходит - и центр всегда внутри, и замыкается, и полигон получается верный.
Я так полигон строю, что центр тяжести всегда внутри будет. По-хорошему, для работы этого алгоритма в качестве центра подойдет любая точка внутри выпуклой оболочки этого множества точек.

Цитата Сообщение от Igor3D Посмотреть сообщение
Формально да - тоже полигон, но очевидно это совсем не то что хотел ТС. Конечно можно упираться (дескать, нет постановки и все такое) - но это ничего нового не вносит. ТС показал вполне нормальные, житейские контуры, интуитивно мы мгновенно понимаем ожидаемый результат - поэтому не будем придираться
Ладно, сойдёмся на том, что мне не понятно то, что понятно Вам. Мне, например, не очевидно, чем один полигон хуже/лучше другого в контексте поставленной задачи. Вам понятно, что звезда не подходит? Тогда объясните мне, где тот критерий, который указывает, что вот конкретно этот полигон подходит, а вот конкретно тот — нет.
А ещё мне не понятно, как Вы, Igor3D, так быстро меняете свои суждения, от
Цитата Сообщение от Igor3D Посмотреть сообщение
Возвращаясь к задаче - вопрос о "хорошести" найденного полигона не стоял и не стоит. "Найти простой (без само-пересечений) - и все. Легко показать что решение может быть не единственным, поэтому кто там "лучший" - уже др задача.
до
Цитата Сообщение от Igor3D Посмотреть сообщение
Формально да - тоже полигон, но очевидно это совсем не то что хотел ТС
Впрочем, по моему мнению, несколько приемлемых решений уже было высказано в теме (в основном, wingblack). Мы с salam пытаемся понять, что хочет ТС, а Вы, Igor3D, понимаете, но не объясняете и никакого кода (ни идеи) не предлагаете...
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2014, 20:09 31
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Мы с salam пытаемся понять, что хочет ТС, а Вы, Igor3D, понимаете, но не объясняете
Посмотрите на картинки приведенные ТС в постах #11 и #12. Вы ведь моментально уловили какой результат ожидается, не так ли? Можно еще проще, напр (звездочки = точки)

* ****
* ****
* *
* *
Ожидаемый результат - буква "Г", а что будет с центром/звездой? Бяка-маляка?

Цитата Сообщение от Mysterious Light Посмотреть сообщение
.. и никакого кода (ни идеи) не предлагаете...
Я уже предложил примитивный алгоритм, но кто знает - иногда примитивный оказывается лучше умных/тонких. Возможно это тот случай. Ищем след точку по углу и расстоянию. Оцениваем и записываем "качество хода". Само-пересеклись - заменяем "наихудший" ход и продолжаем от него.
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
04.02.2014, 20:57  [ТС] 32
Спасибо за интересные предложения, почитал в интернете про задачу коммивояжера. Mysterious Light прав, искомый контур должен иметь минимальный периметр. Попробовал перебором- получилось идеально с точки зрения конечного результата, но если точек много- очень долго, несколько спасает положение то, что сначала сортирую по описывающему контуру, а дальше добавляю точки перебором вариантов.
Пока мне видятся следующие улучшения:
1. Для перебора брать ближайшие точки и только те, что не образуют пересечений при добавлении, т.е. в предположении, что фигура на всем промежутке "роста" представляет собой односвязную область (сейчас тупо перебор всех вариантов).
2. Все же метод отжига, но результат проверять на пересечение и запускать заново, если пересечения есть.

Добавлено через 6 минут
salam, все точки должны быть использованы.

Добавлено через 4 минуты
Igor3D, Простых алгоритмов кучу перепробовал, и каждый где-то ошибается. Сейчас склоняюсь к мнению, что единственный правильный критерий- минимальный периметр. Т.е. контур с минимальным периметром 100% дает нужный результат, вопрос в том есть ли другое условие, позволяющее решить задачу быстрее.
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
04.02.2014, 21:09 33
salam, все точки должны быть использованы.
Тогда расскажите, чем плох алгоритм посортить все точки по у-координате. Для каждой координаты взять в ответ самую левую и самую праву точки. Все точки содержатся, замкнуто, без самопересечений, решается за сложность сортировки.
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
05.02.2014, 00:38  [ТС] 34
Цитата Сообщение от salam Посмотреть сообщение
Тогда расскажите, чем плох алгоритм посортить все точки по у-координате. Для каждой координаты взять в ответ самую левую и самую праву точки.
Не уверен, что правильно понял. Берете точки 1 и 2, потом добавляете 3 и 4, потом 5 и 6, таким образом как бы строя ветви 135 и 246, которые наверху соединятся? Но в случае на второй картинке при достижении точек i и j надо брать k и m, а берутся, в соответствии с алгоритмом, n и p. Если не так понял, поправьте, пожалуйста.
0
Миниатюры
Сортировка по контуру  
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
05.02.2014, 07:56 35
Да, так не хорошо. Я думал о другом случае.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
05.02.2014, 09:57 36
А если так: сначала строим вмещающий выпуклый полигон. Затем, до тех пор пока есть внутренние точки еще не включенные в полигон

- находим точку с минимальным расстоянием до сегмента/отрезка,
- включаем эту точку в данный отрезок
1
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
06.02.2014, 20:50  [ТС] 37
Igor3D, эта мысль тоже была). Рассмотрим рисунок выше (правый), после построения выпуклого полигона первая точка для внесения- точка слева над точкой n, что не верно.
Я усложнял и варьировал условия, но результата с таким алгоритмом не добился.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
07.02.2014, 12:02 38
Цитата Сообщение от AndrSlav Посмотреть сообщение
Igor3D, эта мысль тоже была). Рассмотрим рисунок выше (правый), после построения выпуклого полигона первая точка для внесения- точка слева над точкой n, что не верно.
Согласен. Тогда может повторить выделение выпуклого для оставшихся точек - но тут надо как-то выделять "кластера".

Однозначности здесь нет, надо к этому отнестись спокойно
0
07.02.2014, 12:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2014, 12:02

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

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

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


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

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

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