|
71 / 59 / 14
Регистрация: 20.12.2013
Сообщений: 732
|
|
Сортировка по контуру08.01.2014, 17:37. Показов 3261. Ответов 37
Метки нет (Все метки)
Здравствуйте, подскажите, пожалуйста, алгоритмы или соответствующую литературу, по которым можно отсортировать точки, задающие односвязный контур на плоскости в общем случае, т.е. не обязательно выпуклый.
0
|
|
| 08.01.2014, 17:37 | |
|
Ответы с готовыми решениями:
37
Резка по контуру Заливка по контуру Распознавание по контуру |
|
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
|
||
| 04.02.2014, 11:29 | ||
|
Попробуй вначале просто применить задачу коммивояжера. (возможно потребуется добавить проверку на пересечение отрезков) Так же из простых решений мне видится минимальные расстояния, угол между предыдущем и новым(предполагаемым) отрезком, а также композиция этих признаков, а также изменение коэффициентов для них с повторным проходом если остались незатронутые точки. Или как другое предложение - построить выпуклую фигуру, а потом дорабатывать её до контура по всем точкам, а правил можно много придумать - ближайшая точка к отрезку, ближайшая точка к точке уже включенной в контур, угол между отрезками, и другие, и их комбинация Так - на правах мозгового штурма.
2
|
||
| 04.02.2014, 12:00 | ||
0
|
||
|
|
||
| 04.02.2014, 12:05 | ||
|
wingblack сформулировал второй критерий — изменение угла, направления в траектории. Понятно, что речь идёт о переупорядочивании точек, каждой перестановке соотв. замкнутый маршрут, и среди всех таких замкнутых самонепересекающихся маршрутов мы хотим (и это ТС не сразу объяснил) выбрать самый-самый. Для этого нам нужна мера хорошести маршрута. 1) Длина пути. Чем меньше длина, тем лучше. 2) Изменение направления. Просто просуммироать все углы (по модулю), на которые при прохождении нужно повернуться. Чем меньше суммарный угол поворотов, тем плавнее кривая. Из возможных алгоритмов: 1. Перебор. С отсечениями и прочей оптимизацией. 2. Стохастические методы: геналгоритмы, отжиг и др. Конечно, за конечное время вероятность найти абсолютно оптимальное решение не 100%, но обычно довольно быстро алгоритм находит приемлемое решение. 3. Эвристика. Например, я заметил, что у Вас такая траектория вырисовывается по-человечески однозначно, и точки лежат недалеко друг от друга. Стало быть, можно взять, например, полный перебор, но на перебираемые варианты наложить такое условие: у каждой точки маршрута справа и слева должны быть точки из числа 10 (например) близжайших к ней. Тогда сложность перебора будет не факториальная, а экспоненциальная... ну хоть так-то...
1
|
||
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
| 04.02.2014, 14:58 | |
|
Igor3D, скажите тогда, устраивает ли вас алгоритм, возвращающий при любых входных данных тройку точек, образующих треугольник. Если нет, то какому пункту условия он противоречит.
0
|
|
| 04.02.2014, 15:59 | ||||
0
|
||||
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
| 04.02.2014, 16:13 | |
|
Igor3D, я не меньше вашего добиваюсь прагматизма, но я искренне не понимаю, как можно придумывать алгоритм для построения объекта, свойств которого мы не знаем. может быть и правда мне одному не понятна какая-то простая истина. Я пытаюсь это устранить, задавая вам вопросы. Например, последний. Результатом его обсуждения могло быть либо то, что мне намекнут, чего я не понял, либо мы договоримся, что этот ужасный объект должен содержать все точки множества. Это уже был бы, лично для меня, шаг вперед.
0
|
|
| 04.02.2014, 17:41 | ||
|
Не нужно так "перегибать палку". Если часть исходных данных может быть проигнорирована, то постановщик обязан был это указать - но не наоборот. Пример - найти максимум в массиве содержащем N элементов. Теперь, следуя предложенной методе: "А я вот нашел максимум по первым двум" - ну мало ли, было сказано "содержащем", а что по всем надо искать - такого не говорили!!! А можно еще углубляться в детали типа "а какой же максимум имеется ввиду?" Словом - во всем надо знать меру.Возвращаясь к задаче - вопрос о "хорошести" найденного полигона не стоял и не стоит. "Найти простой (без само-пересечений) - и все. Легко показать что решение может быть не единственным, поэтому кто там "лучший" - уже др задача.
0
|
||
|
|
|||
| 04.02.2014, 18:15 | |||
|
Отсортированные по полярному углу (центр координат в центре масс) точки, если их соединить по порядку, а также последний с первым, образуют замкнутый полигон без самопересечений. То, что этот полигон не самопересекается, следует из того, что любые два отрезка заметают непересекающиеся углы (т.е. если соединить концы каждого отрезка с центром координат, то никакие два образованных треугольника не пересекаются кроме как по стороне). ТС сказал: Притом, как я понимаю, речь идёт о полигоне, который проходит все точки, и только их имеет своими вершинами. Впрочем, пусть ТС нас рассудит, ведь это его задача.
0
|
|||
| 04.02.2014, 18:48 | ||
|
Ну и понятно что это "звезда" со сколь угодно острыми лучами. Формально да - тоже полигон, но очевидно это совсем не то что хотел ТС. Конечно можно упираться (дескать, нет постановки и все такое) - но это ничего нового не вносит. ТС показал вполне нормальные, житейские контуры, интуитивно мы мгновенно понимаем ожидаемый результат - поэтому не будем придираться
0
|
||
|
|
|||||
| 04.02.2014, 19:02 | |||||
|
А ещё мне не понятно, как Вы, Igor3D, так быстро меняете свои суждения, от
0
|
|||||
| 04.02.2014, 20:09 | |||
|
* **** * **** * * * * Ожидаемый результат - буква "Г", а что будет с центром/звездой? Бяка-маляка? ![]()
0
|
|||
|
71 / 59 / 14
Регистрация: 20.12.2013
Сообщений: 732
|
|
| 04.02.2014, 20:57 [ТС] | |
|
Спасибо за интересные предложения, почитал в интернете про задачу коммивояжера. Mysterious Light прав, искомый контур должен иметь минимальный периметр. Попробовал перебором- получилось идеально с точки зрения конечного результата, но если точек много- очень долго, несколько спасает положение то, что сначала сортирую по описывающему контуру, а дальше добавляю точки перебором вариантов.
Пока мне видятся следующие улучшения: 1. Для перебора брать ближайшие точки и только те, что не образуют пересечений при добавлении, т.е. в предположении, что фигура на всем промежутке "роста" представляет собой односвязную область (сейчас тупо перебор всех вариантов). 2. Все же метод отжига, но результат проверять на пересечение и запускать заново, если пересечения есть. Добавлено через 6 минут salam, все точки должны быть использованы. Добавлено через 4 минуты Igor3D, Простых алгоритмов кучу перепробовал, и каждый где-то ошибается. Сейчас склоняюсь к мнению, что единственный правильный критерий- минимальный периметр. Т.е. контур с минимальным периметром 100% дает нужный результат, вопрос в том есть ли другое условие, позволяющее решить задачу быстрее.
0
|
|
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
||
| 04.02.2014, 21:09 | ||
0
|
||
|
71 / 59 / 14
Регистрация: 20.12.2013
Сообщений: 732
|
||
| 05.02.2014, 00:38 [ТС] | ||
|
0
|
||
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
| 05.02.2014, 07:56 | |
|
Да, так не хорошо. Я думал о другом случае.
0
|
|
| 05.02.2014, 09:57 | |
|
А если так: сначала строим вмещающий выпуклый полигон. Затем, до тех пор пока есть внутренние точки еще не включенные в полигон
- находим точку с минимальным расстоянием до сегмента/отрезка, - включаем эту точку в данный отрезок
1
|
|
|
71 / 59 / 14
Регистрация: 20.12.2013
Сообщений: 732
|
|
| 06.02.2014, 20:50 [ТС] | |
|
Igor3D, эта мысль тоже была). Рассмотрим рисунок выше (правый), после построения выпуклого полигона первая точка для внесения- точка слева над точкой n, что не верно.
Я усложнял и варьировал условия, но результата с таким алгоритмом не добился.
0
|
|
| 07.02.2014, 12:02 | ||
|
Однозначности здесь нет, надо к этому отнестись спокойно
0
|
||
| 07.02.2014, 12:02 | |
|
Интеграл по замкнутому контуру Вычислить интеграл по контуру Криволинейный интеграл по контуру Вычислить интеграл по контуру - 2
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|