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

Любой алгоритм построения многоугольника по точкам предусматривает разбиение экспериментальных точек на группы, каждая из которых должна затем аппроксимироваться одной из

сторон многоугольника. Первое упрощение, которое можно ввести при решении задачи построения многоугольника по точкам, состоит в проведении прямой между концевыми точками каждой группы вместо поиска оптимальной аппроксимации. Прямая, используемая для аппроксимации точек определяется уравнением

В сущности, это уравнение (10.2), преобразованное посредством умножения на знаменатель и замены на у, 1 на у и 2 на k. Приведем теперь один полезный результат.

Утверждение 12.3. Если точка не принадлежит прямой, определяемой уравнением (12.22), то ее расстояние от этой прямой равно где

Доказательство. Почленное деление уравнения (12.23) на уравнение (12.24) приводит к получению следующего выражения:

(угол определен на рис. 12.3, а). Константу с можно определить в явном виде из уравнений (12.23) и (12.24), однако лучше дать ей более простую интерпретацию. Если — произвольная точка, принадлежащая рассматриваемой прямой, то задав в уравнении и находим, что поскольку точка должна удовлетворять уравнению (12.22). В таком случае эту константу можно задать как и переписать уравнение (12.25) следующим образом:

Обратимся теперь к чертежу, приведенному на рис. Здесь обозначает расстояние точки от рассматриваемой прямой. Очевидно, что . В таком случае расстояние между точкой и прямой действительно равно

Рис. 12.3 Иллюстрация к утверждению 12.3 и его доказательству

Отметим, что знак при указывает, с какой стороны от прямой находится точка.

Простую проверку коллинеарности обеспечивает вычисление левой части уравнения (12.25) для всех промежуточных точек. Можно задать максимальное значение расстояния таким образом, что точки множества не будут считаться коллинеарными, если какая-либо из них отстоит от прямой на расстояние, большее заданного максимума. С практической точки зрения этот прием не всегда оказывается целесообразным. В самом деле, ошибкам, обладающим регулярностью неслучайного характера, можно поставить в соответствие весовые коэффициенты. Допустимой мерой случайности служит число изменений знака величины (рис. 12.4, а). Если вместо абсолютного максимального значения используется значение, нормированное по длине прямой то пороговое значение становится равным

Рис. 12.4. Проверка коллинеарности точек: а — ошибка d измеряется по нормали к прямой в каждом примере ошибка определена в двух точках, в первом знак ошибки не изменяется, во втором — изменяется шесть раз; б — особый случай, максимальная ошибка близка к нулю, однако при рассмотрении точек в качестве некоторого упорядоченного множества они оказываются неколлинеарнымн

Эти тесты на коллинеарность дают неверные результаты в особых случаях типа проиллюстрированного на рис. На нем представлено упорядоченное множество точек и которое является частью большего контура, включающего ряд других точек, также изображенных на этом рисунке. Расстояние от точки до прямой, соединяющей точки Р и очень мало, однако эти три точки не коллинеарны, если рассматривать их как упорядоченную последовательность. Для того чтобы обойти такие особые случаи, следует с длиной прямой сравнивать длину дуги измеренную вдоль соответствующей последовательности точек. Если отношение слишком велико, то рассматриваемые точки не могут быть коллинеарны. Это простой тест и его целесообразно

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

Проведение прямой между крайними точками вместо поиска оптимальной аппроксимации не вызывает серьезных отклонений от оптимального решения, так как максимальное удаление точек от интерполяционной линии не более чем в двое превышает их удаление от оптимальной аппроксимирующей линии (см. задачу 12.3).

Эти положения реализованы в процедуре представленной в виде алгоритма 12.1. Шаг 1а ориентирован на особый случай и может быть опущен, если появление таковых не ожидается. На шаге 8 используются формулы для вычисления нормированной и ненормированной максимальной ошибки

7. Алогоритм можно упростить, исключив из него шаги 6, 7 и все остальные операции с и С. В таком случае проверка, осуществляемая на шаге 9, будет сведена к сравнению Т (максимального расстояния от точки до прямой) и Лучшие результаты, однако, дает использование теста, определенного на плоскости (рис. 12.5). Формальное обоснование данного подхода можно получить, рассматривая проверку коллинеарности как проверку некоторой гипотезы, однако обсуждение этой интерпретации выходит за пределы задач нашей книги и мы предлагаем использовать область допустимых значений, приведенную на рис. 12.5, в качестве некоторой эвристики.

Рис. 12.5. Иллюстрация к Т—С-тес-ту коллинеарности. Область допустимых значений числа изменений знака ошибки С и ошибки Т заштрихована

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

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

Читателю следует иметь в виду, что алгоритм 12.1 должен реализовываться на основе арифметических операций с плавающей

запятой, а не целочисленной арифметики. Неплохо, вероятно, кроме того, заранее разделить значения на вместо того, чтобы в конце делить значение ошибки Т на или

Алгоритм 12.1. Процедура

Обозначения. Массивы определены как общие массивы, к которым процедура имеет доступ; — индекс первой, а к— индекс последней точек группы, проверяемой на колинеарность. Размерность массива а равна трем; он содержит коэффициенты прямой, соединяющей точку уф с точкой — индекс точки, которой соответствует максимальное (по абсолютной величине) значение ошибки, т. е. точка находится на наибольшем расстоянии от прямой, соединяющей первую и последнюю точки. — длина этой прямой. В результате выполнения процедуры определяются массив Используются следующие локальные переменные: Т — максимальная ошибка (абсолютная величина), — ошибка в некоторой точке, С — число изменений знака ошибки.

(см. скан)