Ну да, толщину стенки принимаем в пол кирпича))
Bobgos, прошу не смешивать алгоритмы. Разница принципиальная. Определитесь с вариантом и тогда уже уточняйте, может я больше не понадоблюсь. Я сужу по цитате:
R= (rx, ry)= (x2-x1, y2-y1) - направляющий вектор прямой, в нашем случае направление ко второму концу отрезка.
где x и y кратны "условной единице" толщины стены, например. НО мы точно не попадем именно в точку
Если это суждение основано на моём рисунке, то оно в корне не верно, т.к. я вычислил всё из исходных координат и только затем нарисовал, а чтобы уместить на листе, взял масштаб 1:500, стенки вообще руками закрасил для наглядности. Поэтому попадём именно "в точку". И для случая HandKot клетки - это только вершины графа, но каждая клетка имеет конкретные координаты на плане.
Итак, на сегодня имеем 2 алгоритма построения графа. Графы получатся совершенно разные. Общее у них то, что короткие пути по ним будут похожи.
HandKot 1) HandKot , усовершенствую немного - строим сетку на плане , сетка с некоторым шагом. Кратность шагу не требуется (например задаём параметром для каждого плана ~ 1/100). Координаты задаются для помещений , которые удобнее представлять как набор прямоугольников, + как-то надо задать пространство , чтобы шарики были связаны с коридорами, иначе граф не найдёт к ним пути. "Виртуальные коридоры" придётся дополнительно оцифровывть снаружи прям-ками.
Далее вычеркнуть все клеточки, которые полностью либо частично перекрываются с помещениями. Из оставшихся клеток сам собою остаётся связный граф с дугами длиной в 1 шаг. Легко программировать, если всё прямоугольное. Линии могут оказаться не прямыми, а ступеньчатыми, но это зависит уже от алгоритма построения пути, как он выбирает минимум. Это ИМХО.
Мой 2) Мой Вариант 3, на идее распознавания, а в нём всегда возможны артефакты. Здесь коорд-ты задаются для коридоров и необязательно покрывают всю коридорную площадь. Прогать сложнее. Поэтому требует визуальной проверки для возможной корректировки.
Теперь по сабрутине, здесь чуть больше, чем 7-й класс.
В принципе Вам достаточно ФОРМАЛЬНО подставить значения в фурмулы. Для примера сделайте это сперва на бумаге.
Ещё раз смотрите сюда.
Это уже имеем для процедуры:
---------------
У нас любой отрезок задан координатами концов
Z1= (x1, y1) и Z2= (x2, y2)
Zт=(Хт,Ут) - координаты точки, от которой измеряем расстояние до прямой, представленной отрезком. В Варианте 3 - эта точка либо центр шарика, либо конец срединного отрезка.
Это вычисляем в процедуре:
-------------------------------------------
Z0 = (X0, Y0) - ближайшее место на отрезке. Геометрически это точка пересечения 2-х перпендикулярных прямых. Либо ею будет один из концов отрезка, смотря что ближе. Узнать это мы сможем только после нахождения т. Z0 .
Далее вычисляем:
(rx, ry)= (x2-x1, y2-y1)
t= ( rx * (Xt - X1) + ry * (Yt-Y1) ) / ( rx^2 + ry^2 )
Подставляем значение t сюда:
X0= x1 + rx*t
Y0= y1 + rx*t
Далее вычисляем:
dx= Xt - X0
dy= Yt - Y0
d= sqr( dx^2 + dy^2 ) - искомое расстояние.
По т. Z0 проверяем, выходит ли она за отрезок (здесь код ......).
IF "выходит" THEN находим ближайший конец отрезка
IF "не выходит" THEN d - искомое расстояние.
END SUB
П.С. Выше почти код, буквы только убрать. Кто хотел бы, давно бы сюда выложил, а при такой писанине я отдыхаю, а не работаю.
