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

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

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

1. Обрабатывать стороны многоугольной закрашенной области в направлении против часовой стрелки, пока для одной из границ отсечения не встретится пара “внутренняя-внешняя вершина”; т.е. первая вершина стороны многоугольника находится внутри обрабатываемой области, а вторая - вне ее.

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

3. Для данного участка обрабатываемой закрашенной области сформировать список вершин.

4. Вернуться к точке пересечения-выхода и продолжать обработку сторон многоугольника против часовой стрелки.

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

Если начать с вершины 1 на рис. 6.29, а, то против часовой стрелки следующей обрабатываемой вершиной будет вершина 2. Следовательно, данная сторона существует на верхней границе отсекающего окна. Эта точка V вычисляется, а затем выполняется левый поворот для обработки границ окна против часовой стрелки. Обрабатывая верхнюю границу отсекающего окна, мы не пересекаем сторону многоугольника, пока не дойдем до левой границы окна. Таким образом, эта вершина помечается 1", и мы следуем по левой границе до точки пересечения V". Затем мы следуем по этой стороне против часовой стрелки, возвращаясь к вершине 1. Этим мы завершаем обход границ окна, и список вершин {1,1', 1", 1'"} определяет обработанную область исходной закрашенной области. Обработка сторон многоугольника затем возобновляется в точке 1'. Сторона, определенная точками 2 и 3, выходит из левой границы, но точки 2 и 2' находятся над верхней стороной отсекающего окна, а точки


⇐ вернуться назад | | далее ⇒