Построение дороги по точкам

[granit201z]

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

-- 09.07.2020, 19:07 --

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

[granit201z]

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

-- 09.07.2020, 22:03 --

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

[granit201z]

granit201z в сообщении #1473111 писал(а):

А как понять, что точка лежит снаружи фигуры?

уважаемые форумчане, вопрос по прежнему актуален. то что я поначалу принял за

granit201z в сообщении #1473111 писал(а):

Мне известен один метод

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

[kotenok gav]

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

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

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

[granit201z]

kotenok gav в сообщении #1473224 писал(а):

Поддерживаю вопрос о алгоритме проверки, лежит ли точка внутри фигуры.

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

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

[Sender]

granit201z в сообщении #1473111 писал(а):

А как понять, что точка лежит снаружи фигуры?

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

[kotenok gav]

Sender в сообщении #1473248 писал(а):

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

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

[Sender]

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

[EUgeneUS]

С точки зрения банальной эрудиции.

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

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

[granit201z]

Sender в сообщении #1473248 писал(а):

Эм, а методы из вики чем не устраивают?

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

[granit201z]

Sender в сообщении #1473256 писал(а):

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

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