Моделирование транспортных потоков в среде Borland C++ Builder

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Государственное образовательное учреждение высшего профессионального образования «Московский государственный технический университет им. Н.Э. Баумана»

Калужский филиал

Факультет «Фундаментальных Наук»

Кафедра «Программного обеспечения ЭВМ, информационных технологий и прикладной математики» (ФН1-КФ)

РАСЧЕТНО-ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОЙ РАБОТЕ

На тему «Моделирование транспортных потоков в среде Borland C++ Builder»

По курсу «Моделирование»

Студент: Мосин В. В.

Группа: ИТД — 82

Преподаватель: Гинзгеймер С. А.

Калуга — 2010 г.

1. Техническое задание на разработку пакета программ

Данный курсовой проект представляет собой приложение, позволяющее моделировать транспортные потоки на сложных перекрестках. Тип модели — микромодель потока на основе алгоритма «следования за лидером».

1.1 Назначение и область применения

Проект создан для расчета длин очередей машин на подъездах к пересечениям проезжих частей на перекрестках.

1.2 Требования к программе

1.2. 1 Требования к функциональным характеристикам

Программа должна обеспечивать:

· возможность построения графа сложного перекрестка

· моделирование поведения отдельных участников потока (машин) с учетом принятых правил проезда перекрестков

· динамическое изменение параметров инфраструктуры перекрестка (приоритеты проезда пересечений, состояние, период переключения и фазы светофоров)

· отслеживание состояния системы в реальном времени

· графическое отображение текущей информации о системе

1.2.2 Требования к надежности

1.2.2.1 Требования к обеспечению надежного функционирования программы

Надежное функционирование программы должно быть обеспечено выполнением Заказчиком совокупности организационно-технических мероприятий, перечень которых приведен ниже:

а) организацией бесперебойного питания технических средств;

б) использованием лицензионного программного обеспечения;

в) регулярным выполнением требований ГОСТ 51 188–98. Защита информации.

1. 2.2.2 Отказы из-за некорректных действий пользователей системы

Отказы программы вследствие некорректных действий пользователя при взаимодействии с программой недопустимы.

1.3 Условия эксплуатации

1.3.1 Требования к составу и параметрам технических средств

В состав технических средств должен входить IВМ-совместимый персональный компьютер (ПЭВМ) включающий в себя:

1. процессор Pentium-4, не менее 2400MHz;

2. оперативную память объемом, 128 Мегабайт, не менее;

3. HDD, 2 Гигабайт, не менее;

4. операционную систему семейства Windows, начиная с версии Windows 95;

5. Монитор, поддерживающий разрешение от 1024×768 и выше;

6. Клавиатура и мышь;

1.4 Требования к программной документации

1.4.1 Предварительный состав программной документации

Состав программной документации должен включать в себя:

1. Должны быть разработаны следующие программные документы:

2. Техническое задание (ГОСТ 34. 602−89).

3. Исследовательская часть (ГОСТ 19. 506−79).

4. Диаграмма классов (UML)

6. Блок-схема основных алгоритмов

6. Примеры (диаграмма)

1.5 Стадии и этапы разработки

1.5.1. Стадии разработки

Разработка должна быть проведена в три стадии:

1. разработка технического задания;

2. проектирование программы;

3. реализация программы;

1.5.2 Этапы разработки

На стадии разработки технического задания должен быть выполнен этап разработки, согласования и утверждения настоящего технического задания.

На стадии рабочего проектирования должны быть выполнены перечисленные ниже этапы работ:

1. выбор средств для создания;

2. проектирование всей системы;

3. разработка программной документации;

На последней стадии, выполняется испытание программы, которая была спроектированная на втором этапе.

1.5.3 Содержание работ по этапам

На этапе разработки технического задания должны быть выполнены перечисленные ниже работы:

1. постановка задачи;

2. определение и уточнение требований к техническим средствам;

3. определение требований к программе;

4. определение стадий, этапов и сроков разработки программы и документации на неё;

5. согласование и утверждение технического задания. На этапе проектирования программы должна быть выполнена работа по выбору средств для выполнения проекта, и описание назначения основных модулей программы.

На этапе разработки программной документации должна быть выполнена разработка программных документов в соответствии с требованиями к составу документации.

На этапе испытания программы должны быть выполнены перечисленные ниже виды работ:

1. разработка, согласование и утверждение и методики испытаний;

2. проведение приемо-сдаточных испытаний;

3. корректировка программы и программной документации по результатам испытаний.

2. ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ

2.1 Общие сведения о программной платформе и среде разработки

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

Язык С++ один из самых быстрых язаков программирования, что является решающим фактором при разработке системы реального времени. Кроме того набор встроенных элементов Borlan C++ Builder предоставляет удобные средства для работы с динамически распределяемыми данными.

2.2 Обоснование выбора темы

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

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

· транспортный поток нестабилен и многообразен, получение
объективной информации о нем является наиболее слож
ным и ресурсоемким элементом системы управления;

· критерии качества управления дорожным движением про
тиворечивы: необходимо обеспечивать бесперебойность дви
жения одновременно снижая ущерб от движения, наклады
вая ограничения на скорость и направления движения;

· дорожные условия, при всей стабильности, имеют непредсказуемые как в части отклонения погодно-климатических параметров так и, собственно, дороги;

· исполнение решений по управлению дорожным движением всегда неточно при реализации и, учитывая природу процесса дорожного движения, приводит к непредвиденным эффектам.

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

Можно ли обойтись без математических моделей и численных экспериментов, ограничившись результатами инженерных расчетов? К примеру, для расчета разгрузки дорожного участка, требуется знать, какое количество автомобилей поворачивает на некотором перекрестке направо. До сих пор никто туда не поворачивал — данных для расчетов нет. Приходится опираться на грубые экспертные оценки. Более того, транспортный поток все время подстраивается под управляющие воздействия. Эффект просчитанной разгрузки исчезает через некоторое время, за счет перераспределения транспортного потока. Если в связи с флуктуациями или случайными факторами резко возрастает количество заторов, на следующий день интенсивность движения, как правило, снижается.

Следовательно, моделирование необходимо в силу следующих свойств транспорной системы:

· компенсация увеличения пропускной способности при развитии сети увеличением спроса и перераспределением его в новых условиях;

· непредсказуемость поведения каждого водителя — выбор маршрута, манера вождения и проч. ;

· влияние случайных факторов (ДТП, погода и проч.) и флуктуаций, связанных с сезонами, выходными и праздничными днями и т. п.

2.3 Классификация моделей транспортных потоков

В моделировании дорожного движения исторически сложилось два основных подхода — детерминистический и вероятностный (стохастический).

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

Все модели транспортных потоков можно разбить на три класса [35]: модели-аналоги, модели следования за лидером и вероятностные модели.

· В моделях-аналогах движение транспортного средства уподобляется какому либо физическому потоку (гидро и газодинамические модели). Этот класс моделей принято называть макроскопическими.

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

· В вероятностных моделях транспортный поток рассматривается как результат взаимодействия транспортных средств на элементах транспортной сети. В связи с жестким характером ограничений сети и массовым характером движения в транспортном потоке складываются отчетливые закономерности формирования очередей, интервалов, загрузок по полосам дороги и т. п. Эти закономерности носят существенно стохастический характер.

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

2.4 Обоснование выбора используемой модели

В пределах одного перекрестка количество машин попадающих в область обработки строго ограничена физической вместимостью перекрестка.

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

Для расчета состояния системы, состоящей из одного перекрестка вполне достаточно вычислительной мощности одного ПК.

3. КОНСТРУКТОРСКАЯ ЧАСТЬ

3. 1 Описание логической структуры программы

Общая структура модели:

На каждом шаге мы имеем следующие данные о системе:

· Текущее системное время t

· Напрвленный граф разрешенных траекторий движения по перекрестку

o Множество вершин

§ Состояние вершины (движение или разрешено светофором или запрещено)

§ Приоритет вершины (знак «главная дорога» или знак «уступи дорогу»)

o Множество ребер

§ Список указателей на машины, находящиеся на данном ребре (загруженность)

§ Вес ребра (вес определяется исходя из длины ребра и его загруженности).

· Множество машин

o Текущее положение машины

o Текущее состояние машины (ускорение или замедление машины, а так же ее скорость)

Чтобы перевести систему в новое состояние необходимо:

· Выполнить расчет новых текущих параметров машин с учетом алгоритма их поведения

· Вычислить новые положения машин с учетом вычисленных на предыдущем этапе параметров (ускорение, замедление)

· Перевести текущее время системы в новое значение t'

Непрерывно переводя систему в новое положение, получаем непрерывный процесс изменения состояния системы от времени.

3. 2 Структура классов

Для моделирования структуры проезжих частей и допустимых траекторий движения на перекрестке используется направленный граф. Вершины графа — точки слияния траекторий, а ребра графа — траектории движения на данном участке полосы.

Класс vertex — описывает отдельный узел графа.

Параметры

· double X, Y; - координаты для отображения узла на экране.

· TList *s_owners; - список ребер, исходящих из этой вершины.

· TList *e_owners; - список ребер, заканчивающихся в этой вершине.

· bool checked; - флаг проверки, используемый в алгоритме Дейкстры для поиска пути

· double W; - текущая цена пути до этой вершины, используется в алгоритме Дейкстры

· bool is_open; - флаг, показывающий, разрешен ли в настоящий момент проезд через эту вершину (состояние светофора, влияющего на эту вершину)

· TDateTime LastCh; - время последнего изменения состояния светофора

· int period_in_msec; - период работы светофора, принимает положительные значения и -1. Если значение данного параметра равно -1, значит данная вершина всегда открыта (не регулируется светофором)

· float closed_to_per; - соотношение времени закрытия светофора к его периоду работы в процентах.

· bool main; - принадлежность к «главной» траектории на перекрестке, имитирует знак «главная дорога».

· bool in_out; - флаг, показывающий, является ли данная вершина въездом на перекресток или выездом с перекрестка.

Методы

· vertex: :vertex (); - конструктор вершины

· int vertex: :time_to_change (); - функция, возвращает время, оставшееся до изменения состояния светофора

Структура edge — ребро графа.

Параметры

· double r_length; - длина ребра в метрах.

· vertex *start; - вершина, являющаяся началом этого ребра.

· vertex *end; - вершина, являющаяся концом этого ребра.

· double angles[2]; - углы направлений входящего и исходящего ребер.

· double angle; - угол направления данного ребра

· TList *cars; - динамический список машин, находящихся на ребре.

· TList *cross_pts; - список пересечений с другими ребрами, не являющихся вершинами.

· bool linear; - флаг, показывающий, является ли ребро прямой или дугой.

· TColor C; - цвет для отображения ребра на экране

· int w; - динамический вес ребра (зависит от плотности потока на ребре)

· double scale; - масштаб отображения

Методы

· void edge: :get_point (double p, double & X, double & Y); - функция, возвращает переменных X и Y значения координат в точке p траектории. (р изменяется от 0 до 1, 0 — начало ребра, 1 — конец ребра).

Структура e_cross — информация о пересечении ребер, не являющемся вершиной.

Параметры

· double p; - положение пересечения на первом ребре.

· edge *E; - первое ребро

· double p_; - положение пересечения на втором ребре

· edge *E_; - второе ребро.

· bool you_major; - флаг приоритета первого ребра над вторым.

Класс graph

Параметры

· bool finding; - флаг, отмечающий, что в данный момент на графе производится поиск пути одной из его машин. Если данный флаг установлен в значение истины, параметры вершин и ребер графа изменять нельзя.

· double scale; - масштаб отображения графа.

· TList *Verts; - динамический список вершин графа

· TList *Edges; - динамический список ребер графа

· TList *Cars; - динамический список машин, находящихся на графе

Методы

· graph: :graph (); - конструктор графа

· void graph: :add_v (vertex *V); - добавить вершину V в граф

· void graph: :connect_v (vertex *V1, vertex *V2, bool l); - связать две вершины V1 и V2 ребром, если флаг l — истина — ребро является прямой, иначе — ребро является дугой.

· void graph: :draw (); - функция, отображающая граф и все машины на экране.

· void graph: :reconnect (); - функция, проверяющая связность графа и правильность параметров отображения ребер.

· TList *graph: :path (vertex *V1, vertex *V2); - функция, возвращает список вершин, через которые проходит маршрут между вершинами V1 и V2.

· bool graph: :is_reachable (vertex *V1, vertex *V2); - проверяет, достижима ли вершина V2 из вершины V1.

· void graph: :find_crosses (); - найти все пересечения ребер

· TList *graph: :find_cross_pts (edge *E); - найти пересечения для ребра Е.

Класс car — класс описывает отдельную машину и реализует ее поведение.

Параметры

· edge *line; - текущее ребро

· edge *next_line; - следующее ребро маршрута

· vertex *Aim; - целевая вершина

· vertex *start; - стартовая вершина

· TList *otherCars; - указатель на список всех машин в системе

· TList *path_edges; - список ребер, составляющих путь следования к целевой вершине

· bool pomeha; - флаг наличия помехи

· bool stop_on_red; - флаг остановки на светофоре

· double place — текущее положение на ребре

· int e_index; - номер позиции на ребре

· int cX, cY; - координаты для отображения

· car *main_car; - указатель на машину, представляющую собой помеху

· e_cross *danger_cross; - пересечение, на котором существует помеха.

· float max_speed; - максимальная скорость в м/мсек

· float curr_speed; - текущая скорость в м/мсек

· float max_uskor; - максимальное ускорение в м/мсек2

· float max_zamedl; - максимальное замедление в м/мсек2

· float curr_uskor; - текущее ускорение в м/мсек2

· float curr_zamedl; - текущее замедление в м/мсек2

· TDateTime PrevTime; - время последнего изменения состояния

· graph *road; - указатель на граф, содержащий текущую траекторию

Методы

· car: :car (double m_s, double m_u, double m_z, double c_s, vertex *Start, vertex *Finish, graph *Road, TList *otCars); - конструктор машины, параметры m_s — максимальная скорость, m_u — максимальное ускорение, m_z — максимальное замедление, c_s — начальная скорость, Start — исходная вершина, Finish — конечная вершина, Road — граф траекторий, otCars — указатель на списокостальных машин.

· void car: :start_first_line (vertex *V, vertex *Vn); - получить начальное состояние, в вершине V с целевой вершине Vn.

· void car: :get_state (); - вычислить новое состояние.

· void car: :move (); - перейти в новое состояние.

· void car: :get_next_line (double Ln); - перейти на новую траекторию

· void car: :draw (); - отобразить машину

· double car: :dX_now (); - получить текущее смещение между текущим и следующим состоянием

· double car: :next_pos_now (); - получить значение следующего положения машины на траектории.

· double car: :crit_dist (); - получить критическую дистанцию для данной машины

· double car: :dist_by_time (double accel, double time_ms); - определить путь, пройденный с указанным ускорением, за указанное время.

· double car: :dist_to_stop (double accel); - определить тормозной путь с заданнымзамедлением.

· double car: :accel_by_dist_to_stop (double Ln); - получить ускорение необходимое для того, чтобы остановиться на указанном отрезке.

· double car: :accel_by_next_car (double s_next, double dist41, double realdist); - получить ускорение для коррекции состояния по следующей машине (следование за лидером)

· double car: :time_for_dist (double dist); - определить время прохождения дистанции

· double car: :check_distance (double & next_speed); - скорректировать состояние относительно скорости впереди едущей машины для соблюдения оптимальной дистанции.

· double car: :nearest_car_dist (); - определить дистанцию до ближайшей машины впереди на текущей траектории.

· void car: :follow (); - определить состояние с учетом только следования за лидером

· void car: :is_danger (); - определить состояние с учетом помех

· void car: :is_not_danger (); - определить состояние с учетом существующей помехи, проверить условие отмены помехи.

· void car: :check_light (); - проверить ближайший светофор впереди

· car *car: :take_prev_car (double & prev_dist); - получить указатель на идущую сзади машину

3. 3 Основные алгоритмы

3. 3.1 Алгоритм следования за лидером

Данный алгоритм предполагает, что единственным фактором, влияющим на поведение машины является дистанция до ближайшей машины впереди и характер ее движения. Если ближайшая машина впереди не представляет собой помеху, т. е. для поддержания безопасного расстояния до него не требуется замедляться, то каждая машина стремится к достижению максимальной скорости за наименьшее время.

Алгоритм можно кратко описать следующим образом:

· Если на текущей траектории впереди нет машин вообще, то считаем данную машину лидером. Следующее состояние будет нацелено на достижение максимально скорости:

· Если впереди есть машина, то принимаем ее за лидера. Если скорость лидера больше и дистанция до него больше минимально допустимой, то следующее состояние так же направлено на достижение максимально скорости.

· Если текущая скорость и скорость лидера одинаковы, проверяем дистанцию. Если дистанция больше минимально допустимой, принимаем максимально возможное ускорение, иначе принимаем такое замедление, чтобы как можно скорее нормализовать дистанцию.

· Если скорость лидера меньше, принимаем такое ускорение, при котором скорости сравняются на расстоянии равном минимально допустимой дистанции.

Данный алгоритм исключает возможность обгонов, а так же столкновений при корректном начальном состоянии.

3. 3.2 Алгоритм Дейкстры для поиска пути по графу

Введем следующие ограничения:

· V -- множество вершин графа

· E -- множество ребер графа

· w[ij] -- вес (длина) ребра ij

· a -- вершина, расстояния от которой ищутся

· U -- множество посещенных вершин

· d[u] -- по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u

· p[u] -- по окончании работы алгоритма содержит кратчайший путь из a в u

Присвоим

Для всех отличных от a

присвоим

Пока

Пусть -- вершина с минимальным d[v]

Для всех таких, что

если d[u] > d[v] + w[vu] то

изменим

изменим

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U -- массив булевых переменных.

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

На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0. Последний случай возможен тогда и только тогда, когда граф G не связан.

3. 3.3 Алгоритм принятия решения для отдельного участника потока

Для реализации более реалистичного поведения отдельной машины алгоритм следования за лидером был доработан следующим образом:

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

· Анализ состояния ближайшего светофора на пути следования

· Анализ помех на пересечениях текущего ребра и следующего ребра маршрута.

На выходе мы имеем 3 пары параметров:

· Ускорение и замедление для поддержания дистанции

· Ускорение и замедление для своевременного проезда светофора

· Ускорение и замедление для уступания дороги помехе.

Если хотя бы одно из замедлений больше 0, то в качестве текущего параметра выбирается максимальное из замедлений.

Если все ускорения больше 0, а все замедления равны 0, то в качестве текущего параметра выбирается наименьшее из ускорений.

Наличие помехи проверяется следующим образом:

пока (не все пересечения для текщего ребра проверены)

если (на выбранном пересечении нужно уступать)

начало условия

найти ближайшую к пересечению машину (Car)

найти время достижения пересечения t1

пока (есть машина или не найдена помеха)

начало цикла

найти время достижения машиной пересечения t2

если (модуль разности |t1-t2| < 8 секунд)

флаг помехи = 1

установить ускорение = 0

установить достаточное замедление

иначе

перейти к следующей за текущей (Car) машине

конец цикла

перейти к след шагу цикла

конец условия

перейти к след шагу цикла

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

4. ТЕХНОЛОГИЧЕСКАЯ ЧАСТЬ

4. 1 Назначение программы

Данная программа предназначена для моделирования транспортных потоков на перекрестке.

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

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

4. 2 Запуск и выполнение

Для запуска программы необходимо запустить исполняемый. exe файл. Далее с помощью встроенного редактора построить граф допустимых траекторий движения на перекрестке, создать светофоры и задать периоды их переключений, задать плотности потока на въездах на перекресток.

После чего нажав кнопку Start Redraw запустить цикл расчета и отображения состояний системы.

4. 3 Системные требования

1. процессор Pentium-4, не менее 2400MHz;

2. оперативную память объемом, 128 Мегабайт, не менее;

3. HDD, 2 Гигабайт, не менее;

4. операционную систему семейства Windows, начиная с версии Windows 95;

5. Монитор, поддерживающий разрешение от 1024×768 и выше;

6. Клавиатура и мышь;

Заключение и выводы

В результате выполнения данной курсовой работы мною были получены следующие выводы:

· Выбранная мной модель поведения отдельной машины удовлетворяет требованиям данной модели.

· Полученная система масштабируема в ущерб производительности программы.

· Существует максимальное допустимое количество одновременно корректно обрабатываемых машин. Чем больше машин одновременно обрабатывается, тем больше временной интервал между смежными рассчитанными состояниями каждой машины, что отрицательно сказывается на работе алгоритмов принятия решений.

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

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

перекресток алгоритм транспортный поток

Список литературы

1. ШвецовВ.И. Математическое моделирование транспортных потоков // Автоматика и телемеханика. - 2003. -№ 11

2. Семенов В. В. Математическое моделирование динамики транспортных потоков мегаполиса

3. Харари Ф. Теория графов // Едиториал УРСС 2003 г.

4. Ермолаев В., Сорока Т. C++ BLILDER: Книга рецептов// москва 2006

Приложение

//---------------------------------------------------------------------------

#include < vcl. h>

#pragma hdrstop

#include «Graphs. h»

#include «Main. h»

#include < math. h>

#include «Cars. h»

#include «Car_thr. h»

#include «Redraw. h»

//---------------------------------------------------------------------------

#pragma package (smart_init)

#pragma resource «*. dfm»

TForm1 *Form1;

graph *G;

//TList *AllCars;

vertex *V1, *V2;

bool start;

bool move;

double dist (int X, int Y, vertex *V){

return sqrt ((V-> X-X)*(V->X-X) + (V-> Y-Y)*(V->Y-Y));

}

//---------------------------------------------------------------------------

__fastcall TForm1: :TForm1(TComponent* Owner)

: TForm (Owner)

{

G = new graph ();

G-> scale = Form1-> Edit1->Text. ToDouble ();

V1=NULL;

V2=NULL;

move = 0;

G-> Cars = new TList;

start=0;

}

//---------------------------------------------------------------------------

void __fastcall TForm1: :Button1Click (TObject *Sender)

{

Form1-> RadioButton1->Checked=false;

Form1-> RadioButton2->Checked=false;

Form1-> RadioButton3->Checked=false;

Form1-> RadioButton4->Checked=false;

for (int i = 0; i < G-> Edges->Count; i++) {

edge *E = (edge *)G-> Edges->Items[i];

E->C = 0xaaaaaa;

E->w = 1;

}

G-> draw ();

}

//---------------------------------------------------------------------------

void __fastcall TForm1: :Image1MouseDown (TObject *Sender, TMouseButton Button, TShiftState Shift,

int X, int Y)

{

G-> scale = Form1-> Edit1->Text. ToDouble ();

if (Form1-> RadioButton1->Checked) { //vertexes

vertex *V = new vertex ();

V->X = X;

V->Y = Y;

G-> add_v (V);

}

if (Form1-> RadioButton2->Checked) { //line

for (int i = 0; i < G-> Verts->Count; i++) {

vertex *V = (vertex*)G-> Verts->Items[i];

double R = dist (X, Y, V);

if (R < 5) {

if (V1) {

V2 = V;

G-> connect_v (V1,V2,true);

V1=NULL;

V2=NULL;

}

else{

V1 = V;

}

}

}

}

if (Form1-> RadioButton3->Checked) {

for (int i = 0; i < G-> Verts->Count; i++) {

vertex *V = (vertex*)G-> Verts->Items[i];

double R = dist (X, Y, V);

if (R < 5) {

if (V1) {

V2 = V;

G-> connect_v (V1,V2,false);

V1=NULL;

V2=NULL;

}

else{

V1 = V;

}

}

}

}

if (Form1-> RadioButton4->Checked) {

for (int i = 0; i < G-> Verts->Count; i++) {

vertex *V = (vertex*)G-> Verts->Items[i];

double R = dist (X, Y, V);

if (R < 5) {

if (V1) {

V2 = V;

TList *P = G-> path (V1,V2);

if (P-> Count > 0) {

for (int i = 0; i < P-> Count-1; i++) {

vertex *V = (vertex *)P-> Items[i];

vertex *V_n = (vertex *)P-> Items[i+1];

for (int j = 0; j < V-> s_owners->Count; j++) {

edge *E = (edge *)V-> s_owners->Items[j];

if (E-> end->X == V_n->X & & E-> end->Y == V_n-> Y) {

E->C = 0×00ff00;

E->w = 2;

}

}

}

}

V1=NULL;

V2=NULL;

}

else{

for (int i = 0; i < G-> Edges->Count; i++) {

edge *E = (edge *)G-> Edges->Items[i];

E->C = 0xaaaaaa;

E->w = 1;

}

V1 = V;

}

}

}

}

if (!Form1-> RadioButton1->Checked & & !Form1-> RadioButton2->Checked & & !Form1-> RadioButton3->Checked & & !Form1-> RadioButton4->Checked) {

for (int i = 0; i < G-> Verts->Count; i++) {

vertex *V = (vertex*)G-> Verts->Items[i];

double R = dist (X, Y, V);

if (R < 5) {

move = 1;

V1 = V;

if (Button == mbRight) {

V-> main = !V-> main;

}

}

}

}

G-> reconnect ();

G-> find_crosses ();

G-> draw ();

}

//---------------------------------------------------------------------------

void __fastcall TForm1: :Image1MouseMove (TObject *Sender, TShiftState Shift, int X,

int Y)

{

if (move) {

V1->X = X;

V1->Y = Y;

G-> find_crosses ();

G-> reconnect ();

G-> draw ();

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1: :Image1MouseUp (TObject *Sender, TMouseButton Button, TShiftState Shift,

int X, int Y)

{

if (move) {

move=0;

V1=NULL;

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1: :FormResize (TObject *Sender)

{

Form1-> ScrollBox1->Width = Form1-> ClientWidth — Form1-> ScrollBox1->Left;

Form1-> ScrollBox1->Height = Form1-> ClientHeight — Form1-> ScrollBox1->Top;

}

//---------------------------------------------------------------------------

void __fastcall TForm1: :Button2Click (TObject *Sender)

{

vertex *s, *f;

//car *C = new car (0. 0194,1. 85e-6,-3. 7e-6,0. 016, s, f);

TList *Sta, *Fin;

Sta = new TList;

Fin = new TList;

for (int i = 0; i < G-> Verts->Count; i++) {

vertex *V = (vertex*)G-> Verts->Items[i];

if (V-> s_owners->Count > 0 & & V-> e_owners->Count ==0) {

Sta-> Add (V);

}

if (V-> s_owners->Count == 0 & & V-> e_owners->Count > 0) {

Fin-> Add (V);

}

}

int sn = rand ()%(Sta-> Count);

int fn = rand ()%(Fin-> Count);

s = (vertex*)Sta-> Items[sn];

f = (vertex*)Fin-> Items[fn];

car *C = new car (0. 0194,0. 185,-0. 37,0. 01, s, f, G, G->Cars);

//Car_thr *CT = new Car_thr (0,C);

}

//---------------------------------------------------------------------------

void __fastcall TForm1: :Button3Click (TObject *Sender)

{

start=1;

while (start){

for (int i = 0; i < G-> Cars->Count; i++) {

car *C = (car *)G-> Cars->Items[i];

C-> move ();

if (C-> line == NULL) {

G-> Cars->Delete (G->Cars->IndexOf (C));

delete C;

}

G-> draw ();

Application-> ProcessMessages ();

}

Application-> ProcessMessages ();

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1: :Button4Click (TObject *Sender)

{

start = 0;

}

//---------------------------------------------------------------------------

#ifndef GraphsH

#define GraphsH

#include < vcl. h>

#include < math. h>

#include < systdate. h>

class vertex{

public:

double X, Y;

TList *s_owners;

TList *e_owners;

//for path

bool checked;

double W;

TList *path;

//for cars

bool is_open;

TDateTime LastCh;

int period_in_msec; //-1 = бесконечность

float closed_to_per; //процентное соотношение закрытого времени к периоду

bool main;

bool in_out; //въезд или выезд;

vertex: :vertex ();

int vertex: :time_to_change ();

};

struct edge{

double r_length;

vertex *start;

vertex *end;

double angles[2];

double angle;

TList *cars;

TList *cross_pts;

bool linear;

TColor C;

int w;

double scale;

void edge: :get_point (double p, double & X, double & Y);

};

struct e_cross{

double p;

edge *E;

double p_;

edge *E_;

bool you_major;

};

class graph{

public:

bool finding;

double scale;

TList *Verts;

TList *Edges;

TList *Cars;

graph: :graph ();

void graph: :add_v (vertex *V);

void graph: :connect_v (vertex *V1, vertex *V2, bool l);

void graph: :draw ();

void graph: :reconnect ();

TList *graph: :path (vertex *V1, vertex *V2);

bool graph: :is_reachable (vertex *V1, vertex *V2);

void graph: :find_crosses ();

TList *graph: :find_cross_pts (edge *E);

};

bool edges_cross (edge *e1, edge *e2, int acc, double & x1, double & x2);

//---------------------------------------------------------------------------

#endif

//---------------------------------------------------------------------------

#pragma hdrstop

#include «Graphs. h»

#include «Main. h»

#include < vcl. h>

#include < math. h>

#include «Cars. h»

//---------------------------------------------------------------------------

#pragma package (smart_init)

Graphics: :TBitmap *map;

vertex: :vertex (){

s_owners = new TList;

e_owners = new TList;

this-> main = false;

this-> is_open = true;

path = new TList;

this-> period_in_msec = -1;

}

void draw_v (vertex *v){

int r;

if (v-> main) {

r = 5;

}

else{

r=3;

}

int x, y;

x = v-> X;

y = v-> Y;

if (v-> is_open) {

Form1-> Image1->Canvas->Pen->Color = (TColor)0×449 944;

Form1-> Image1->Canvas->Brush->Color = (TColor)0×22ff22;

Form1-> Image1->Canvas->Ellipse (x-r, y-r, x+r, y+r);

}

else{

Form1-> Image1->Canvas->Pen->Color = (TColor)0×444 499;

Form1-> Image1->Canvas->Brush->Color = (TColor)0×2222ff;

Form1-> Image1->Canvas->Ellipse (x-r, y-r, x+r, y+r);

}

};

double get_angle (vertex *s, vertex *e){

double A = -2*M_PI;

if (s->X == e-> X) {

if (s->Y < e-> Y) {

A = M_PI/2;

}

else{

A = -M_PI/2;

}

}

if (s->Y == e-> Y) {

if (s->X < e-> X) {

A = 0;

}

else{

A = M_PI;

}

}

if (A == -2*M_PI) {

A = atan (fabs (e-> Y-s->Y)/fabs (e->X-s->X));

if (e->X < s->X & & e->Y > s-> Y) {

A = M_PI — A;

}

if (e->X < s->X & & e->Y < s-> Y) {

A = -(M_PI-A);

}

if (e->X > s->X & & e->Y < s-> Y) {

A = -A;

}

}

return A;

}

bool is_line (vertex *s, vertex *e, double a[2]){

if (fabs (a[0])≠fabs (a[1])) {

return 0;

}

else{

double A = get_angle (s, e);

if (fabs (a[0]) == fabs (a[1]) & & fabs (a[0]) == fabs (A)) {

return 1;

}

}

return 0;

}

double dist_v (vertex *v1, vertex *v2){

return sqrt ((v1-> X-v2->X)*(v1->X-v2->X)+(v1->Y-v2->Y)*(v1->Y-v2->Y));

}

double draw_besier (vertex *s, vertex *e, double a[2], double scale, TColor C, int w){

double x0, y0,x1,y1,x2,y2,x3,y3;

double R = dist_v (s, e);

x0 = s-> X;

y0 = s-> Y;

x1 = x0 + (R/2)*cos (a[0]);

y1 = y0 + (R/2)*sin (a[0]);

x3 = e-> X;

y3 = e-> Y;

x2 = x3 — (R/2)*cos (a[1]);

y2 = y3 — (R/2)*sin (a[1]);

double x0, y0, x1, y1, x2, y2, x3, y3, x4, y4, X, Y;

X = x0;

Y = y0;

while (Form1-> Image1->Canvas->TryLock ()){}

Form1-> Image1->Canvas->Pen->Width=w;

Form1-> Image1->Canvas->Pen->Color = C;

Form1-> Image1->Canvas->MoveTo (X, Y);

double len=0;

for (double x = 0; x < 1; x+=0. 01) {

x0 = x0 + x*(x1-x0);

y0 = y0 + x*(y1-y0);

x1 = x1 + x*(x2-x1);

y1 = y1 + x*(y2-y1);

x2 = x2 + x*(x3-x2);

y2 = y2 + x*(y3-y2);

x3 = x0 + x*(x1-x0);

y3 = y0 + x*(y1-y0);

x4 = x1 + x*(x2-x1);

y4 = y1 + x*(y2-y1);

double X1, Y1;

X1 = x3 + x*(x4-x3);

Y1 = y3 + x*(y4-y3);

Form1-> Image1->Canvas->LineTo (X1,Y1);

double dl = sqrt ((X1-X)*(X1-X) + (Y1-Y)*(Y1-Y))*scale;

len+=dl;

X=X1;

Y=Y1;

}

return len;

}

void draw_e (edge* e, double scale){

int x1, y1,x2,y2;

x1 = e-> start->X;

y1 = e-> start->Y;

x2 = e-> end->X;

y2 = e-> end->Y;

if (is_line (e-> start, e->end, e->angles)) {

Form1-> Image1->Canvas->Pen->Color = e-> C;

if (e-> cross_pts->Count > 0) {

Form1-> Image1->Canvas->Pen->Color = 0xffffff — e-> C;

}

Form1-> Image1->Canvas->Pen->Width = e-> w;

Form1-> Image1->Canvas->MoveTo (x1,y1);

Form1-> Image1->Canvas->LineTo (x2,y2);

e-> r_length = sqrt ((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))*scale;

}

else{

if (e-> cross_pts->Count > 0) {

e-> r_length = draw_besier (e-> start, e->end, e->angles, scale, 0xffffff-e->C, e->w);

}

else{

e-> r_length = draw_besier (e-> start, e->end, e->angles, scale, e->C, e->w);

}

}

Form1-> Image1->Canvas->Pen->Width = 1;

}

void edge: :get_point (double p, double & X, double & Y){

if (linear) {

X = (this-> end->X — this-> start->X)*p+this->start->X;

Y = (this-> end->Y — this-> start->Y)*p+this->start->Y;

}

else{

double x0, y0,x1,y1,x2,y2,x3,y3;

double R = dist_v (start, end);

x0 = start-> X;

y0 = start-> Y;

x1 = x0 + (R/2)*cos (angles[0]);

y1 = y0 + (R/2)*sin (angles[0]);

x3 = end-> X;

y3 = end-> Y;

x2 = x3 — (R/2)*cos (angles[1]);

y2 = y3 — (R/2)*sin (angles[1]);

double x0, y0, x1, y1, x2, y2, x3, y3, x4, y4;

x0 = x0 + p*(x1-x0);

y0 = y0 + p*(y1-y0);

x1 = x1 + p*(x2-x1);

y1 = y1 + p*(y2-y1);

x2 = x2 + p*(x3-x2);

y2 = y2 + p*(y3-y2);

x3 = x0 + p*(x1-x0);

y3 = y0 + p*(y1-y0);

x4 = x1 + p*(x2-x1);

y4 = y1 + p*(y2-y1);

X = x3 + p*(x4-x3);

Y = y3 + p*(y4-y3);

}

}

graph: :graph (){

Verts = new TList;

Edges = new TList;

finding = false;

map = new Graphics: :TBitmap;

map-> LoadFromFile («map. bmp»);

Form1-> Image1->Width = map-> Width;

Form1-> Image1->Height = map-> Height;

}

void graph: :add_v (vertex *V){

Verts-> Add (V);

}

void graph: :connect_v (vertex *V1, vertex *V2, bool l){

edge *E = new edge;

E-> angle = get_angle (V1, V2);

E-> start = V1;

E-> end = V2;

E-> cars = new TList;

V1-> s_owners->Add (E);

V2-> e_owners->Add (E);

E-> angles[0] = E-> angle;

E-> angles[1] = E-> angle;

E->w = 1;

E->C = 0xaaaaaa;

E-> scale = this-> scale;

if (l) {

E-> linear = true;

}

else{

E-> linear = false;

if (E-> start->e_owners->Count > 0) {

edge * eo = (edge*)E-> start->e_owners->Items[0];

E-> angles[0] = eo-> angle;

}

if (E-> end->s_owners->Count > 0) {

edge * so = (edge*)E-> end->s_owners->Items[0];

E-> angles[1] = so-> angle;

}

}

Edges-> Add (E);

E-> cross_pts = new TList;

draw_e (E, this-> scale);

this-> find_crosses ();

}

void graph: :reconnect (){

for (int i = 0; i < Edges-> Count; i++) {

edge *E;

E = (edge *)Edges-> Items[i];

if (E-> linear) {

E-> angle = get_angle (E-> start, E-> end);

E-> angles[0] = E-> angle;

E-> angles[1] = E-> angle;

}

}

for (int i = 0; i < Edges-> Count; i++) {

edge *E;

E = (edge *)Edges-> Items[i];

if (!E-> linear) {

if (E-> start->e_owners->Count > 0) {

edge * eo = (edge*)E-> start->e_owners->Items[0];

E-> angles[0] = eo-> angle;

}

if (E-> end->s_owners->Count > 0) {

edge * so = (edge*)E-> end->s_owners->Items[0];

E-> angles[1] = so-> angle;

}

}

}

}

void draw_c (car *C, double scale){

Form1-> Image1->Canvas->Pen->Color = 0xff0000;

Form1-> Image1->Canvas->Brush->Color = 0xaa0000;

Form1-> Image1->Canvas->Rectangle (C->cX-2, C-> cY-2, C-> cX+2, C-> cY+2);

}

void graph: :draw (){

Form1-> Image1->Canvas->Brush->Color = 0xffffff;

Form1-> Image1->Canvas->Pen->Color = 0xffffff;

Form1-> Image1->Canvas->Rectangle (0,0,Form1->Image1->Width, Form1-> Image1->Height);

for (int i = 0; i < Verts-> Count; i++) {

vertex *V = (vertex *)Verts-> Items[i];

draw_v (V);

}

for (int i = 0; i < Edges-> Count; i++) {

edge *E = (edge*)Edges-> Items[i];

draw_e (E, scale);

}

for (int i = 0; i < Cars-> Count; i++) {

car *C = (car *)Cars-> Items[i];

draw_c (C, scale);

}

}

void check (vertex *V1){ //deep

for (int i = 0; i < V1-> s_owners->Count; i++) {

edge *E = (edge *)V1-> s_owners->Items[i];

vertex *V = E-> end;

if (!V-> checked) {

double P = E-> r_length + V1-> W;

if (V->W == -1) {

V->W = P;

V-> path->Clear ();

//V-> path = V1-> path;

for (int k = 0; k < V1-> path->Count; k++) {

V-> path->Add (V1->path->Items[k]);

}

V-> path->Add (V);

}

else{

if (V->W > P) {

V->W = P;

V-> path->Clear ();

//V-> path = V1-> path;

for (int k = 0; k < V1-> path->Count; k++) {

V-> path->Add (V1->path->Items[k]);

}

V-> path->Add (V);

}

}

}

}

V1-> checked = 1;

if (V1-> s_owners->Count > 0) {

for (int i = 0; i < V1-> s_owners->Count; i++) {

edge *E = (edge *)V1-> s_owners->Items[i];

vertex *V = E-> end;

if (!V-> checked) {

check (V);

}

}

}

}

void check_w (TList *Vs){ //width

while (Vs-> Count > 0) {

vertex *V1 = (vertex *)Vs-> Items[0];

for (int i = 0; i < V1-> s_owners->Count; i++) {

edge *E = (edge *)V1-> s_owners->Items[i];

vertex *V = E-> end;

if (!V-> checked) {

double P = E-> r_length + V1-> W;

if (V->W == -1) {

V->W = P;

V-> path->Clear ();

//V-> path = V1-> path;

for (int k = 0; k < V1-> path->Count; k++) {

V-> path->Add (V1->path->Items[k]);

}

V-> path->Add (V);

}

else{

if (V->W > P) {

V->W = P;

V-> path->Clear ();

//V-> path = V1-> path;

for (int k = 0; k < V1-> path->Count; k++) {

V-> path->Add (V1->path->Items[k]);

}

V-> path->Add (V);

}

}

}

}

V1-> checked = 1;

Vs-> Delete (0);

if (V1-> s_owners->Count > 0) {

for (int i = 0; i < V1-> s_owners->Count; i++) {

edge *E = (edge *)V1-> s_owners->Items[i];

vertex *V = E-> end;

if (!V-> checked) {

Vs-> Add (V);

}

}

}

}

}

TList *graph: :path (vertex *V1, vertex *V2){

this-> finding = true;

for (int i = 0; i < Verts-> Count; i++) {

vertex *V = (vertex*)Verts-> Items[i];

V->W = -1;

V-> checked = 0;

V-> path->Clear ();

}

V1->W = 0;

V1-> path->Add (V1);

TList *Q = new TList;

Q-> Add (V1);

check_w (Q);

TList *P = new TList;

for (int i = 0; i < V2-> path->Count; i++) {

P-> Add (V2->path->Items[i]);

}

Q-> Clear ();

delete Q;

this-> finding = false;

return P;

}

bool edges_cross (edge *e1, edge *e2, int acc, double & x1, double & x2){

if (e1 == e2) {

return 0;

}

double step1 = 1/e1-> r_length/acc;

double step2 = 1/e2-> r_length/acc;

double R = 5/e1-> scale;

x1=-1; x2=-1;

for (double i = 0; i < 1; i+=step1) {

for (double j = 0; j < 1; j+=step2) {

double X1, Y1,X2,Y2;

e1-> get_point (i, X1, Y1);

e2-> get_point (j, X2, Y2);

double R1 = sqrt ((X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1));

if (R1 < R) {

x1 = i;

x2 = j;

R=R1;

}

}

}

if (x1 > 0 & & x2 > 0 & & x1 < 1 & & x2 < 1) {

return 1;

}

else{

return 0;

}

}

int vertex: :time_to_change (){

if (this-> period_in_msec == -1) {

return -1;

}

else{

unsigned short h, m, s, ms;

this-> LastCh. DecodeTime (&h,&m,&s,&ms);

int Time0 = h*3 600 000 + m*60 000+s*1000+ms;

TDateTime CurT = Time ();

CurT. DecodeTime (&h,&m,&s,&ms);

int Time1 = h*3 600 000 + m*60 000+s*1000+ms;

return this-> period_in_msec — Time1 + Time0;

}

}

TList *graph: :find_cross_pts (edge *E){

e_cross *e_c;

TList *crosses = new TList;

for (int i = 0; i < this-> Edges->Count; i++) {

edge *E_ = (edge*)Edges-> Items[i];

double x, x_;

if (edges_cross (E, E_, 1, x, x_)) {

e_c = new e_cross;

e_c->p = x;

e_c->E = E;

e_c-> p_ = x_;

e_c-> E_ = E_;

//проверка на главность траектории в этом пересечении

//1 приоритет «главная дорога» / «уступи дорогу»

if (E_-> start->main ≠ E-> start->main) {

if (E-> start->main) {

ПоказатьСвернуть
Заполнить форму текущей работой