Невыпуклые отсекающие области - алгоритм Вайлера - Азертона

Для использования рассмотренных алгоритмов отсечения требуются выпуклые отсекающие области. Однако во многих приложениях, например, при удалении невидимых поверхностей, необходимо уметь отсекать и по невыпуклым областям. Этой потребности отвечает более мощный, но и более сложный алгоритм, предложенный Вайлером и Азертоном. Будем называть многоугольник, который отсекается, обрабатываемым многоугольником, а многоугольник, по которому производится отсечение, - отсекающим многоугольником (отсекателем). Новые границы, образуемые в результате отсечения обрабатываемого многоугольника отсекающим, совпадают с участками границ отсекателя. Никаких иных новых границ не возникает. Следовательно, число многоугольников в результате минимально.

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

Литеры

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

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

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