|
||
| Правила | Регистрация | Пользователи | Поиск | Сообщения за день | Все разделы прочитаны | Справка по форуму | Файлообменник | |
|
Поиск в этой теме |
09.07.2020, 20:22 | #1 | |
Алгоритм "построителя дорог"
Регистрация: 04.07.2020
Сообщений: 26
|
||
Просмотров: 7911
|
|
||||
Регистрация: 18.12.2010
Сообщений: 5,047
|
|
|||
|
||||
Регистрация: 04.07.2020
Сообщений: 26
|
Цитата:
|
|||
|
||||
Проектировщик электрических сетей Регистрация: 17.01.2014
Пенза
Сообщений: 176
|
Вы бы прикрепили пример того что вы имеете с прибора и то что вы хотите получить. Лучше несколько примеров, простые, сложные, странные... Тогда можно дискутировать, я вот не совсем понял что вы получаете с прибора, какие точки.
|
|||
|
||||
Проектировщик электрических сетей Регистрация: 17.01.2014
Пенза
Сообщений: 176
|
Я как понял ему надо не рельеф построить. А по точкам провести полилинию, так что бы она прошла по нужным точкам.
|
|||
|
||||
КЖ; C# Регистрация: 03.11.2005
Санкт-Петербург
Сообщений: 2,587
|
Задача похожа на нахождение минимальной выпуклой оболочки... соответственно, ИМХО, и копать нужно в ту сторону.
|
|||
|
||||
YngIngKllr Регистрация: 29.03.2005
СПб
Сообщений: 12,968
|
1. Нужно пример с точками
2. Нужно понять что хотим получить по итогу.. 3. Может быть если это разовая работа, сделать полуавтоматический вариант алгоритма, который будет соединять точки.
__________________
Работаю за еду. Working for food. Für Essen arbeiten. العمل من أجل الغذاء Працую за їжу. |
|||
|
||||
Регистрация: 04.07.2020
Сообщений: 26
|
именно так
----- добавлено через ~2 мин. ----- Я посмотрел Вашу ссылку. Да. Похожа. Но оболочка не обязательно будет выпуклой. Даже в подавляющем большинстве случаев как раз наоборот |
|||
|
||||
Регистрация: 04.07.2020
Сообщений: 26
|
К сожалению я не нашел как тут прикрепить файл
----- добавлено через ~1 мин. ----- не совсем Вас понял ----- добавлено через ~3 мин. ----- есть один вариант, но он предполагает "правильный" обход, что не всегда возможно |
|||
|
||||
сети Регистрация: 03.11.2008
Московия*
Сообщений: 5,763
|
|
|||
|
||||
Регистрация: 04.07.2020
Сообщений: 26
|
ну, например, одна сторона дороги имеет какой-нибудь сложный контур (карман, например), а вторая просто прямая. Когда человек окажется на стороне сложного контура, то скорее всего, он сначала обойдет его (в несколько точек), а только потом вернется на первую сторону (таким образом зигзаг будет нарушен). Но допустим даже, зная все нюансы, я может и мог бы ходить удобным образом для алгоритма. Но иногда мне приходится чертить то, что обходили другие люди.
|
|||
|
||||
Регистрация: 09.11.2017
Сообщений: 28
|
https://vestnik.utmn.ru/upload/ibloc...0%BE%D0%B2.pdf - здесь рассматривается реализация похожей задачи.
Очередность и направление обхода значения не имеют. Построили минимальную выпуклую оболочку, исключили точки ставшие ее вершинами. Вычислили параметр (getParamAtPoint) каждой из оставшихся точек по отношению к МВО и отсортировали их по возрастанию этого параметра. Поочередно добавляем отсортированные точки как новые вертексы МВО. Единственный нюанс - контроль внутренних (находящихся внутри контура) точек если таковые имеются. Тогда надо контролировать разницу углов между старым и новым направлением участка МВО. |
|||
|
||||
Проектировщик электрических сетей Регистрация: 17.01.2014
Пенза
Сообщений: 176
|
Цитата:
|
|||
|
||||
Регистрация: 04.07.2020
Сообщений: 26
|
|
|||
|
||||
Регистрация: 04.07.2020
Сообщений: 26
|
----- добавлено через ~7 мин. ----- Цитата:
Берем ограничивающий прямоугольник, такой, что все точки дороги находятся внутри него, а некоторые будут лежать на его гранях. Берем одну такую точку (лежащую на какой-либо из четырех граней) и через нее и середину смежной грани проводим отрезок. Таким образом мы перешли от ограничивающего прямоугольника к пятиугольнику. Некоторые точки могут повылезать за его границы. В таком случае берем одну из вылезших точек (с самой маленькой координатой y, например, и через нее и бывшую "середину смежной грани" проводим отрезок. Часть точек залезут обратно внутрь новообразованной фигуры. И, в общем, подобными действиями через некоторое количество итераций фигура сформируется таким образом, что будет повторять контур дороги и, если в ней (дороге) нет никаких замкнутых областей - "недорожных островков", то задача решена. Чтобы понять, что точка лежит снаружи фигуры можно воспользоваться википедией: https://en.wikipedia.org/wiki/Point_in_polygon Последний раз редактировалось myranda, 11.07.2020 в 09:56. |
|||
|
||||
Регистрация: 04.07.2020
Сообщений: 26
|
уже ни в чем. просто привел решение для завершенности темы
----- добавлено через ~1 мин. ----- триангуляция - это построение треугольников? |
|||
|
||||
Регистрация: 02.10.2016
Сообщений: 205
|
у каждой точки находим её 7 соеседних(по наименьшему расстоянию).
получаем семь отрезков. эту процедуру проделоваем со всеми точками. получаем массив отрезков. затем ищем пересекающиеся отрезки. те отрезки которые не имеют пересечения и будут контуром дороги. |
|||
|
||||
Регистрация: 04.07.2020
Сообщений: 26
|
Логично. Но может быть случай, например, когда по одной стороне дороги точки стоят с большими пробелами (скажем дорога прямая), а по другой довольно плотно (например, на этой стороне много карманов, выступов). Тогда отрезки дороги (по прореженной стороне) не войдут в наборы семерок, а следовательно выпадут из рассмотрения и не будут построены
|
|||
|
||||
YngIngKllr Регистрация: 29.03.2005
СПб
Сообщений: 12,968
|
А не проще ли сетку(mesh) построить сперва.
А потом определить её контур. После этого работать с получившимся контуром. Сперва построив срединую линию для контура. ----- добавлено через ~4 мин. ----- Для построения mesh есть различные библиотеки. Для получения контура можно использовать следующий алгоритм. Сделать список граней треугольников, если грань встречается дважды то удалять её из набора. Срединную линию тоже построить можно. ----- добавлено через ~11 мин. ----- Я бы для такого построителя использовал пайтон. В принципе библиотек у него достаточно..
__________________
Работаю за еду. Working for food. Für Essen arbeiten. العمل من أجل الغذاء Працую за їжу. |
|||
|
||||
Регистрация: 02.10.2016
Сообщений: 205
|
Цитата:
----- добавлено через ~1 мин. ----- Цитата:
|
|||
|
Опции темы | Поиск в этой теме |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Какой язык перспективен для инженера-конструктора с условием | The_Mercy_Seat | Программирование | 705 | 17.03.2021 14:19 |
Алгоритм построения стропильной системы в Revit 2016 | Tyhig | Revit | 8 | 07.11.2017 15:30 |
Нужен алгоритм расчета каркасной перегородки с нагрузками | LarisaK | Поиск исполнителей | 0 | 07.03.2016 16:44 |
Алгоритм брезенхема для 4 осей | vova_kansk | Программирование | 5 | 16.07.2014 11:28 |
Ошибка при зумировании листа. Алгоритм печати в модели и в листе | Rask | Программирование | 8 | 30.08.2012 13:54 |