АППРОКСИМАЦИЯ ЛИНИЙ СОПРЯЖЕННЫМИ ДУГАМИ ОКРУЖНОСТЕЙ В ГРАФИЧЕСКИХ СИСТЕМАХ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ

В.В. Мигунов

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

Введение

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

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

Постановка задачи

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

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

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

Порядок величин характеризуется размерами элементов в чертежах - от нескольких миллиметров до нескольких метров.

Алгоритм аппроксимации вправе опираться на непрерывность всех нужных производных исходной кривой в области аппроксимации, которые вычисляются по  его запросу в нужной точке достаточно быстро. Реально требуется, чтобы аппроксимируемая функция была непрерывной вплоть до 2й производной на отрезке аппроксимации, включая концы. Ее кривизна может быть нулевой только в конечном числе точек, прямолинейные фрагменты должны выделяться до аппроксимации.

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

Основные идеи алгоритма аппроксимации

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

В общем случае с помощью одной дуги окружности, выходящей из заданной точки A под заданным углом, можно попасть в другую заданную точку B, но не с заданным в ней углом (на рис.1 углы направлений изображены стрелками). У такой дуги есть 2 степени свободы - радиус и угол раствора, тогда как положение точки B и угол в ней имеют вместе 3 степени свободы. Практической иллюстрацией здесь служит такой пример. Пользователю графического редактора предлагается обвести какой-либо контур серией сопряженных дуг, указывая точки сопряжения. У всей совокупности направлений дуг в точках сопряжения имеется лишь одна степень свободы. Это приводит к "разбалтыванию" дуг около контура, если пользователь указывает точки сопряжения на самом контуре. Задача может оказаться для пользователя неразрешимой без специальных средств корректировки совокупности дуг с сохранением их сопряженности.

Поэтому каждый шаг выполняется с помощью двух сопряженных дуг, которые в совокупности имеют 4 степени свободы вместо необходимых трех. "Лишняя" степень свободы означает, что имеется целое семейство пар сопряженных дуг. На рис.1 точка C - пересечение касательных к кривой в точках A и B, точка Bsim на касательной AC удалена от C на такое же расстояние, как и B. Рассмотрим

семейство O окружностей, проходящих через точку B под заданным углом, с центрами, находящимися с той же стороны от BC, что и точка A.

Рис.1. Реализация одного шага двумя сопряженными дугами

Среди них есть единственная, которая проходит через точку Bsim и касается AC в этой точке. Она имеет радиус Rsim. Нетрудно видеть, что к любой окружности семейства O с радиусом R < Rsim можно провести касательную дугу из точки A, обладающую тремя свойствами: она выходит из A под заданным углом; она касается окружности в точке D, дальнейшее перемещение из которой по окружности в точку B не требует возврата; знак ее кривизны такой же, как у дуги DB. При увеличении радиуса R > Rsim, пока точка A еще не попадает внутрь окружности, касательные дуги обладают теми же свойствами, за исключением кривизны. Знак ее противоположен знаку кривизны дуги DB. В обоих случаях, если координаты центра окружности X, Y заданы в системе координат, связанной с точкой A (ось X идет от A к C), то радиус дуги AD вычисляется явно: RAD = R + 0.5 (X² + (Y - R)²) / (Y - R). При дальнейшем росте радиуса в точке касания возникает возврат направления обхода - явное нарушение требования близости углов ориентации.

В случае, когда точка Bsim лежит левее A, предыдущий анализ проводится с заменой ролей точек A и B, и семейство окружностей O располагается со стороны точки A. Если же Bsim достаточно близка к A, шаг делается с помощью одной, а не двух дуг (если угловое отклонение в точке A допустимо).

Варианты, когда точка C лежит левее точки A, либо поворот от угла в точке A к углу в точке B происходит по часовой стрелке, либо точка B совпадает с C, означают наличие хотя бы одной точки перегиба у аппроксимируемой кривой на этом участке, либо, когда в точке B = C угол совпадает с таковым в точке A, возможен просто прямой участок. Прямолинейные участки исключены из кривой до применения алгоритма, а точки перегиба обслуживаются особым образом. Отметим, что у цепных линий и гипербол этих сложностей нет.

Выбор радиуса R среди допустимых вариантов можно связать с задачей минимизации погрешности при заданном шаге, но это отрицательно скажется на быстродействии. Поэтому в качестве подходящего радиуса берется величина, обратная к среднему значению кривизны на участке приблизительно в половину длины кривой для заданного шага, начиная с точки B (разность углов направлений делится на длину кривой). Если имеется перегиб кривой, берется средняя кривизна от B до точки перегиба. Если сопряжение с непрерывным направлением обхода невозможно, шаг уменьшается. После построения сопряжения оценивается наибольшее отклонение аппроксимации. По его значению принимается решение об увеличении или уменьшении шага. Для коррекции шага dS используется оценка отклонения по нормали, полученная в предположении линейного изменения кривизны по длине линии: E'³ / 96. Здесь E' - максимум модуля производной от кривизны по длине на этом шаге.

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

Свойства и область применения алгоритма

Изложенный подход не дает наилучшей аппроксимации с позиций минимального наибольшего отклонения при заданном числе шагов, либо с позиции минимального числа шагов при заданном наибольшем отклонении. Довольно часто возникающее при его использовании точное (с точностью до машинного представления чисел) совпадение точек и углов в точках A и B избыточно, оно увеличивает число дуг. Достоинствами алгоритма являются простота и быстродействие. Систематические расчеты показали его эффективность. Он успешно применяется в подсистеме проектирования молниезащиты САПР TechnoCAD GlassX. Для цепной линии в прямоугольнике 100х10мм² отклонение не более 0,1мм при угловом отклонении не более 0.001 рад обеспечивается уже 3 сопряженными дугами.

Рис.2. Результаты аппроксимации кривой y = sin (5x) exp(-x) на отрезке [-1; 5]

На рис. 2 приведены результаты аппроксимации более сложной кривой с повышенной точностью. Предельное отклонение задано 0,001 при предельном угловом отклонении 0.001 рад. Потребовалось 83 сопряженных дуги. На рис.2 они показаны через одну с тем, чтобы были видны их длины. По тому, как изменяются длины дуг, видно, что алгоритм адаптивно измельчает шаг в местах с большой кривизной и быстрым ее изменением, увеличивая его на участках с малой и медленно меняющейся кривизной.

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

Особенности численной реализации

При численной реализации аппроксимации главным требованием было обеспечение быстродействия. Тем не менее, оказалось необходимым вести анализ в терминах углов (а не их тангенсов) и координат S вдоль кривой (а не вдоль оси X). При каждой величине шага обрабатывалось 7 точек (нечетное число точек можно увеличить), средняя из которых в целях равномерности расположения на кривой помещалась приблизительно на середине длины S кривой на этом шаге, с использованием косинусов углов в начале и в конце шага. В каждой из точек запоминались координаты X, Y и S, угол G, кривизна E. При обнаружении на одном шаге двух точек перегиба шаг уменьшался. Все повороты и переходы к связанным системам координат реализовывались в терминах ортов векторов и матричных операций. За отклонение по нормали принималась разность между расстоянием от точки (одной из 5 промежуточных) до центра соответствующей дуги и ее радиусом. При слабом изменении кривизны на длине шага окружность, касательная в точке B, проходит близко к точке A. В этом случае анализировались варианты: одна дуга, дуга плюс отрезок прямой, если они обеспечивали условия по угловому отклонению в точке A. Шаг считался подходящим, если наибольшее отклонение составляло от 80% до 100% от заданного. Точка D стыка дуг отыскивалась только тогда, когда уже найден подходящий шаг.

Литература

1. Nina Amenta, Tetsuo Asano, Gill Barequet and others. Application Challenges to Computational Geometry. CG impact task force report (Technical Report TR-521-96). – USA, Princeton University, April 1996. – 57 p.