Во многих работах приводятся качественные соображения по быстродействию различных алгоритмов отсечения. В части работ, например, [32] или [37] приводятся результаты численных экспериментов по измерению скорости. Как правило, авторы работ этими экспериментами подтверждают преимущество своих алгоритмов.
В целом можно отметить несколько методических неточностей проведения таких экспериментов:
неясно насколько одинаково хороши реализации собственного и сравниваемых алгоритмов,
эксперименты ([32] и [37] проводились в среде OC UNIX и нет убедительных свидетельств отсутствия влияния окружения на результаты,
неясно насколько правильно выбиралось число повторений одного отсечения относительно минимального измеряемого кванта времени.
Исходя из этих соображений были проведены численные эксперименты по измерению быстродействия алгоритмов отсечения Коэна-Сазерленда, FC-алгоритма, Лианга-Барски и Кируса-Бека.
Использовались подпрограммы, приведенные в Приложении 7 при отсечении окнами различных размеров при полном разрешении 1000×1000. Процедуры транслировались и исполнялись на 486/DX4/100 в среде на Turbo C под управлением MS DOS 6.22.
Аналогично [37] были подготовлены 5 наборов данных по 1000 отрезков каждый со случайной генерацией конечных точек при следующих ограничениях:
Обе конечные точки отрезка внутри окна.
Одна конечная точка отрезка в окне, другая вне.
Обе конечные точки вне окна но с видимым сегментом.
Обе конечные точки вне окна и отрезок невидим.
Обе конечные точки генерировались случайно без ограничений.
Сгенерированные данные сохранялись в файлах и считывались в оперативную память перед очередным прогоном теста. Процедуры отсечения использовали данные из оперативной памяти. Для исключения временных затрат, связанных с организацией циклов и запросом координат отрезков, предварительно прогонялся тест с использованием "пустой" процедуры отсечения. Отсечение каждого отрезка проводилось 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: Время (с) для простого приема отрезка.
Эксперимент на 486/DX4/100 | Окно | CS | FC | LB | CB | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| Данные из статьи [37] | Окно | CS | FC | LB | CB | 0.0 | 25.3 | 11.0 | 113.0 | 377.1 | 10.0 | 25.3 | 11.0 | 121.6 | 393.9 | 20.0 | 25.3 | 10.7 | 122.3 | 390.6 | 30.0 | 25.4 | 11.0 | 122.0 | 395.0 | 40.0 | 25.4 | 11.0 | 123.2 | 394.3 | 50.0 | 25.3 | 11.2 | 121.5 | 394.6 | 60.0 | 25.0 | 10.9 | 121.6 | 394.5 | 70.0 | 25.4 | 11.0 | 122.7 | 394.7 | 80.0 | 25.2 | 10.2 | 121.4 | 393.3 | 90.0 | 25.2 | 11.0 | 124.8 | 394.4 | 98.0 | 25.1 | 10.6 | 122.7 | 393.6 |
|
Таблица 0.2.2: Время (с) для отрезков с одним концом в окне
Эксперимент на 486/DX4/100 | Окно | CS | FC | LB | CB | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| Данные из статьи [37] | Окно | CS | FC | LB | CB | 0.0 | 124.0 | 71.6 | 146.7 | 390.5 | 10.0 | 110.2 | 61.1 | 148.5 | 399.1 | 20.0 | 107.0 | 57.7 | 148.0 | 398.5 | 30.0 | 104.3 | 57.2 | 147.5 | 401.4 | 40.0 | 101.8 | 55.2 | 148.7 | 403.9 | 50.0 | 100.8 | 54.8 | 149.2 | 397.2 | 60.0 | 100.8 | 54.4 | 148.9 | 400.7 | 70.0 | 96.9 | 53.6 | 146.9 | 399.5 | 80.0 | 96.3 | 51.9 | 148.3 | 399.0 | 90.0 | 95.6 | 51.9 | 148.5 | 400.3 | 98.0 | 94.6 | 50.6 | 147.1 | 400.7 |
|
Таблица 0.2.3: Время (с) для видимых отрезков вне окна
Эксперимент на 486/DX4/100 | Окно | CS | FC | LB | CB | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| Данные из статьи [37] | Окно | CS | FC | LB | CB | 0.0 | 233.0 | 135.4 | 174.8 | 406.6 | 10.0 | 193.1 | 104.9 | 173.2 | 406.4 | 20.0 | 183.0 | 98.4 | 174.8 | 406.1 | 30.0 | 177.5 | 97.5 | 174.4 | 409.4 | 40.0 | 177.1 | 96.6 | 175.6 | 409.8 | 50.0 | 173.9 | 95.5 | 174.2 | 405.0 | 60.0 | 168.9 | 93.4 | 173.2 | 405.9 | 70.0 | 168.0 | 92.9 | 173.4 | 406.5 | 80.0 | 166.4 | 92.1 | 173.6 | 413.8 | 90.0 | 164.8 | 91.7 | 173.3 | 411.9 | 98.0 | 163.9 | 91.0 | 172.6 | 403.7 |
|
Таблица 0.2.4: Время (с) для невидимых отрезков вне окна
Эксперимент на 486/DX4/100 | Окно | CS | FC | LB | CB | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| Данные из статьи [37] | Окно | CS | FC | LB | CB | 0.0 | 46.9 | 25.0 | 75.9 | 230.4 | 10.0 | 36.9 | 18.2 | 79.2 | 233.9 | 20.0 | 34.7 | 16.8 | 79.3 | 237.0 | 30.0 | 31.9 | 15.1 | 78.8 | 234.6 | 40.0 | 29.1 | 13.4 | 78.7 | 225.9 | 50.0 | 28.4 | 12.6 | 78.8 | 229.0 | 60.0 | 26.4 | 11.7 | 78.0 | 226.1 | 70.0 | 25.5 | 11.7 | 77.2 | 223.1 | 80.0 | 24.7 | 11.2 | 76.2 | 222.3 | 90.0 | 25.0 | 10.8 | 75.9 | 220.7 | 98.0 | 24.6 | 10.8 | 68.9 | 197.5 |
|
Таблица 0.2.5: Время (с) для случайных отрезков
Эксперимент на 486/DX4/100 | Окно | CS | FC | LB | CB | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| Данные из статьи [37] | Окно | CS | FC | LB | CB | 0.0 | 53.7 | 27.9 | 80.1 | 240.5 | 10.0 | 104.6 | 55.9 | 124.5 | 324.3 | 20.0 | 100.4 | 54.5 | 131.7 | 347.7 | 30.0 | 98.4 | 53.0 | 137.7 | 367.7 | 40.0 | 95.1 | 50.7 | 139.4 | 375.4 | 50.0 | 87.2 | 46.5 | 140.9 | 387.1 | 60.0 | 76.0 | 41.1 | 138.7 | 388.7 | 70.0 | 65.1 | 34.4 | 135.4 | 393.0 | 80.0 | 52.8 | 26.8 | 132.1 | 392.1 | 90.0 | 39.0 | 19.0 | 126.8 | 395.3 | 98.0 | 28.0 | 12.4 | 123.5 | 393.4 |
|
8 8 8
| |