Cтраница 3
Важным аргументом при выборе способа математического описания для представления поверхности служит простота решения некоторых важных задач машинной графики, например определения пересечения двух поверхностей. Очевидно, что для этого больше всего подходят плоскости, однако при большом числе конечных участков поверхности, ограниченных замкнутыми кривыми, общий объем вычислений может оказаться значительным. Поверхности, построенные с помощью 5-сплайнов, обладают свойством выпуклой оболочки ( см. утверждение И. Число таких плоскостей может оказаться значительно меньше, чем необходимо при аппроксимации многогранниками, и, следовательно, задачи на пересечение и подобные им легче решать, оперируя этими плоскостями. Дополнительные затраты, связанные с определением точного пересечения, часто очень малы. В самом деле, большинство выпуклых оболочек вообще не пересекаются, и, следовательно, отсутствует необходимость проверять, не пересекаются ли соответствующие поверхности. При составлении карт местности, ориентированных на машинную картографию, очевидно, целесообразно использовать плоскости, поскольку требования к гладкости изображения не очень высоки. [31]
Определение пересечения двух многоугольников путем многократного применения алгоритма 15.3, описанное в предыдущем разделе, не всегда оказывается эффективным. Так, информация относительно расположения вершин многоугольника IIj, полученная за один прогон алгоритма, никак не используется при другом прогоне. Существуют различные способы увеличения эффективности этого процесса и некоторые из них будут здесь изложены. Напомним, что пит обозначают число вершин ( или сторон) многоугольников П2 и Eli соответственно. В наихудшем случае шаги 3 - 8 алгоритма 15.3 выполняются тп раз. Минимальная оценка трудоемкости определения пересечения составляет т п, поскольку все вершины должны быть обработаны, по меньшей мере, один раз. Разница между тп и т п может оказаться значительной, поэтому необходим поиск эффективных процедур. [32]
Однако следует отметить, что, если т - малое число ( скажем, 3 или 4), как это часто бывает в прикладных задачах машинной графики, повышение эффективности процедуры может оказаться невозможным. Экономия, полученная за счет уменьшения числа осмотров одной вершины, может утрачиваться вследствие роста объема учетных операций. Поэтому проводимое в этом разделе обсуждение, относится к задаче определения пересечения двух многочленов лишь в случае, когда у обоих число вершин значительно. Существенное значение для машинной графики имеют алгоритмы, обеспечивающие эффективное определение попарных пересечений для большого числа многоугольников. Именно такая ситуация возникает при решении задачи разделения видимых и невидимых частей воспроизводимого объекта, а также при проверке рисунка схемы, особенно в случае высокой степени интеграции. Здесь также применимы принципы, положенные в основу эффективных алгоритмов определения пересечения многоугольников. [33]