Прямое вычисление координат

Пусть заданы координаты конечных точек отрезка прямой. Найдем координаты точки внутри отрезка (рис. 3.1).

В зависимости от угла наклона прямой выполняется цикл по оси х или по у

(рис. 3.2).

Приведем пример записи этого алгоритма на компьютерном языке програм­мирования С, C++. Для сокращения текста рассмотрим фрагмент программы, где выполняется цикл по оси х, причем х1 <х2:

Здесь все операции выполняются над целыми числами. Двойные скобки не­обходимы для того, чтобы деление выполнялось после умножения. Недос­татки такой программы — в цикле выполняется много лишних операций, присутствуют операции деления и умножения. Это обуславливает малую скорость работы. Относительно лишних операций в цикле. Можно вынести вычисление (у2 - у 1)/(х2 – х1) из цикла, поскольку это значение не изменя­ется. Однако для этого уже необходимо использовать операции с плавающей точкой:

Поскольку мы решили использовать операции с плавающей точкой, то по­пробуем еще уменьшить количество операций в цикле. Если раскрыть скобки в выражении у = у1 + (х – х1)-к; то получим у = у1 + х.к- х1.к. Здесь значе­ние (yl – х1.к) является константой— эти операции также вынесем из тела цикла.

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

Если рассматривать цикл вычисления у, по соответствующим значениям х_i = х1, х1 +1,..., х2 как итеративный процесс, то можно поставить такой вопрос: чему равна разность (у_i+1 — у_i)1 Она равна у_i+1 —у_i = xl + (х_i+1—xl)k-xl- (x_i – х1) к = (х_i+1 – x_i) к = к; поскольку x_i+1 – x_i =1. Разность (y_i+1 – у_i) — константа, равная к. Исходя из этого, можно построить цикл таким образом:

В теле цикла есть только одна операция для вычисления координаты у (если не учитывать <= и ++).

Если сравнивать последний вариант с предыдущим, то последний лучше по быстродействию. Также существенно отличаются способы вычисления коор­динаты у. В последнем варианте значение у вычисляется прибавлением при­ращения к на каждом шаге, и на последнем шаге цикла (когда х=х2) долж­но стать у=у2. Исходя из чисто математических соображений здесь все кор­ректно, однако необходимо учесть, что в компьютере дробные числа представляются в формате с плавающей точкой не точно. Кроме погрешно­сти представления чисел существует ошибка выполнения арифметических операций с плавающей точкой. Ошибка зависит от разрядности мантисс, и самая малая — для long double, но все равно не нулевая. С каждым шагом цикла ошибки накапливаются, и может так произойти, что у не равно у2 на последнем шаге. Это необходимо учитывать при использовании алгоритма.

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

1. Простота, ясность построения алгоритма.

2. Возможность работы с нецелыми значениями координат отрезка.

Недостатки:

1. Использование операций с плавающей точкой или целочисленных опера­ций умножения и деления обуславливает малую скорость. Однако это за­висит от процессора и для различных типов компьютеров может быть по-разному. В современных компьютерах, в которых процессоры используют эффективные способы ускорения (например, конвейер арифметических операций с плавающей точкой), время выполнения целочисленных опера­ций уже не намного меньше. Для старых компьютеров разница могла быть в десятки раз, поэтому и старались разрабатывать алгоритмы только на основе целочисленных операций.

2. При вычислении координат путем добавления приращений может накап­ливаться ошибка вычислений координат.

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