2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Построение дороги по точкам
Сообщение09.07.2020, 18:40 


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

-- 09.07.2020, 19:07 --

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

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение09.07.2020, 21:18 


12/03/17
686
Я - крутяк!))
Замечательная идея пришла в голову. Я назову этот способ "натяжкой".
Берем ограничивающий прямоугольник, такой, что все точки дороги находятся внутри него, а некоторые будут лежать на его гранях. Берем одну такую точку (лежащую на какой-либо из четырех граней) и через нее и середину смежной грани проводим отрезок. Таким образом мы перешли от ограничивающего прямоугольника к пятиугольнику. Некоторые точки могут повылезать за его границы. В таком случае берем одну из вылезших точек (с самой маленькой координатой $y$, например, и через нее и бывшую "середину смежной грани" проводим отрезок. Часть точек залезут обратно внутрь новообразованной фигуры. И, в общем, подобными действиями через некоторое количество итераций фигура сформируется таким образом, что будет повторять контур дороги и, если в ней (дороге) нет никаких замкнутых областей - "недорожных островков", то задача решена.

-- 09.07.2020, 22:03 --

Прошу прощения. Тут еще один вопрос назрел. А как понять, что точка лежит снаружи фигуры? Мне известен один метод, но он очень муторный для большого числа граней. Есть ли простые способы?

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение10.07.2020, 18:34 


12/03/17
686
granit201z в сообщении #1473111 писал(а):
А как понять, что точка лежит снаружи фигуры?

уважаемые форумчане, вопрос по прежнему актуален. то что я поначалу принял за
granit201z в сообщении #1473111 писал(а):
Мне известен один метод

ошибочно. Этот метод не будет работать. Подскажите, если не затруднит

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение10.07.2020, 19:52 


21/05/16
4292
Аделаида
Поддерживаю вопрос о алгоритме проверки, лежит ли точка внутри фигуры. Для двумерных фигур этот вопрос имеет прямое отношение к моей теме topic140231.html.

-- 11 июл 2020, 02:24 --

Последние два мои сообщения оттуда немного намечают алгоритм, кстати.

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение10.07.2020, 20:45 


12/03/17
686
kotenok gav в сообщении #1473224 писал(а):
Поддерживаю вопрос о алгоритме проверки, лежит ли точка внутри фигуры.

вот что-то замаячило в голове. но это довольно муторно. Пусть нам нужно проверить точку B.
любую фигуру (ограниченную ломаными) можно разбить на треугольники.
а дальше в цикле бежим по этим треугольникам:
найти произвольную точку A (например, центр масс этого треугольника), лежащую внутри такого треугольника.
а дальше проверить, лежат ли эта эта точка A и точка B по одну сторону прямой, которая образовывает первую сторону треугольника (в справочнике Выгодского описано как это сделать). Если да, то проверить вторую прямую (образовывающую вторую сторону треугольника), и если да, то проверить наконец третью прямую. Если выясним, что точка будет лежать внутри одного из треугольников (т.е. по одну сторону с точкой A от всех трех прямых, образующих этот треугольник), то соответственно она лежит внутри фигуры , если же она не лежит внутри ни одного треугольника, то она вне фигуры.

Правда, сколько при этом придется сделать вычислений я затрудняюсь себе даже представить

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение10.07.2020, 21:35 


14/01/11
2916
granit201z в сообщении #1473111 писал(а):
А как понять, что точка лежит снаружи фигуры?

Эм, а методы из вики чем не устраивают?
https://en.wikipedia.org/wiki/Point_in_polygon

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение10.07.2020, 22:02 


21/05/16
4292
Аделаида
Sender в сообщении #1473248 писал(а):
Эм, а методы из вики чем не устраивают?
https://en.wikipedia.org/wiki/Point_in_polygon

О, значит, я в соседней теме изобрел велосипед 1962 года :D

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение10.07.2020, 23:02 


14/01/11
2916
Там, правда, могут быть нюансы, если граница частично совпадает с лучом, надо аккуратно рассмотреть все случаи, с какой стороны она приходит и куда уходит.

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение10.07.2020, 23:32 
Аватара пользователя


11/12/16
13195
уездный город Н
С точки зрения банальной эрудиции.

Имеем задачу восстановления многоугольника по его вершинам.
В этой задаче есть ровно два случая:
1. Многоугольник выпуклый. Задача довольно таки тривиальна.
2. Многоугольник не выпуклый. Задача не имеет однозначного решения, и нужно применять какие-то дополнительные знания о многоугольнике.

Насколько представляю себе дорогу, она либо прямая, и тогда описывается сильно вытянутым прямоугольником или трапецией; либо имеются повороты, и тогда она описывается фигурой, какая-то из сторон (или две стороны) которой будет вогнутой.
Возможные изменения ширины дороги пока оставим за скобками.

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение11.07.2020, 01:42 


12/03/17
686
Sender в сообщении #1473248 писал(а):
Эм, а методы из вики чем не устраивают?

спасибо. все оказалось так просто))

 Профиль  
                  
 
 Re: Построение дороги по точкам
Сообщение11.07.2020, 09:19 


12/03/17
686
Sender в сообщении #1473256 писал(а):
Там, правда, могут быть нюансы, если граница частично совпадает с лучом, надо аккуратно рассмотреть все случаи, с какой стороны она приходит и куда уходит.

ну, это легко проверить и, если совпадает, выбрать другое направление луча. Ошибиться с направлением больше раз, чем сторон в многоугольнике будет сложно))

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group