Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Графика / Отсечение отрезка /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Сравнение алгоритмов двумерного отсечения - Программирование от RIN.RU
Сравнение алгоритмов двумерного отсечения

Во многих работах приводятся качественные соображения по быстродействию различных алгоритмов отсечения. В части работ, например, [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: Время (с) для простого приема отрезка.

Эксперимент на 486/DX4/100
ОкноCS FC LB CB
Данные из статьи [37]
ОкноCS FC LB CB
0.0 25.311.0113.0377.1
10.025.311.0121.6393.9
20.025.310.7122.3390.6
30.025.411.0122.0395.0
40.025.411.0123.2394.3
50.025.311.2121.5394.6
60.025.010.9121.6394.5
70.025.411.0122.7394.7
80.025.210.2121.4393.3
90.025.211.0124.8394.4
98.025.110.6122.7393.6



Таблица 0.2.2: Время (с) для отрезков с одним концом в окне

Эксперимент на 486/DX4/100
ОкноCS FC LB CB
Данные из статьи [37]
ОкноCS FC LB CB
0.0 124.071.6146.7390.5
10.0110.261.1148.5399.1
20.0107.057.7148.0398.5
30.0104.357.2147.5401.4
40.0101.855.2148.7403.9
50.0100.854.8149.2397.2
60.0100.854.4148.9400.7
70.096.953.6146.9399.5
80.096.351.9148.3399.0
90.095.651.9148.5400.3
98.094.650.6147.1400.7



Таблица 0.2.3: Время (с) для видимых отрезков вне окна

Эксперимент на 486/DX4/100
ОкноCS FC LB CB
Данные из статьи [37]
ОкноCS FC LB CB
0.0 233.0135.4174.8406.6
10.0193.1104.9173.2406.4
20.0183.098.4174.8406.1
30.0177.597.5174.4409.4
40.0177.196.6175.6409.8
50.0173.995.5174.2405.0
60.0168.993.4173.2405.9
70.0168.092.9173.4406.5
80.0166.492.1173.6413.8
90.0164.891.7173.3411.9
98.0163.991.0172.6403.7



Таблица 0.2.4: Время (с) для невидимых отрезков вне окна


Эксперимент на 486/DX4/100
ОкноCS FC LB CB
Данные из статьи [37]
ОкноCS FC LB CB
0.0 46.925.075.9230.4
10.036.918.279.2233.9
20.034.716.879.3237.0
30.031.915.178.8234.6
40.029.113.478.7225.9
50.028.412.678.8229.0
60.026.411.778.0226.1
70.025.511.777.2223.1
80.024.711.276.2222.3
90.025.010.875.9220.7
98.024.610.868.9197.5





Таблица 0.2.5: Время (с) для случайных отрезков

Эксперимент на 486/DX4/100
ОкноCS FC LB CB
Данные из статьи [37]
ОкноCS FC LB CB
0.0 53.727.980.1240.5
10.0104.655.9124.5324.3
20.0100.454.5131.7347.7
30.098.453.0137.7367.7
40.095.150.7139.4375.4
50.087.246.5140.9387.1
60.076.041.1138.7388.7
70.065.134.4135.4393.0
80.052.826.8132.1392.1
90.039.019.0126.8395.3
98.028.012.4123.5393.4



 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь