Михаил Ч.Сделал вычесление "на лету" через UDF
При изменение значений в B2 и C2 маршрут сразу перерисовывается
Михаил, спасибо. теперь дело "за малым"...
За комментарии отдельная благодарность.

Заметил один из маршрутов прокладывается сначала по отрезку в одну стороны (влево) потом на на перекрестке разворачивается на 180° и дальше идет к точке назначения.
теперь не могу вспомнить между какими точками.

exp98Bobgos, дополняем друг друга по-немногу. Забудьте пока про сложности с уравнениями, это фигня, считайте, что они у вас есть и именно в том виде, как я написал. Сегодня пришла мысь. Предыдущую мою простыню положим в архив, а пока вырисовывается вариант попроще.
поэтому и благодарен вам за помощь - оптимальные решения в большинстве случаев принимаются коллегиально
exp98По сути у нас есть граф, у которого вершины состоят из прямоугольников, надо только этот граф формально построить, т.е. найти последовательность, в которой их соединять. Наши исходные упрощения сильно облегчают построение. Перекрёстков вида "Ж" у нас нет сейчас, есть только Т, Г, |, Х и м.б. "трезубец". Плюс к этому шарики, а там они типа Т. И у нас нет изолированных циклов.
перекрестков I и трезубец? мне кажется перекрестки по принятым ограничениям могут быть только Г, Т, X
Точки пунктов (шарики) - это просто точки прежде всего.
exp98Задача такая. Имеем прямоугольники, заданные своими координатами, и шарики, заданные координатами центров.ага - просто точки диапазона vertexexp98 Прямоугольники стыкуются без промежутков, т.е. у них общие боковые стороны. подозреваю, будут ошибкиexp98На самом деле прямоугольники могут быть и трапециями, у которых скос небольшой, тогда перекрёстки будут типа "(".
Для построения графа ищем соседние прям-ки методом "поиск в ширину". Канва алгоритма простая.

1) Кажем начальный прям-к. Сразу имеем 2 вершины графа на концах прям-ка и дугу между ними.
да, это на последнем моем формулами находил - концы зеленых линийexp98
2) Берём необработанную вершину и задаём направление от прям-ка, куда двигаться вдоль срединной оси прям-ка. Рекурсивной процедурой "поиском в ширину" ОБРАБАТЫВАЕМ все соседние с ним прям-ки. Сделать это можно примерно так.
2.1. Поскольку взятая в п.2) вершина лежит на стороне прям-ка, то у неё есть 2 соседние угловые точки этого прям-ка. Одна из них для ВЕРШИНЫ всегда левая, другая - правая. Нумеруем их слева направо.
надеюсь, что правильно понял, что "левая" и "правая" - относительно направления в котором отрезок оси заканчивается,т.е. точки короткой стороны прямоугольников коридоров. тогда можно просто определить короткие стороны прямоугольников коридоров и найти координаты центраexp982.2. Находим все прям-ки, соседние с обрабатываемой стороной. Для этого В цикле для каждой из этих 3-х точек "заметаем" геометрическое пространство в поисках ближайшей стороны соседних прям-ков.

нужно задать ограничение для "заметания" - не более погрешности снятия данных чертежа. например, 1/2 ширины коридора.
Что значит "заметаем"?
exp98 2.3. Устраняем дублирование в найденном наборе. В результате получаем новые дуги и вершины. Заносим их в граф.
сначала нужно определить как заметать и потом думать какая вершина будет основной,а какая дублем. подумать о том, как построить новые дуги - что будет связующим элементом.exp982.4. Если прям-к на краю чертежа, то одна вершина графа тупиковая, т.е. "лист". У неё нет других дочерних вершин и нам туда не надо. Этой дуге назначаем бесконечный вес.если есть вершина, то она может быть связана с любым из перекрестков или пунктов, а через одну дугу как минимум с дочерней (или наоборот с parent). Задача подразумевает развитие,поэтому без необходимости границы чертежа предлагаю не использовать. Прямоугольник может быть не на краю чертежа, но тем не менее быть тупиком.
Пока не представляю как это реализовать в коде. Может предложите на базе файла Graph4SQL2? exp982.5. Ну, значительно проще найти соседствующие шарики.просто,это если перебором дуги строго по горизонтали/вертикали и в условиях координат с шестизначными числами (и если не округлять с кучей знаков после запятой) подозреваю будет тормоза. Поясните как exp983) Для каждого изолированного цикла алгоритм придётся повторить.

Напоминаю, что это всего лишь канва алгоритма. Предлагаю её начать детализировать. Потом стыкуем с программой МихЧ.
Кстати, МихЧ писал про соединения встык, у меня это "трезубец", а в случае "|" ширина прям-ков может разниться.

правильно понял трезубец - на картинке?
exp98Полагаю, что новый алгоритм построения графа лучше тем, что работаем с нестрогими прям-ками, и что в предыдущем надо находить точки пересечения прямых, и иногда склеивать несколько точек в одну вершину графа. В новом варианте склеек может не понадобиться, т.к. вершины графа мы фактически имеем с самого начала. Но это ИМХО. И мне всё же ещё работать надо. Обещанный скан смогу только послезавтра.
а "2.3. Устраняем дублирование в найденном наборе." ЭТО разве не склеивание нескольких точек в одну вершину?
Ребята, жду выходных. у самого отчетные - не до...

exp98Потом стыкуем с программой МихЧ.
Предлагаю на базе программы МихЧ. тестовый модуль сделать для кода и предложить:
а) "Рекурсивной процедурой "поиском в ширину" ОБРАБАТЫВАЕМ все соседние с ним прям-ки"
я к сожалению совсем не программер, поэтому путаюсь в терминах, а уж код получается кривой и уж очень сложный (видимо заметили) .
Б) Рассмотреть другой подход к формированию исходных данных - коридоров.
Точки вершин понятно - выбрал из списка, ткнул в чертеж и подписал, или заполнил прочие доп. свойства inputbox или формой.
Коридоры в dwg проще обрисовать, но теоретически можно вставлять ромбы (квадраты, повернутые на 22,5° ) в местах поворота в каждом перекрестке, что позволит проложить через один перекресток 4-ре несоосные ломанные, т.е графически отобразить одновременно 4-ре маршрута одного вида.
в случае с ромбами сложнее будет с пониманием в каких местах будут повороты. Будут пропуски и соответственно неверные трассы.
коридоры обводить надежнее. Можно минимизировать ошибки при вводе, проверяя, существует ли вводимая координата одной из точек коридора и обязательно соблюдая сопряжение областей. т.е. разрешить (точнее заставить пользователя подтвердить) запись координат только первой снимаемой области и задать ограничения - чтобы коридоры вносились при первом съеме координат последовательно сопряженные.

Михаил Ч.,

как твое мнение по поводу ромбов предыдущего поста?
придется включать синусы/косинусы

Может подумать об упрощении исходной задачи - поочередной прорисовке одной трассы. Конечно цель была другая....

HandKotBobgos, ответьте на такие вопросы:
1. вот эти прямоугольники, как я понял стены, они каких размеров бывают?
2. на какое расстояние по вертикали и горизонтали они могут быть перемещены при редактировании?

или программа, в которой Вы рисуете план, это вида обычного PAINTа?
1. прямоугольники которые помещения могут быть самых разных размеров Например: 2000х2000 или 20000х18000
Коридоры по длине неограничиваются. Ширина 800,1000, 1200, 1500, 1800, 3000, 3500, и так далее до 6000мм, а может и больше. ОБласти (теже коридоры внутри помещеений совсем разнообразны, но обычно не более 3000мм.

2. на любое. Задача - универсальный инструмент. взяли dwg прорисовали запуская из excel прямоугольники - коридоры, снимая координаты, указали точки - источники/назначения и рисуем что хотим excel. А рисуем мы трассы - полилини

3. программа: нанокад. тоже можно делать в автокад

exp98Bobgos,
поскольку вычисление пути Вам подогнали, обещанный мною скан не потребуется.
За мной оставалось расстояние от точки до отрезка, где отрезки - это наши срединные линии.
У нас отрезок задан координатами концов Z1= (x1, y1) и Z2= (x2, y2).

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

Удобно задать прямую в векторном параметрическом виде:
Z= Z1 + R*t,
где t - числовой параметр, действительное число, его вычислим и получим место, где на прямой находится ближайшая точка.
Z= (x, y) - вычисляемые координаты прямой
Z1= (x1, y1) - координаты известной точки на прямой, в нашем случае= один из концов отрезка.
R= (rx, ry)= (x2-x1, y2-y1) - направляющий вектор прямой, в нашем случае направление ко второму концу отрезка.

В реализации могут быть варианты. Для примера:

Private TYPE COORDIN
x as LONG
y as LONG
END TYPE
DIM Z as COORDIN, Z1 as COORDIN, Zт as COORDIN, R as COORDIN
.................
call myDystance( .............)
.................

SUB myDystance(Zт as COORDIN, Z1 as COORDIN, R as COORDIN, d as LONG, Z0 as COORDIN, flag as INTEGER) -

Входные значения:
Zт=(Хт,Ут) - координаты точки
Z1 и R - коэффициенты уравнения прямой.

Возвращает:
d= расстоянию
Z0 - координаты ближайшей точки на отрезке, которая, если требуется, становится новой вершиной графа,
либо специальный flag, что ею является одна из вершин отрезка, тогда новых вершин графа не возникает.

Координаты ближайшей точки Z на прямой:

Z= Z1 + R*t - сюда подставить значение t и округлить до целого.
для к-ты Х, tx= (Хт - x1) / (rx + ry )
для к-ты Y, ty= (Yт - y1) / (ry - rx )

Расстояние до прямой:

Dim dx as double, dy as double, d2 as double
dx= - ry * tx
dy= rx * ty
d2= sqr( dx*dx + dy*dy) и округлить до целого.
d= d2

End Sub
За опечатки извините.
вот это дело. математика 7 класс давно забыта, а тут... надо пробовать тогда будут возникать вопросы.
жду выходных, ибо спать элементарно не успеваю.

HandKotexp98HandKot,
на мой взгляд, прям-ки - это коридоры, их внутренность. А программа скорее всего автокад либо нанокад, ибо формат DWG.

мне показалось по другому.
Просто донесу свою версию построения графа:
Пусть ширина коридора не может быть меньше и кратна "условной единицы".
Пусть ширина и толщина стен не может быть меньше и кратна "условной единицы".
Пусть размер помещения NxM условных единиц

Тогда создаем граф для помещения с количеством вершин NxM и размером вершины 1x1 "условная единица". У каждой вершины получается от 2 (по углам) до 4 (ни у края, ни в углах) связанных вершин.
После этого берем стену (прямоугольник) и выкидываем из графа те вершины, которые попали внутрь этого прямоугольника и так для всех стен.
В результате мы получим граф коридоров.
Поиск маршрута в нем уже дело техники.

да нужно задуматься об ограничениях.
1. Пусть ширина коридора не может быть меньше и кратна "условной единицы".
верна первая часть не может быть меньше 500
кратна - нет. т.к. прорисовывается по чертежу, который не проверяется на кратность. если конечно округлить, то можно принять толщину стены - 250 как шаг (точнее лучше 100 если учитывать сэндвич), после которого следующая проверяемая точка уже пересечет границы коридора -прямоугольника.
2. "Пусть ширина и толщина стен не может быть меньше и кратна "условной единицы". "
ширина -нет. возможны уступы для Z с любым расстоянием сдвига. Но проверить можно ширина и толщина не менее 100мм.
Значения можно внести в константы или заложить в конфигурируемые параметры модели
3. Пусть размер помещения NxM условных единиц
помещения - любого размера. Можно при съеме координат накладывать на общую сетку, т.е. применять те самые условные единицы. это несложно.

Зачем нам помещения? заново чертить все помещения не требуется, более того трасса может пролегать внутри помещения по виртуальным коридорам, которые прочерчиваются (при съёме модели чертежа в эксель) между оборудованием..
мы не говорим о модели всего чертежа. Размеры файлов могут достигать 100Мб, сложно будет. В слоях вечный беспорядок..... ИМХО проще всего обрисовать прямоугольниками коридоры для прокладки маршрутов.
Если сложно построить граф по прямоугольникам, лучше прочертить сразу граф осевых линий и определить пересечения этих линий. но это не даст возможность прочерчивать несколько трасс вдоль осевых линий без риска начертить трассы по стене или вообще по помещению за стеной. Например: коридор 800, по нему проходит 4 трасс, которые для восприятия должны иметь толщину не менее 150-200, т.е если будет минимальный отступ, 50, то как миним одна из трасс выйдет за пределы коридора.
Но пока чертим по осевым....

exp98Кажется теперь правильно. У себя проверил, а как перенёс сюда?..

1) Z0= Z1 + R*t - в векторной форме, сюда подставить значение t и округлить до целого, к-ты ближней т. на прямой.
Z0 = (X0, Y0)
t= ( rx * (Xt - X1) + ry * (Yt-Y1) ) / ( rx^2 + ry^2 )

2) Расстояние до прямой:

Dim dx as double, dy as double, d2 as double
dx= Xt - X0
dy= Yt - Y0
d= sqr( dx^2 + dy^2 )

Путает немного. Можно файлик с этим примером.
Применяемые обозначения верно поняты:
Z= (x, y) - вычисляемые координаты прямой. Z(x,y) - это точка лежащая на прямой которая проверяется ?
Zт=(Хт,Ут) - координаты точки, т.е тоже самое: Z(x,y) - это точка лежащая на прямой которая проверяется ?
Z0 - координата искомой точки (или проверяемой в текущий момент), , т.е тоже самое: Z(x,y) - это точка лежащая на прямой которая проверяется ?
Z1= (x1, y1) - координаты известной точки на прямой, в нашем случае= один из концов отрезка. Это понятно
R - коэффициент 2 (k2)


R= (rx, ry)= (x2-x1, y2-y1) - направляющий вектор прямой, в нашем случае направление ко второму концу отрезка.
где x и y кратны "условной единице" толщины стены, например. НО мы точно не попадем именно в точку

получается:
Z0 = (X0, Y0) - я понял как то что искомая точка устанавливается в координаты x=0? y=0? но ведь нам нужно найти x и y!
t= ( rx * (Xt - X1) + ry * (Yt-Y1) ) / ( rx^2 + ry^2 )

t - это то самое "условное значение" приращения вектора?
что такое: rx Xt X1 ry Yt Y1
???

Сори за невосприятие. А можно код с комментариями переложить в файл который сформирует хотя бы в черновичке граф?