Bobgos, вечер добрый! Поверьте, не это Вам сейчас важно. Важно понимать схему работы Варианта 3, коль скоро будет использоваться он. Вы действительно полагаете, что по программе разберётесь, не поняв алгоритма? Или Вы тот самый Том Сойер, которому надо было покрасить забор? Мне код сидеть писать 3-5 суток предлагаете?

Скажу сейчас только 2 вещи:
1) Сабрутина всё же требует доводки, в т.ч. и по причине того, как именно она будет встраиваться в схему.
2)
Bobgosк чему приклеить сие... к перебору каждого направления от точки Z2?
Ваш рис. почти не о том.
Забудьте о направлениях. Мы строим граф не последовательно в каком-то направлении, а путём перебора всех отрезков и шариков по принципам "близости" и "перебора в ширину". Это основывется на сделанных допущениях о природе прям-ков.

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

2. Вне графа останется множество свободных срединных линий, т.к. они "далеко" от вершин, которые уже в графе. Поэтому скорее всего они будут присоединены к внутренности отрезка, создавая новую вершину графа, а не к имеющейся вершине графа. В этом месте использ. сабрутину.
Zt - здесь ВСЕ концы НЕприсоединённых срединных отрезков.
Z1 и Z2 - концы всех присоединённых срединных отрезков.
Эти множества точек НЕ пересекаются.
Как распалагаются взаимно [Z1, Z2] и Zt заранее неизвестно.

3. Предполагается, что в 1-2 в граф втянули все срединные отрезки. Осталось присоединить шарики. В этом месте также использ. сабрутину. Но!
Zt - здесь ВСЕ НЕприсоединённые шарики.
[Z1 , Z2] - все дуги графа, они же и срединные отрезки.
Мы немного предполагаем как распалагаются взаимно [Z1, Z2] и Zt.
("серые" отрезки на моём рис. НУЖНО не использовать, п.3 можно модифицировать, но об этом позднее, после понимания алгоритма).

Да, и постарайтесь не смешивать понятия "дуга графа" и "срединный отрезок". После присоединения к графу срединный отрезок становится дугой. Однако от шарика до ближ. срединного отрезка строим новую дугу и новй отрезок, но он уже НЕ срединный, если там не было прям-ка.

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

Bobgos, начать рисовать блок-схемы будет хорошим советом. Не держите всё в голове.

О, идея! Давайте начнём с конца, с 3-го прохода алгоритма.
Исходные:
У нас построен граф по всем прям-кам. Этот граф оказался связным. А шарики ещё не присоединены.
Ваша блок-схема алгоритма?

Bobgos
Давно собирался спросить. Было бы хорошо, если прям-ки можно было нарисовать почти до центра шарика. Иначе придётся существенно использовать 2-ю точку, указывающую направление от шарика к коридору, о которой Вы говорили в одном из первых сообщений (см. замечание в конце).

Гы)) теперь я недопонял:
авторминимального расстояния до ближайшего отрезка оси коридора
Но это неважно, предлагаю свой вариант.

Допущение (б) я вообще не использую. П.п. с 1. по 4. предлагаю превратить в следующее.

Посмотрим на единственный пример плана. На нём видно, что большинство шариков расположены удачно.
а) А именно сидят с боку и близко от нужного ПРЯМ-КА. В этом случае вместе с шариком появится дополнительная вершина графа, лежащая на осевом отрезке, а дуга раздробится на 2-е.
б) Ещё есть шарик, который сидит близко от торца нужного ПРЯМ-КА. В этом случае новой вершиной графа будет только шарик.
Т.к. шарики КАСАЮТСЯ нужной стороны нужного КОРИДОРА, то на этом плане ближайшей стороной будет сторона именно нужного ПРЯМ-КА. И если забыть про замечание в конце, то ближайшим осевым отрезком будет именно нужный.


Есть принципиальные возражения, поправки?

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

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

Более свежая рыба, более приблИженная к последним пунктам 1,2,3,4. Чего в ней не хватает для полноты?
Предыдущая теперь не первой свежести, можнобы и удалить.

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

В конце поместил группу функций для красивой работы с координатами точек - код теперь компактней.
Предыдущий файл можно выкинуть.

А здесь координаты: концы отрезков и шарики.
Рядом текст выражения, чтобы копи/вставка прямо в эксэл ... и можно проверять.

вложение здесь

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

Исходные отрезки и шарики на листе Лист1. Для него служебный лист Т. Диапазон координат задан в константах макроса. Результат графа см. на листе граф.

Поскольку 1-й и 2-й проходы не имитировал, то и начальный граф был пустой, так что не удивляйтесь, что почти все вершины изолированы дргу от друга. И тут как раз наглядно видно, что в ходе вычислений ДУГА может дробиться и исчезать, при этом ОТРЕЗОК в массиве каким был, таким и остался. Зато появились новые точки, ставшие вершинами графа.

Я обвёл рамкой 3 области, идущие подряд:
- концы отрезков
- шарики
- вычисляемые точки присоединения шариков, если они новые.
И да, значения в графе сейчас = расст. между точками либо 0, если точки не связаны. а для стыковки с нахождением пути, потребуется в дальнейшем заменять 0 на бескон-сть, но контекстная замена заменит также и правильные 0 - это надо в макросе менять.

Ну вот, есть материал для развития. Взамен поделитесь, какими макросами экспортировать данные из dwg? Изучать неохота.

Ну просто не знаю, с первого раза файл не крепится, уже не первый раз.

Shocker.Pro, да-да, так и показалось, что просмотр сбивает. Или наверно можно без просмотра.


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

Я приложил картинку графа по исходным данным, нарисовано автоматом, не мною. Здесь только топология, без расстояний.
Читать её надо так.
Номера вершин 1 - 42 - это концы отрезков
43 - 71 - шарики
72 - ... - новые точки, присоединения шариков, стыковки отрезков и т.д. У них могут быть нулевые расстояния, но на рисункеэто конечно не отображено.

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

Ох, и надоело же простыни писать(
Рисовал в PHP, т.к. нанокад мне осенью активационный код вовремя не дал, и я от них отказался. Просто я хелп эксэла не ставил, а методом тыка графику не нащупал, в инет за справкой - только время терять было. Теоретически могу по фтп сразу заливать рисунок или данные вам куда-нить в папку на сайте. Сейчас в эксел формируется текст программы рисовалки на PHP, а можно и для автокада, если напишете её текст.

Об ошибках. Те, что вижу я , предвиделись, но я не ожидал, что они все вылезут ) Я писал, что не сделаны умные проверки, в основном это обработка "синапсов", 3-х проходов вместо 2-х и новые торцевые отрезки на терминальных вершинах. + настройка радиуса окрестности. В общем, макет программы получен.

В результате сейчас:
1) Ищется абсолютный минимум вместо нескольких ближайших. Но его обрабатываю с ошибкой. Это программистская ошибка. Её видно по Г-образным линиям у нижних шаров - ошибочное присоединенние к вертикальной осевой линии вместо конца отрезка. Остальное - это ошибки упрощёной методики.
2) Как раз на виртуальных коридорах сидит шар - перекрёсток типа Y не обработан. Здесь граф к шару пойдёт через стенку что ли? Нет запрета на то, что в этом месте 2 коридора НЕ ДОЛЖНЫ соединяться.
3) Длинные гориз-ные коридоры связаны справа - без объяснения. Скорее это связано с п.1)
4) Не могу понять, то ли я ошибся, то ли 2 коротких вертик-х коридора действительно не стыкуются с горизонтальными?
5) Сдвоенные линии - из-за целочисленных округлений. Кроме того я приравнял расстояния 10=0.
6) А вот , наверное ни из графа, ни из рисунка не видно, что если 2 шара присоединяются к одной линии, то в графе их связь в графе сейчас не создаётся. Это надо исправить.
7) Ну и пока не видно, как я уже писал, ошибочной связи шара с более узким коридором, нежели с более широким нужным. За это пока не брался.

Что я ещё не увидел? Белый цвет линий? это эффект сложения противоположных цветов : синий+жёлтый одинаковой интенсивности, расположенные рядом, дают впечатление белого.

Сейчас по сути 2 коротких подпрограммы всё делают, а будет штук 10. Сейчас 600 строк и половина комментов, потому так быстро и сделал. В итоге хочу сказать, что даже доводка до перечня 1-7 потребует полной занятости на неделю работы, не меньше. Даже только п.1) уже займёт время. Не обещаю даже, что возьмусь за устранение всех п.1-7. За хорошую плату бы сделал, потому что мой проект закрыли, а за полгода так и не плачено. И время самое удачное для поиска, может придётся переквалифицироваться в управдомы.

Всех с НГ!
Файл прилагаю.

Bobgos,
подарки от Снегурочки для проверок.
С п.1) покончено. Шлите ещё вариант для контроля.

Чтобы не было путаницы. Оба рисунка - графы (пусть и с ошибками пока). Один рис. - просто топология, другой - точки расположены в правильных координатах. Для проверки и отладки полезны оба. А переписывать заново - дело хозяйское.

По Вашим вопросам:
У меня нет "полурешений". Формулы плавно переросли в программу, а затем использовались только для проверок программы.

ВХодные данные как ссылка на формульный диапазон - ну это из-за лени. Кто мешает сделать рассчёт в программе? В ВЫходных данных формулы для прямоугольников - тож самое. А выплюнуть готовый скрипт в файл - мне это надо? С эттим как раз обезьяна справится. Дальше. Раздел Констант надо задавать через форму, а сами константы сделать глобальными переменными.

Кстати напомню: можете на любой угол повернуть координаты. В программе ничего не изменится, я надеюсь. Для проверки я сместил крайний правый шарик - там видно, что присоединяется он правильно. Можете вместо прям-ков взять трапеции или овалы и без плотной стыковки - только укажите осевые отрезки.

"Примеры создания и доступа" - как написано, так и есть - была целостная единица с правильной последовательностью команд. Сейчас возможно она уже неправильная) Есть такой приём. Когда не хочется обдумывать всё долго и заранее или трудно, или думаешь урывками, я начинаю писать комментарии типа блок-схемы. Затем комменты наполняю очевидными командами / процедурами и т.п. Затем порции команд как одна логическая единица копирую в разные места и т.д. - одновременно мне легко вносить изменения в такие порции. Так на скелет наращивается мясо. Оптимизация потом. Но начать с чего-то всегда придётся. За принцип: сделать заведомо простое, может тогда сложного и не останется, пожизненая благодарность препу. А.Комбарову. С Вашим случаем как раз так и получилось.

Точки поворотов. С ними как раз всё хорошо, лишняя дуга там отсеится сама Дейкстрой, это пока сейчас здесь ошибка (п. 6).

П.2): Найдите на Рис. Шарики 70, 52, 55 - вот эта ситуация из области распознавания сцен. Кто знает заранее, рядом там тупик или нужный коридор? Это надо заранее обозначить признаком или т.п., мы говорили о Лучах. Или запустить 2-й цикл программы.

Посмотрите на Шарик 51. Ещё немного и он притянется к нижнему коридору. А к какому правильно? Те же Лучи. Ну и 45-й так же может сработать и т.д.

Синапс - ну это для сложных ветвлений. А пока навеяло как обойтись уже сделанным. П. 6) я легко сделаю автоматической постобработкой, пол дня как-нить выделю.

Поскольку из Варианта 3 я объединил 1-й и 2-й прогоны и недореализовал их, то ввести постобработку, устраняющую недостатки, т.е. 4-й этап. Например ручками (кроме п.6) тыкается, что надо удалить или что исправить. Поскольку программа модульная, это легко сделать зациклив её на 2-й круг, но предварительно надо задать фильтры на вершины и дуги, а граф 2-й раз не инициировать. А для фильтров надо вместо моих циклов последовательного перебора по i,j: Otr(i) или PNTS(j) по точкам или отрезкам, вести перебор по фильтрам-спискам: Otr( ListO.next), PNTS( ListP.next) и т.д. Это действительно легко и просто.

А например, для простой правки как у Шарика 70, можно оставить в фильтре только его и прям-к 19 и напустить на них алгоритм ещё раз. Тогда граф пополнится ещё одной дугой. В общем такие простые костыли практически без программирования. А можно наделать костылей на разные случаи по мере их появления и т.п. В любом случае без постобработки в Вашей задаче не обойтись, и уж глазками всегда надо смотреть для проверки. Кстати, 5-й этап - автодиагностика нужна ВХодных и ВЫходных данных.

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

Насчёт РНР. РНР запускается из эксела командой SHELL(). А так всё легко переложить на нём, и ГУИ сделать в браузере, javascript позволяет. По крайней мере простейший интерактивный графический редактор графа с перетаскиванием мышью нужных обектов на их правильное место. Только это не очень быстро сделать, зато лицензионная чистота 100% и кроссплатформенно. Вместо РНР есть питон,перл и т.п. Вы можете эту обработку разместить на сервере, а в браузере получать результат на планшет, загорая на пляже. И т.д., главное вовремя заткнуть фонтан идей. А можно найти готовый редактор векторных объектов и редактировать там. А если в редакторе ещё и макросы можно ...

Вы сами видите, что даже мелких улучшений полно, и просто так тратиться на это желания нет. Основную идею я для себя проверил хотите пользуйтесь, не хотите - нет. Да я и без лички могу: alp98 (cat) ya. ru, надеюсь понятно.

ещё

рнр

Bobgos, ну что же, погодка блгаоприятствовала. Это вроде всё, что я обещал. Макрос во вложении. Получилось даже лучше и проще, чем ожидал. Граф далеко не оптимальный, но и неважно, это макет. Проверять можно, отключая запись на лист дуг для тех или иных вершин. Стыковку 2-х и более виртуальных коридоров с одним шаром можно обеспечить на 2-м (3-м ...) прогоне разными способами.
Например, отключив сравнение шара с уже подключённым отрезком => он соединится с другим прям-ком.
А можно открыть окно Imidiate, и непосредствено в нём выполнить команду вида GR(i,j)=1400 или какое там расстояние д.б.
Или создать чёрный список.

Теперь отмазка! Как в любой задаче распознавания возможны 2 типа ошибок: 1-го и 2-го рода, об этом я уже упоминал. Немножко регулировать можно отсевом по расстоянию, а если нет, то для каждого плана руками. Вместо бесконечности я заносил константу NOL=-1 - это к вопросу о стыковке с поиском пути.

php, а рисунок не изменился, вернее изменение не видно.