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. Построение многоугольника по точкам
Обозначения. Массивы
содержат координаты экспериментальных точек,
— индекс первой, а к — индекс последней точки группы, проверяемой на коллинеарность.
— число экспериментальных точек, обычно входящих в состав такой группы
— индекс последней вершины многоугольника и
прямая, соединяющая точку
с точкой
— индекс точки, в которой при проведении текста на коллинеарность была зафиксирована максимальная ошибка.
(см. скан)