Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной техники Кафедра вычислительной техники (специальность 220100). учебное пособие
| Вид материала | Учебное пособие |
| 0.6.5 Сравнение алгоритмов двумерного отсечения |
- Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной, 1650.9kb.
- Рабочая программа для специальности: 220400 Программное обеспечение вычислительной, 133.96kb.
- Государственный Технический Университет. Факультет: Автоматики и Вычислительной Техники., 32.46kb.
- Образования Республики Молдова Колледж Микроэлектроники и Вычислительной Техники Кафедра, 113.64kb.
- Постоянное развитие и углубление профессиональных навыков в области информационных, 54.56kb.
- «Программное обеспечение вычислительной техники и автоматизированных систем», 1790.14kb.
- Задачи дисциплины: -изучение основ вычислительной техники; -изучение принципов построения, 37.44kb.
- Лекция №2 «История развития вычислительной техники», 78.1kb.
- Система контроля и анализа технических свойств интегральных элементов и устройств вычислительной, 582.84kb.
- Московский государственный инженерно-физический институт (технический университет), 947.05kb.
0.6.5 Сравнение алгоритмов двумерного отсечения
Во многих работах приводятся качественные соображения по быстродействию различных алгоритмов отсечения. В части работ, например, [32] или [37] приводятся результаты численных экспериментов по измерению скорости. Как правило, авторы работ этими экспериментами подтверждают преимущество своих алгоритмов.
В целом можно отметить несколько методических неточностей проведения таких экспериментов:
неясно насколько одинаково хороши реализации собственного и сравниваемых алгоритмов,
эксперименты ([32] и [37] проводились в среде OC UNIX и нет убедительных свидетельств отсутствия влияния окружения на результаты,
неясно насколько правильно выбиралось число повторений одного отсечения относительно минимального измеряемого кванта времени.
Исходя из этих соображений были проведены численные эксперименты по измерению быстродействия алгоритмов отсечения Коэна-Сазерленда, FC-алгоритма, Лианга-Барски и Кируса-Бека.
Использовались подпрограммы, приведенные в Приложении 7 при отсечении окнами различных размеров при полном разрешении
1000×1000. Процедуры транслировались и исполнялись на 486/DX4/100 в среде на Turbo C под управлением MS DOS 6.22.
Аналогично [37] были подготовлены 5 наборов данных по 1000 отрезков каждый со случайной генерацией конечных точек при следующих ограничениях:
1. Обе конечные точки отрезка внутри окна.
2. Одна конечная точка отрезка в окне, другая вне.
3. Обе конечные точки вне окна но с видимым сегментом.
4. Обе конечные точки вне окна и отрезок невидим.
5. Обе конечные точки генерировались случайно без ограничений.
Сгенерированные данные сохранялись в файлах и считывались в оперативную память перед очередным прогоном теста. Процедуры отсечения использовали данные из оперативной памяти. Для исключения временных затрат, связанных с организацией циклов и запросом координат отрезков, предварительно прогонялся тест с использованием "пустой" процедуры отсечения. Отсечение каждого отрезка проводилось 1000 раз. Измерение времени проводилось перед началом цикла по координатам.
Результаты измерений приведены в таблицах 0.2.3, 0.2.4, 0.2.5, 0.2.6, 0.2.7. Первая колонка таблиц - мои измерения. Вторая колонка таблиц - данные из [37]. Последние проводились на DEC VAX 8600 с ускорителем плавающей арифметики, транслировались C-компилятором без оптимизации и исполнялись под управлением ULTRIX V 1.1 (C).
Таблица 0.2.1: Время (с) для простого приема отрезка.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблица 0.2.2: Время (с) для отрезков с одним концом в окне.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблица 0.2.3: Время (с) для видимых отрезков вне окна.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблица 0.2.4: Время (с) для невидимых отрезков вне окна.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблица 0.2.5: Время (с) для случайных отрезков.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||