| Правила | Регистрация | Пользователи | Поиск | Сообщения за день | Все разделы прочитаны |  Справка по форуму | Файлообменник |

Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Алгоритм "построителя дорог"

Алгоритм "построителя дорог"

Ответ
Поиск в этой теме
Непрочитано 09.07.2020, 20:22 #1
Алгоритм "построителя дорог"
myranda
 
Регистрация: 04.07.2020
Сообщений: 26

Здравствуйте. Есть набор трехмерных точек (по сути координата z в них не важна, поэтому двумерных), полученных геодезическими методами. Это точки, взятые по краю дороги. Необходимо соединить их таким образом, чтобы получилась дорога. Вообще говоря, точки пронумерованы. Когда участок дороги обходится по замкнутому контуру (сначала по одному краю в одну сторону, после - переход на другую сторону и по этой стороне возвращаюсь к исходной точке) - проблем нет никаких. Но иногда обход может быть и другим - например, зигзагом (одна сторона - чуть вперед другая сторона - чуть вперед - первая сторона и т.д.), иногда и зигзаг (по зашпарке) может быть не правильным. В общем случае, есть просто набор точек, соответствующих краям дороги, на нумерацию которых не следует обращать внимания. По этим точкам нужно восстановить контур дороги. Пока что ничего не приходит в голову - только то, что должно выполняться условие, что длинна замкнутого контура должна быть наименьшей. Но чтобы в этом убедиться - нужно построить все возможные замкнутые контуры, в которых каждая точка вершина только на двух ребрах, а таковых $n!$. Еще где - то маячит мысль о том, что дорога должна иметь какое то более-менее направление на плоскости, т.е. приблизительно лежать вдоль какой-то прямой, но как правильно это использовать - понимания пока нет

-- 09.07.2020, 19:07 --

Возможно не самая оптимальная мысль, но можно разбить весь рассматриваемый участок на квадраты. Затем пробежаться по всем точкам, чтобы понять в какие из квадратов они попадают (помечая эти квадраты). затем соединить центры помеченных квадратов, таким образом составить примерную линию направленности дороги
Правда, если дорога будет извилистой или, еще хуже, с перекрестками - это сильно осложняет задачу
Просмотров: 7912
 
Непрочитано 09.07.2020, 21:51
#2
trir


 
Регистрация: 18.12.2010
Сообщений: 5,047


https://habr.com/ru/company/croc/blog/301178/
trir вне форума  
 
Автор темы   Непрочитано 09.07.2020, 22:26
#3
myranda


 
Регистрация: 04.07.2020
Сообщений: 26


Цитата:
Сообщение от trir Посмотреть сообщение
но это не совсем то. По потоку изображений с камеры действительно можно построить 3д модель окружающего пространства и вычислить положение и ориентацию этой камеры в нем. Эти вопросы по большей части в ведении такого направления техники, как техническое зрение. У меня же задача на порядок более простая. Но все-равно спасибо за ссылку
myranda вне форума  
 
Непрочитано 09.07.2020, 22:54
#4
veb86

Проектировщик электрических сетей
 
Регистрация: 17.01.2014
Пенза
Сообщений: 176


Вы бы прикрепили пример того что вы имеете с прибора и то что вы хотите получить. Лучше несколько примеров, простые, сложные, странные... Тогда можно дискутировать, я вот не совсем понял что вы получаете с прибора, какие точки.
veb86 вне форума  
 
Непрочитано 09.07.2020, 23:09
#5
CalcProg


 
Регистрация: 02.10.2016
Сообщений: 205


триангуляция. практикум по инженерной геодезии.

----- добавлено через ~4 мин. -----
ну и книжки описывающие способы построения триангуляционной сетки. способов много. один из них разбиение на квадраты.
CalcProg вне форума  
 
Непрочитано 10.07.2020, 00:33
#6
veb86

Проектировщик электрических сетей
 
Регистрация: 17.01.2014
Пенза
Сообщений: 176


Цитата:
Сообщение от CalcProg Посмотреть сообщение
триангуляция. практикум по инженерной геодезии.

----- добавлено через ~4 мин. -----
ну и книжки описывающие способы построения триангуляционной сетки. способов много. один из них разбиение на квадраты.
Я как понял ему надо не рельеф построить. А по точкам провести полилинию, так что бы она прошла по нужным точкам.
veb86 вне форума  
 
Непрочитано 10.07.2020, 08:02
#7
Boxa

КЖ; C#
 
Регистрация: 03.11.2005
Санкт-Петербург
Сообщений: 2,587


Задача похожа на нахождение минимальной выпуклой оболочки... соответственно, ИМХО, и копать нужно в ту сторону.
Boxa вне форума  
 
Непрочитано 10.07.2020, 08:54
#8
DEM

YngIngKllr
 
Регистрация: 29.03.2005
СПб
Сообщений: 12,968


1. Нужно пример с точками
2. Нужно понять что хотим получить по итогу..
3. Может быть если это разовая работа, сделать полуавтоматический вариант алгоритма, который будет соединять точки.
__________________
Работаю за еду.
Working for food.
Für Essen arbeiten.
العمل من أجل الغذاء
Працую за їжу.
DEM вне форума  
 
Автор темы   Непрочитано 10.07.2020, 18:43
#9
myranda


 
Регистрация: 04.07.2020
Сообщений: 26


Цитата:
Сообщение от veb86 Посмотреть сообщение
А по точкам провести полилинию, так что бы она прошла по нужным точкам.
именно так

----- добавлено через ~2 мин. -----
Цитата:
Сообщение от Boxa Посмотреть сообщение
Задача похожа
Я посмотрел Вашу ссылку. Да. Похожа. Но оболочка не обязательно будет выпуклой. Даже в подавляющем большинстве случаев как раз наоборот
myranda вне форума  
 
Непрочитано 10.07.2020, 19:08
#10
engngr

сети
 
Регистрация: 03.11.2008
Московия*
Сообщений: 5,763


Offtop:
Цитата:
Сообщение от myranda Посмотреть сообщение
Но иногда обход может быть и другим - например, зигзагом
Одну сторону некошерно снять было, шаббатно.
engngr вне форума  
 
Автор темы   Непрочитано 10.07.2020, 19:09
#11
myranda


 
Регистрация: 04.07.2020
Сообщений: 26


Цитата:
Сообщение от DEM Посмотреть сообщение
1. Нужно пример с точками
2. Нужно понять что хотим получить по итогу..
К сожалению я не нашел как тут прикрепить файл

----- добавлено через ~1 мин. -----
Цитата:
Сообщение от engngr Посмотреть сообщение
Одну сторону некошерно снять было, шаббатно.
не совсем Вас понял

----- добавлено через ~3 мин. -----
Цитата:
Сообщение от DEM Посмотреть сообщение
3. Может быть если это разовая работа, сделать полуавтоматический вариант алгоритма, который будет соединять точки.
есть один вариант, но он предполагает "правильный" обход, что не всегда возможно
myranda вне форума  
 
Непрочитано 10.07.2020, 19:13
#12
engngr

сети
 
Регистрация: 03.11.2008
Московия*
Сообщений: 5,763


Цитата:
Сообщение от myranda Посмотреть сообщение
не совсем Вас понял
Я имел в виду это:
Цитата:
Сообщение от myranda Посмотреть сообщение
есть один вариант, но он предполагает "правильный" обход
Почему это не всегда возможно?

Номера или имена точек можно было бы привязать к стороне еще, например.
engngr вне форума  
 
Автор темы   Непрочитано 10.07.2020, 20:12
#13
myranda


 
Регистрация: 04.07.2020
Сообщений: 26


Цитата:
Сообщение от engngr Посмотреть сообщение
Почему это не всегда возможно?
ну, например, одна сторона дороги имеет какой-нибудь сложный контур (карман, например), а вторая просто прямая. Когда человек окажется на стороне сложного контура, то скорее всего, он сначала обойдет его (в несколько точек), а только потом вернется на первую сторону (таким образом зигзаг будет нарушен). Но допустим даже, зная все нюансы, я может и мог бы ходить удобным образом для алгоритма. Но иногда мне приходится чертить то, что обходили другие люди.
myranda вне форума  
 
Непрочитано 10.07.2020, 21:02
| 1 #14
Alex.gomel


 
Регистрация: 09.11.2017
Сообщений: 28


https://vestnik.utmn.ru/upload/ibloc...0%BE%D0%B2.pdf - здесь рассматривается реализация похожей задачи.
Очередность и направление обхода значения не имеют. Построили минимальную выпуклую оболочку, исключили точки ставшие ее вершинами. Вычислили параметр (getParamAtPoint) каждой из оставшихся точек по отношению к МВО и отсортировали их по возрастанию этого параметра. Поочередно добавляем отсортированные точки как новые вертексы МВО. Единственный нюанс - контроль внутренних (находящихся внутри контура) точек если таковые имеются. Тогда надо контролировать разницу углов между старым и новым направлением участка МВО.
Alex.gomel вне форума  
 
Непрочитано 10.07.2020, 21:07
#15
DEM

YngIngKllr
 
Регистрация: 29.03.2005
СПб
Сообщений: 12,968


Цитата:
Сообщение от myranda Посмотреть сообщение
К сожалению я не нашел как тут прикрепить файл
Зайдите в расширенный режим...
__________________
Работаю за еду.
Working for food.
Für Essen arbeiten.
العمل من أجل الغذاء
Працую за їжу.
DEM вне форума  
 
Непрочитано 10.07.2020, 22:24
#16
veb86

Проектировщик электрических сетей
 
Регистрация: 17.01.2014
Пенза
Сообщений: 176


Цитата:
Сообщение от myranda Посмотреть сообщение
ну, например, одна сторона дороги имеет какой-нибудь сложный контур (карман, например), а вторая просто прямая. Когда человек окажется на стороне сложного контура, то скорее всего, он сначала обойдет его (в несколько точек), а только потом вернется на первую сторону (таким образом зигзаг будет нарушен). Но допустим даже, зная все нюансы, я может и мог бы ходить удобным образом для алгоритма. Но иногда мне приходится чертить то, что обходили другие люди.
Это все гадание на кофейней гуще, Вы сначала покажите то что Вы хотите скормить алгоритму и что получить от алгоритма. Потому что, если это тупо облако точек с номерами, то эту задачу скорее всего не решить. Заходите в расширенный режим и добавляете файл...
veb86 вне форума  
 
Автор темы   Непрочитано 11.07.2020, 09:45
#17
myranda


 
Регистрация: 04.07.2020
Сообщений: 26


example.dwg
myranda вне форума  
 
Автор темы   Непрочитано 11.07.2020, 09:47
#18
myranda


 
Регистрация: 04.07.2020
Сообщений: 26


Нажмите на изображение для увеличения
Название: Безымянный.jpg
Просмотров: 45
Размер:	185.4 Кб
ID:	228223

----- добавлено через ~7 мин. -----
Цитата:
Сообщение от veb86 Посмотреть сообщение
Потому что, если это тупо облако точек с номерами, то эту задачу скорее всего не решить.
в принципе в общих чертах задача уже решена. осталось только написать прожку. решена следующим образом:
Берем ограничивающий прямоугольник, такой, что все точки дороги находятся внутри него, а некоторые будут лежать на его гранях. Берем одну такую точку (лежащую на какой-либо из четырех граней) и через нее и середину смежной грани проводим отрезок. Таким образом мы перешли от ограничивающего прямоугольника к пятиугольнику. Некоторые точки могут повылезать за его границы. В таком случае берем одну из вылезших точек (с самой маленькой координатой y, например, и через нее и бывшую "середину смежной грани" проводим отрезок. Часть точек залезут обратно внутрь новообразованной фигуры. И, в общем, подобными действиями через некоторое количество итераций фигура сформируется таким образом, что будет повторять контур дороги и, если в ней (дороге) нет никаких замкнутых областей - "недорожных островков", то задача решена.
Чтобы понять, что точка лежит снаружи фигуры можно воспользоваться википедией:
https://en.wikipedia.org/wiki/Point_in_polygon

Последний раз редактировалось myranda, 11.07.2020 в 09:56.
myranda вне форума  
 
Непрочитано 11.07.2020, 10:13
#19
CalcProg


 
Регистрация: 02.10.2016
Сообщений: 205


если алгоритм действий понятен, тогда в чём суть вопроса?

----- добавлено через ~4 мин. -----
лично я бы решил эту задачу одним из методов триангуляции. ;-)
CalcProg вне форума  
 
Автор темы   Непрочитано 11.07.2020, 10:19
#20
myranda


 
Регистрация: 04.07.2020
Сообщений: 26


Цитата:
Сообщение от CalcProg Посмотреть сообщение
если алгоритм действий понятен, тогда в чём суть вопроса?
уже ни в чем. просто привел решение для завершенности темы

----- добавлено через ~1 мин. -----
Цитата:
Сообщение от CalcProg Посмотреть сообщение
лично я бы решил эту задачу одним из методов триангуляции
триангуляция - это построение треугольников?
myranda вне форума  
Ответ
Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Алгоритм "построителя дорог"

Размещение рекламы
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Какой язык перспективен для инженера-конструктора с условием 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