Bobgos, метод правой (или левой руки) прост: двигаемся в любую сторону, не отрывая руку от стенки, пока не выйдем. Можно зациклиться, если есть внутренний цикл. Тогда будем бесконечно крутиться вокруг, значит надо помечать пройденное место. Собсно, и весь алгоритм - в детстве ещё читал.
И выше уже писали: сначала построить граф, затем проверить на циклы в грАфе.
А нужно ли искать кратчайший?

Помимо указанных форматов есть открытый формат DOT, готовится в ноутпаде. Такой формат легко засасывается в ячейки эксел и при необходимости там и правится, и проверяется.

digraph имя {
//здесь навалом пишем все пары в любом порядке
a1 -> b1;
a1 -> b2;
a1 -> b3;
b2 -> c1;
f1 -> b3;
b2 -> c1;
b2 -> f1;
a1 -> d1;
a1 -> d1;
и т.д.
}
Если просто надо визуализировать для проверки, то можно использовать неприхотлтвый, но мощный открытый пакет GraphViz. В нём основные утилиты dot.exe - конвертер в каринки и dotty.exe - визуальный редактор графа.


Если же надо программно обработать граф, то изначально есть 2 канонических представления графа.
Вообще, граф == отображение {A} --> {A}x{A}, где {A}-множество вершин, которое отобрашается в их Декартово произведение. А по-русски: это вершины и рёбра вместе взятые.
Ой, чей-то много написал ...

Bobgos, на вопрос как построить граф?
А что за координаты на рисунке. Народ имел ввиду, что вы создёте массив центральных точек на всех перекрёстках - это вершины графа. Или вопрос как автоматизировать нахождение перекрёстков, когда есть вершины криволинейных прямоугольников-коридоров? В последнем случае, если руками указать все перекрёстки , то их центры взять как среднеарифм. координат.

Да, о представлениях графа. В языках давно есть готовые Tree-структуры.
Если с чистого листа, то: либо "матрица вершин" (почти вся пустая), либо "списки инцидентности", которые похожи на формат DOT. Но вот программировать удобнее на списках, тк. уже есть готовые методы: следующий, предыдущий, пусто и т.д.
Ну и две стратегии обхода всего графа: поиск "в ширину"/"в глубину" - всё равно всё пройденное запоминать надо.

И чтоб мысль закончить. Алгоритм эмпирического блуждания по графу - тогда не надо никаких поворотов/векторов/углов и проч. Просто полагаем, что ребро графа - это коридор. Ну или алгоритм поиска пути, приближённого к короткому.
При выборе способов ещё важно, насколько повторяемо будет это задание. Если один раз сделать, то можно и полувручную.

какой ещё вопрос остался?
Bobgosпроблема не перевести из dwg в xls координаты. Вопрос как построить граф?
считаем, что уже есть координаты областей по которым можно строить маршрут от точки А к точке Б.

как построить граф и проложить маршрут - определить координат точек ломаной линии?
Да еще и посчитать какой путь короче, для двух маршрутов найти точки пересечения?

Если я правильно понял: имеем криволинейные полоски на плоскости, которые могут пересекаться, да? По типу топографической карты, рекка и её притоки + каналы и т.д. Или дороги на местности. А как карты векторизуют, они ведь пиксельные?

Т.е. как превратить полоску в линию?
Доморощенный и неудобный вариант: решение системы линейных неравенств вида:
a1 *x +b1*y<=c1
a2 *x +b2*y>=c2,
решение - это прямоугольник, отрезок, точка либо пусто.

Два таких прямоугольника задают пересечение 2-х фрагментов "дорог".
Находим все изолированные (или даже частично пересекрывающиеся парные пересечения) - это и будут перекрёстки.
Для этого кластеризуем найденные пересечения.
Центры найденных кластеров можно принять за перекрёстки.
(Этот метод имеет погрешности)

Универсальный метод "по гребню хребта".
Каждый участок "дороги" сглаживаем окрестностным сглаживателем. В результате получаем вместо плоской дороги 3-хмерный вал (хребет на местности). Теоретически у хребта будет гребень (или узкое плато, идущее по вершине).
Затем ищем точки пересечения гребней, т.е. 1-мерных линий. Но и тут есть некоторые нюансы, т.к. строгого пересечения может не быть.
На qb я когда-то баловался, валяется черновик.

авторКак найти смежную вершину - точку в которой возможен поворот пути по коридорам областей
Например:
Если в достаточно маленькой окрестности точки на линии есть точки другой линии.

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

Bobgos,
добрый вечер,я случайно сюда щас гянул. Ваш вопрос мне вполне интересен теоретически, и чего смогу, то подскажу. Но ведь не я один такой "умный" в инете.

Выше уже просили показать побольше данных. Добавляю просьбу:
- примеры координат в ТЕКСТОВОМ виде,точек 100,например. И вообще, каков масштаб проблемы,т.е. порядок точек всего?
- рисунок характерных перекрёстков, пусть даже и сделанный в пайнтбраше. Возможно пропорции перекрёстков окажутся важны.

Задача ведь не элементарная. Когда будет понятно с алгоритмом, с кодом будет легче. Насколько я понимаю в технике программирования, то при обходах графов полезны рекурсивные вызовы функции со статическими переменными (либо их замена на глобально доступные переменные).

Насчёт алгоритмов у меня появилась идея, но применима ли она здесь - надо посмотреть распределение точек с координатами.
Из рисунка надо оценить сложность перекрёстков: "Ж"-обрАзные, Г-, Т-,Х-,"(", "|" и т.д ?

Из последнего сообщения мне показалось, что Вы думали о графе, который строится из "стенок" коридоров,да? Я уверен, что здесь предлагался как раз граф "коридоров" и перекрёстков. Хотя м.б. подойдёт идея соединить стенки коридоров в цепочку рёбер,тогда граф т.ск. уже построен.
Вопрос с функцией отрезков мне не очень понятен. Если есть уравнение 2-х прямых, то их т. пересечения вычисляется теоретически.

В частности, для примера, пока Вы вполне можете руками в экселе
сделать матрицу парных расстояний тех точек, которые определяют перекрёстки (как я понимаю - это углы коридоров). Лучше для статистики вообще любых точек, в т.ч. и на перекрёстках. Расстоянние самое Евклидовое sqrt( (x1-x2)^2 + (y1-y2)^2 ), впрочем можно обойтись без корня,т.к. нам важно их только сравнить.

Затем вытягиваете матрицу в один столбец.

Затем все смотрим ТОЧЕЧНУЮ диаграмму по этому столбцу. Есть подозрение, что даже визуально точки будут распадаться на кластеры.

Дальнейшие выводы возможны после визуализации, но идея такая.
Кластеры с минимальными значениями соответствуют перекрёсткам, но при этом ВСЕМ перекрёсткам.

Чтобы отделить один от другого нужно с каждым парным расстоянием ассоциировать конкретные координаты этих точек. Т.о. точки получают признак "перекрёсток".

Затем умно "кластеризуем" сами точки.
Умозрительно говоря, два этих множества должны пересекаться как раз в местах перекрёстков.

Это всё можно сделать формулами при помощи рук. Это всё делается только для того, чтобы нащупать канву алгоритма, а без характерных данных я дальше не фантазирую. Ну, есть ещё способ: превратить всё в растр и напустить векторизатор в автоматизированом режиме, а потом вытащить координаты и программировать.