12.5.2. ПРОСТОЙ АЛГОРИТМ ПОСТРОЕНИЯ МНОГОУГОЛЬНИКА ПО ТОЧКАМ

Алгоритм 12.2 обеспечивает построение многоугольника по точкам, обрабатывая небольшие группы точек размером так что (Типичные значения лежат в диапазоне 5—10). Алгоритм строит (отслеживает) текущую прямую и новую прямую Если при применении соответствующего теста обнаруживается коллинеарность группы точек (проверка на шаге 4 устанавливает, что в результате использования процедуры COLLINEAR получено истинное значение), то выполняется блок шагов 5—10. На шаге 5 определяется новая прямая представляющая собой прямую, полученную в результате применения процедуры Если первая точка группы назначается точкой склеивания то новая прямая становится текущей прямой (шаг 6), а шаги 7—9 пропускаются. Если отличается от у, то на шаге 8 используется тест на слияние, заключающийся в сравнении прямых (рис. 12.6).

Рис. 126. Иллюстрация к алгоритму 12.2: задание прямых

Если угол между этими двумя прямыми мал, то соответствующие группы точек объединяются и текущая прямая определяется как прямая, соединяющая точки (шаг 8), Малый угол гарантирует близость новой аппроксимирующей прямой к обеим прямым (см. утверждение 12.4). Если угол между прямыми велик, то на шаге 9 алгоритм назначает точку точкой склеивания, задавая . В любом случае алгоритм переходит к обработке новой группы точек, присваивая к значение и увеличивая .

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

Операции, предусмотренные на шагах 8 и 9, можно заменить повторным применением теста на коллинеарность к объединению

сегментов, которые обеспечиваются обращением к процедуре Этот прием увеличивает общий объем вычислений, однако его использование является непосредственной гарантией адекватности теста.

Алгоритм 12.2 относится к описанному в литературе классу алгоритмов, осуществляющих «просмотр вдоль» некоторого множества точек. В каждой точке прямая корректируется и проверяется, не превышает ли ошибка допустимого значения. Если значение ошибки находится в допустимых пределах, алгоритм переходит к обработке следующей экспериментальной точки, в противном случае вводится соответствующая точка склеивания (см. разд. 12.7). Представленный ниже алгоритм относится к типу алгоритмов, осуществляющих «просмотр скачками вдоль» некоторого множества точек. Этот алгоритм предусматривает использование одной прямой для группы точек, что позволяет исключить вычисления, связанные с пересчетом прямой в каждой точке. Однако при возникновении ошибки алгоритм должен вернуться к точке, в которой ошибка принимает максимальное значение. Таким образом, важно выбирать размер группы точек достаточно малым для снижения частоты возвратов. При этот алгоритм сводится к алгоритму «просмотра вдоль». В этом случае тест на коллинеарность всегда адекватен и алгоритм сводится к шагам 8 и 9.

Алгоритм 12.2. Построение многоугольника по точкам

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

(см. скан)