exp98,
да, план характерный... только нужен универсальный инструмент для любой сложности коридоров.

во вложении шаблон для записи точек коридоров. В dwg предлагаю не углубляться - за исходные берем лист sprAreas (формат представления данных о коридорах.

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

повторяем г)-е) для других точек источник2- назначение2
ж) находим пересечения
з) прорисовываем маршрут, выделяем пересечения

exp98,

ок выложу файлик описанными областями на одном из примеров.
к сожалению nanocad3.7 как-то странно реагирует на VBA обращения к слоям. А ноут мой похоронен до получения премиальных. Придется найти способ снять данные о точках.

но сразу говорю.
Размерность задачи - областей коридоров порядка 50 шт. Максимум - не ограничивается - но думаю обрисовывать более 3-4 сотен коридоров не потребуется в принципе.
Типов маршрутов - маршрутов различных цветов для различных видов материальных потоков - в пределах десятка (это 1. сырье нерастаренное, 2-3 полуфабрикаты 2-х или трех степеней готовности, 4. тара, 5. ТБО, 6. органические отходы, 7. упаковочные материалы)
Для основного типа маршрутов - движение полуфабрикатов (для одновременного отображения) - порядка до 15 линий + еще до 7ми трасс для других видов трасс.

т.е одновременное отображение для 15 +7 трасс, проходящих по не более 200 областям между ориентировочно 100 начальными/конечными точками.

Такой комментарий достаточен для выработки предложения по построению алгоритма?

поправлю немного:
Bobgosт.е одновременное отображение для
(15+7)* N трасс, проходящих по не более 200 областям между ориентировочно 100 начальными/конечными точками.
где N - это число этапов от 2-х до 10 (максимум) - число точек начала/окончания для выбранного маршрута
это задача максимум.

Задача минимум - одновременное построение (1+0)*N трасс, т.е. маршрут продукта от одного рабочего центра к другому.
но хранение данных о уже прорисованных маршрутах как активных и проверки на пересечение с некоторыми неосновными категориями маршрутов.

Такой комментарий достаточен для выработки предложения по построению алгоритма?

exp98Ха! вопрос усложняется.
Вы полагаете, что самое сложное - это решить задачу транспортного типа, а я думаю, что сложнее полностью автоматическое построение графа по любому подобному плану. И я как раз прежде всего рассматривал этот аспект задачи, а Ваше мнение? В противном случае руками создаём учебный граф, рёбрам присваиваем вес=длина пути и начинаем формулировать частные виды задач. Выбор за Вами. Боюсь, что "кружочки" придётся оцифровывать вручную.
Вручную необходимо будет формировать список точек источников-приемников. Координаты их планировал вносить из Excel с помощью отдельной команды:



exp98А пока можно ведь снять координаты с приведённого плана в пэйнтбраше. И сосредоточимся на одном "типе маршрута", на самом важном.
согласен, что сконцентрироваться на одном
exp98В любом случае, хорошо бы определиться с терминологией. Был приведён рисунок фрагмент плана. Что на нём есть что?
1. "Один коридор" - это что? Я думал, что границы коридоров начерчены чёрными линиями, а что тогда такое ступенчатое в середине? там границы коричневые. А по периметру малиновая линия.
-периметр - общая область чертежа для поиска пути. Если не потребуется - то и ладненько...exp982. Что такое "область коридора"? это равно "область"?
да разрешенная для поиска пути область - коридор. "Очерчен черной линией, но с заделом для "красивости" прорисовки при снятии размеров - обведения коридоров предполагал, что область будет например на 100 мм уже, чем сам коридор.
exp983. Что на рисунке "трасса"?
это ломаннная линия по центру коридоров exp984. Что означает цвет линии? это тип маршрута или трассыexp985. Что такое "маршрут"? что такое "этап"? это ломанная линия по центру коридора или трассаexp986. Если "начальными/конечными точками"=100, а "областей"=200, то граф предполагается какой? 100 вершин и 200 рёбер?
100 начальных конечных точек - это именно точки. Да, они в том числе должны будут добавляться к графу.
Вершины графа: а) точки начальные/конечные, точки вхождения в маршрут и б) точки поворотов коридоров. Ребра графа а) отрезки между поворотами б) отрезки между например исходной точкой маршрута и ближайшим расстоянием до отрезка -оси коридора exp987. Маршруты (на графе), которые мы предполагаем строить могут не позволять строиться другим маршрутам? давайте сначала нужно нарисовать один маршрут exp988. "Рабочий центр" является одной из вершин будущего графа? это и есть начальные /конечные точки маршрута exp989. Под "графом" я всегда понимал топологию "коридоров", которые полагал физическими коридорами. Это значит, что для конкретного плана граф один и то же независимо от того, какой тип материальных потоков будем рассматривать. Такое возможно? Просто тогда налагаем доп. ограничения на допустимый путь по графу. да, граф должен быть а) статический - определенный топологией коидоров и б) динамическая часть, определяемая точкам начала, конца маршрутов и точками вхождения для того чтобы добраться от начальной точки до линии маршрута exp9810. Ну и для начала главное, ручная оцифровка плана, превращение его в граф, совершенно не допустима? может допустим автоматизированный режим? для начала допустима. Поставил на второй ноут NanoCad Вечером. если успею - сниму точки с какого-нить плана exp98Да, и ещё важно. На приведённом рисунке некоторые "коридоры" по длине соизмеримы с шириной. Такое может быть?
соизмеримы могут, но не квадратны. Принимаем это за аксиому, чтобы можно было найти ось коридора.

exp98Вот вроде для затравки.
Я усматриваю 3 основных этапа задачи.
1) Превращение dwg в "наш" формат.

1.1. Прикрепил файл с оцифрованным чертежом.
sprAreas = координаты 4-х точек областей, доступных для трассировки
по ним нужно найти оси и пересечения осей для формирования вершин графа
sprWCentre - координаты рабочих центров
1-я точка центр круга, 2-я точка - направление начала движения, если потребуется (но лучше определить в VBA к ближайшей оси области)
ncGrafTemp - лист для составления графа
от точки x1y1 на листе sprWCentre нужно найти кратчайший путь до ближайшей оси - ребра графа, дополнить граф вершиной - точками входа в маршрут
ncTraceType - лист типов трасс (маршрутов)
для начала возьмем
а) Сырье класс1 и б) Готовая продукция = два типа маршрутов для которых потом найти пересечения


exp982) Собственна задачи на графе.

еще раз для слепеньких. Граф - это список вершин с координатами?

exp983) Экспорт и рисоваание найденных маршрутов в dwg.

3-экспорт не считал нужным. Вся идея - выполнять на лету.
Т.е. выбрал какой=то продукт к которому привязаны рабочие центры, сырьеЮ полуфабрикаты поделенные на классы из листа ncTraceType и показал на слое трассировку выпуска, посчитал расстояния для перемещения

exp98Да, а решаем в VBA? Тогда вот как я бы начал.
1) - полагаю сделанным, для этого составляю таблицу в эксел.

Нумерую все вершины графа как-нибудь. В таблице эксел эта нумерация отражена например так:
N1 X Y
N2 X Y
N3 X Y
..........

ЗАдаю размерность задачи, чтобы поместился рисунок, например до 25 вершин графа, рёбер будет примерно столько же.
Выбираю описание графа в виде матрицы вершин Г(25х25). Граф предполагается не направленный (т.е. движение в любую сторону возможно)? Тогда матрица Г будет симметричной. Если с направлениями, то не симметричной. Надо определиться с этим заранее.

Определяю Г(ij)
Каждую строку матрицы Г отводим для описания связей с остальными вершинами.
Г(ij)=0 <=> вершины i и j не связаны друг с другом, где i - строка, j - столбец
Г(ij)=1 <=> они связаны. Вместо 1 удобно писать вес ребра и "минус вес" если в этом направлении запрет движения.
В дальнейшем при поиске путей всегда двигаемся вдоль СТРОК.
Направленнось рёбер или нет можно будет поправить позднее: упрёмся - разберёмся. Лично мне нужно вспоминать как рекомендуют. Вроде длдя 2-направленности подразумевали 2 противонаправленных ребра - тогда матрица м.б. несимметрична.

2) Ну собственно этап поиска пути да, задаём начальную вершину, ограничения, конечную и впрёд - выбираем один из способов нахождения маршрута, а предварительно конвертируем матрицу Г() в требуемый формат. Результат возвращаем в виде матрицы М(25х25), а можно в виде последовательного направленного списка, состоящего из номеров вершин Г.

Пока в 0-м приближении так.
Ах ну да, очевидно, Ваш граф может содержать циклы, поэтому у него нет понятия корень/листья как у дерева. Для каждого маршрута, который хотим найти берутся вершины начала и конца маршрута.
нужно переварить малость... а если в коде и по порядку?

Часть вершин графа уже есть в списке рабочих центров = это точки назначения и источника
Остальные нужно определить: см. начало этого поста. Как это в коде реализовать?

Bobgos1.1. Прикрепил файл с оцифрованным чертежом. Картинка того, с чего снимались координаты:

HandKotBobgosпропущено...
Картинка того, с чего снимались координаты:

что-то картинку не видно
попробуйте открыть в новом окне

Михаил Ч.Для меня эта тема интересная с точки зрения нахождения кратчайшего пути.
Вся сложность состоит именно в построении корректного графа по чертежу.
Алгоритм нахождения кратчайших путей запрограммировать не сложно (алгоритмом Дейкстры, Левита, Форда-Беллмана, Флойда-Уоршелла), ссылку на реализации я уже давал.

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

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

Михаил Ч.,
Да, теперь начинаю понимать.
в Excel формулами построил отрезки осей прямоугольников. вроде вышло.

exp98Может с помощью рисунка половина моего плана станет понятней.

На диаграммах:
сверху: у(х) для коридоров, здесь угадываются контуры прямоугольников
снизу: у(х) для шариков, здесь видны напаравляющие веекторы.

0) На данный момент все координаты забиты вручную, зато имеем нужные признаки по принадлежности:
Вектор - шарик,
4 точки - прямоугольник.
Этот этап (п.0) ещё предстоит автоматизировать, а сейчас действуем по-задуманному. Заведомые ляпы - плз, критикуем.

не догоняю я точечные диаграммы
exp981)Для каждого прямоугольника составить уравнение прямой, которая будет его осью.
Уравнение имеет вид ax + by=c


Пойдем по пунктам
пункт 1 формулами состоял из шагов на картинке 1-0..1-3
1-0 - сортировка координат в составе строки массива областей. нужно реализовать в коде при снятии с dwg
1-1 - определяем средние координаты для x и y
1-2 - находим правильное направление (экстремумы, а точнее разницу между максимумом и минимумом по каждой оси для каждой области
1-3 - в зависимости от результата п1-2 присваиваем значение либо средних координат (т.е. средние значения по оси Х для области Xmin+(Xmax-Xmin)/2) , если у1-y2<x1-x2)
получены координаты отрезков - НО не прямых.

Внимание:
как полученные данные применить в виде уравнения?
для первой области в массиве прямая определяется кажется выражением:
a1+a2*x+b1+b2*y = 0,
где
b1=23130, b2=0
a1=0, a2=y
НО
для отрезка по сути еще нужно еще добавить, (а точнее только составить систему неравенств -условий) :
Xmax>=X>=Xmin
Y=Ymin+(Ymax-Ymin)/2

Вопрос: что использовать отрезки или прямые?
Если отрезки, то крайние точки отрезков не являются точками пересечения осей (см. рисунок) и нужно искать ближайшую точку пересечений. Как?
Если прямые, то не учитываются ограничения коридоров. И точек пересечение будет больше или они будут одинаковыми и понять какой вес (длина) у ребра графа действительна (не пересекает стену) не получится.