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

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

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

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

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

-- 09.07.2020, 19:07 --

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


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


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

Последний раз редактировалось 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
Сообщений: 205


у каждой точки находим её 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
СПб
Сообщений: 12,968


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

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

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


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


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

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

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

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

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


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

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


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


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


Как успехи? Какой алгоритм применил для решения задачи?
CalcProg вне форума  
Ответ
Вернуться   Форум 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