Глава 10. ПОСТРОЕНИЕ ПО ТОЧКАМ И ВОСПРОИЗВЕДЕНИЕ КРИВЫХ

10.1. ВВЕДЕНИЕ

В разд. 7.6. обсуждались возможности задания кривой на дискретной сетке, а в разд. 9.7 — способы построения кривой по ее остову. При решении одних прикладных задач допустимо представление кривой в виде последовательности пикселов, а при решении других предпочтительно задавать кривую с помощью математического выражения. Последнее может оказаться значительно компактнее дискретных представлений, как свидетельствует сопоставление рис. 9.8 и табл. 9.1. Отыскание кривой, проходящей через заданное множество точек, составляет задачу интерполирования, а отыскание кривой, проходящей вблизи заданного множества точек — задачу аппроксимации. Для обозначения обеих задач будем пользоваться термином построение кривой по точкам. Представляет также интерес задача воспроизведения изображения кривой, заключающаяся в следующем: для заданного математического выражения требуется найти соответствующие пикселы и присвоить им значения, при которых они составляют изображение кривой, описываемой заданным выражением. Эту задачу нельзя считать тривиальной даже при воспроизведении изображений прямых (см. разд. 7.6).

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

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

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

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

Часто решающее значение при построении кривых по точкам приобретает выбор математического описания (функции). Хотя многочлены — первое, что приходит здесь в голову, их применение обычно дает плохое решение. Наибольшее распространение получили методы, предусматривающие использование кусочно-полиномиальных функций различных типов. При решении задач аппроксимации также следует уделять внимание выбору критерия, характеризующего качество приближения. Максимальное расстояние точек от кривой или поверхности представляется вполне разумным критерием, однако часто его использование порождает сложные вычислительные проблемы. В принципе, необходимо достижение некоторого компромисса между тем, что интуитивно кажется желательным, и тем, что оказывается реальным с вычислительной точки зрения.

Начнем с построения кривых по точкам при помощи многочленов. В двух следующих главах будет рассмотрено построение кривых по точкам кусочно-полиномиальными методами. Основное внимание будет сосредоточено на аппроксимации 5-сплайнами и многоугольниками, а в данной главе мы займемся многочленами Безье. Некоторые методы построения поверхностей рассматриваются в гл. 13.

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