zabika.ru 1

Министерство образования Российской Федерации


Санкт-Петербургский государственный электротехнический университет

Курсовая работа

по дисциплине "Комбинаторные алгоритмы"

«Пересечение отрезков: метод заметания плоскости»

Выполнили: студенты гр. 5382 и 5395

Ботян И.

Воробьёва М.

Королёв Ю.

Овчаренко А.

Преподаватель: Преображенский А.

Санкт-Петербург

2010 г.

Постановка задачи


Дано: n прямолинейных отрезков на плоскости.

Найти: все попарные пересечения отрезков.

Описание программы


Программа предоставляет следующие возможности:

  1. Добавление отрезков на плоскости. Может производится несколькими способами:

  • загрузка из текстового файла

  • добавление отрезков

  • ручное добавление отрезков с помощью мыши

  • генерация указанного количества отрезков в заданном диапазоне

  1. Удаление всех или выбранного отрезка

  2. Сохранение добавленных отрезков в текстовый файл

  3. Нахождение попарных пересечений отрезков

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

  5. Отмена/повтор выполненных операций

Добавление отрезков на плоскости


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

После добавления отрезка внизу экрана в таблицу «Отрезки» будет добавлена строка, содержащая координаты начала и конца добавленного отрезка.





Загрузка из текстового файла


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

TABTABTAB


Например:

-10.05

110.3

80.2

-10

Для того, чтобы загрузить отрезки из файла, необходимо вызвать диалог загрузки файла. Это можно сделать путём нажатия на кнопку панели инструментов «Загрузить отрезки» или выбора соответствующего пункта меню «Файл». После этого в рабочее пространство будут добавлены новые отрезки, содержащиеся в текстовом файле.

Добавление отрезков


Добавление нового отрезка в рабочую область производится путём нажатия на кнопку на панели инструментов «Добавить отрезок» или выбрать соответствующий пункт из меню «Отрезок». После этого на экране появится диалоговое окно, содержащее следующие параметры добавления нового отрезка:

  • координаты начала отрезка

  • координаты конца отрезка





Ручное добавление отрезков с помощью мыши


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

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






Генерация указанного количества отрезков в заданном диапазоне


Вместо того, чтобы вручную добавлять каждый отрезок, можно воспользоваться программным способом добавления отрезков. Для этого нужно нажать на кнопку панели инструментов «Сгенерировать отрезков» или выбрать соответствующий пункт меню «Отрезок». После этого на экране появится модальное окно, содержащее следующие параметры добавления отрезков:

  • количество отрезков, которое будет добавлено в рабочую область

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

  • указание того, что при генерации отрезков будет использовано нормальное распределение (если нет, то будет использовано равномерное распределение)





Удаление всех отрезков или заданного отрезка


Удаление всех отрезков, находящихся в рабочей области, производится путём нажатия на кнопку панели инструментов «Удалить все отрезки» или выбора соответствующего пункта меню «Отрезок». После этого все отрезки, находящиеся в рабочей области, будут удалены.

Возможно удалить выделенный отрезок. Это можно сделать путём нажатия на кнопку панели инструментов «Удалить отрезок» или выбора соответствующего пункта меню «Отрезок». После этого текущий отрезок будет удалён из рабочей области.

Сохранение добавленных отрезков в текстовый файл

Для того, чтобы сохранить отрезки в текстовый файла, необходимо вызвать диалог загрузки файла. Это можно сделать путём нажатия на кнопку панели инструментов «Сохранить отрезки» или выбора соответствующего пункта меню «Файл». После этого все координаты всех отрезков, находящихся в рабочей области, будут сохранены в заданном текством файле.

Нахождение попарных пересечений отрезков


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








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


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

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


  • Статус заметающей прямой на данном шаге, который состоит из текущих отрезков (заметающая прямая находится в начале или конце отрезка, или на пересечении отрезков), а также отрезков, которые пересекает заметающая прямая и находящиеся выше или ниже текущих отрезков.
















  • Прямая, на которую спроецировны начала и концы всех отрезков, а также их пересечения. На ней также постепенно появляются пересечения отрезков, как в рабочей области.



Отмена/повтор выполненных операций


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