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

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

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

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

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

-- 09.07.2020, 19:07 --

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


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


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
Пенза
Сообщений: 177


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


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


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

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

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


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

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

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


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

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


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
Московия*
Сообщений: 4,970


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
Московия*
Сообщений: 4,970


Цитата:
Сообщение от 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
Сообщений: 24


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
СПб
Сообщений: 13,006


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

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


Цитата:
Сообщение от 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
Просмотров: 42
Размер:	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
Сообщений: 192


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

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


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


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

----- добавлено через ~1 мин. -----
Цитата:
Сообщение от CalcProg Посмотреть сообщение
лично я бы решил эту задачу одним из методов триангуляции
триангуляция - это построение треугольников?
myranda вне форума  
 
Непрочитано 11.07.2020, 10:31
#21
CalcProg


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


да. например: "триангуляция делоне и её применение". а.в.скворцов.

Последний раз редактировалось CalcProg, 11.07.2020 в 10:38.
CalcProg вне форума  
 
Автор темы   Непрочитано 11.07.2020, 10:36
#22
myranda


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



ну да. любой многоугольник можно представить треугольниками. Но по какому критерию бы Вы вычислили какие ребра подлежат удалению?
myranda вне форума  
 
Непрочитано 11.07.2020, 10:48
#23
CalcProg


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


у каждой точки находим её 7 соеседних(по наименьшему расстоянию).
получаем семь отрезков. эту процедуру проделоваем со всеми точками. получаем массив отрезков. затем ищем пересекающиеся отрезки. те отрезки которые не имеют пересечения и будут контуром дороги.
CalcProg вне форума  
 
Автор темы   Непрочитано 11.07.2020, 12:03
#24
myranda


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


Цитата:
Сообщение от CalcProg Посмотреть сообщение
у каждой точки находим её 7 соеседних(по наименьшему расстоянию).
получаем семь отрезков. эту процедуру проделоваем со всеми точками. получаем массив отрезков. затем ищем пересекающиеся отрезки. те отрезки которые не имеют пересечения и будут контуром дороги.
Логично. Но может быть случай, например, когда по одной стороне дороги точки стоят с большими пробелами (скажем дорога прямая), а по другой довольно плотно (например, на этой стороне много карманов, выступов). Тогда отрезки дороги (по прореженной стороне) не войдут в наборы семерок, а следовательно выпадут из рассмотрения и не будут построены
myranda вне форума  
 
Непрочитано 11.07.2020, 15:43
1 | 1 #25
DEM

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


А не проще ли сетку(mesh) построить сперва.
А потом определить её контур.
После этого работать с получившимся контуром.
Сперва построив срединую линию для контура.

----- добавлено через ~4 мин. -----
Для построения mesh есть различные библиотеки.
Для получения контура можно использовать следующий алгоритм.
Сделать список граней треугольников, если грань встречается дважды то удалять её из набора.
Срединную линию тоже построить можно.

----- добавлено через ~11 мин. -----
Я бы для такого построителя использовал пайтон.
В принципе библиотек у него достаточно..
__________________
Работаю за еду.
Working for food.
Für Essen arbeiten.
العمل من أجل الغذاء
Працую за їжу.
DEM вне форума  
 
Непрочитано 11.07.2020, 16:00
#26
CalcProg


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


Цитата:
Сообщение от myranda Посмотреть сообщение
Логично. Но может быть случай, например, когда по одной стороне дороги точки стоят с большими пробелами (скажем дорога прямая), а по другой довольно плотно (например, на этой стороне много карманов, выступов). Тогда отрезки дороги (по прореженной стороне) не войдут в наборы семерок, а следовательно выпадут из рассмотрения и не будут построены
нет они не выпадут скорее всего получим изгиб дороги в сторону карманов.

----- добавлено через ~1 мин. -----
Цитата:
Сообщение от DEM Посмотреть сообщение
А не проще ли сетку(mesh) построить сперва.
А потом определить её контур.
После этого работать с получившимся контуром.
Сперва построив срединую линию для контура.

----- добавлено через ~4 мин. -----
Для построения mesh есть различные библиотеки.
Для получения контура можно использовать следующий алгоритм.
Сделать список граней треугольников, если грань встречается дважды то удалять её из набора.
Срединную линию тоже построить можно.

----- добавлено через ~11 мин. -----
Я бы для такого построителя использовал пайтон.
В принципе библиотек у него достаточно..
конечно так проще, но пионеры не ищут лёгких путей.
CalcProg вне форума  
 
Непрочитано 13.07.2020, 08:04
#27
veb86

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


Цитата:
Сообщение от CalcProg Посмотреть сообщение
да. например: "триангуляция делоне и её применение". а.в.скворцов.
При такой задаче, я бы тоже начал читать в сторону триангуляции, мне кажется она подойдет
veb86 на форуме  
 
Непрочитано 13.07.2020, 13:10
#28
DEM

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


А может лучше не читать а попробовать какую то готовую библиотеку.
__________________
Работаю за еду.
Working for food.
Für Essen arbeiten.
العمل من أجل الغذاء
Працую за їжу.
DEM вне форума  
 
Непрочитано 22.07.2020, 15:46
#29
CalcProg


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


Как успехи? Какой алгоритм применил для решения задачи?
CalcProg вне форума  
Ответ
Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Алгоритм "построителя дорог"

CAD БИБЛИОТЕКА
Размещение рекламы
Опции темы Поиск в этой теме
Поиск в этой теме:

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


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