30. Удаление невидимых линий и поверхностей в пространстве изображений. Алгоритм Варнока (разбиение окнами): последовательность действий и основные принципы.

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

1. Все многоугольники являются внешними – окно закрасить цветом фона
2. Многоугольник, связанный с окном является внутренним – закрасить окно цветом фона, растровая развёртка многоугольника
3. Многоугольник, связанный с окном является пересекающим – отсечение по границе окна и п. 2
4. С окном связан один охватывающий многоугольник – закрасить цветом многоугольника
5. С окном связаны внутренние пересекающие мноугольники, и есть хотя бы один охватывающий, расположенный ближе всех остальных к наблюдателю.

Рекомендуемая последовательность

1. Проводится простейший габаритный тест с прямоугольной оболочкой, определяется как можно большее количество пустых окон и окон с единственным внутренним многоугольником
2. Выполнение теста с целью определения окон, пересекаемых единственным многоугольником
3. Тест с целью распознавания внешних и охватывающих многоугольников. Получаем новые пустые окна и окна, охватываемые пустым многоугольником
4. Можно проводить разбиение окна на подокна или проводить ещё тест на обнаружение охватывающего многоугольника, лежащего ближе к наблюдателю