О Охватывание (surrounding). Область R полностью охвачена гранью F (рис. 13.14, г). После большого количества разбиений подобласти исходной области R становятся очень малыми, поэтому данное условие выполняется довольно часто.
О Заключение внутри (contained). Грань F полностью заключена внутри области R (рис. 13.14, г). Эта ситуация имеет место тогда и только тогда, когда все вершины F лежат внутри R.
Грань F считается втянутой в область R, если имеет Место пересечение, охватывание или заключение внутри. Поэтому наше определение «простой» области выглядит так: область R является простой, если не более одной грани пересекается с ней, охвачено ею или заключено в ней.
Поэтому подпрограмма islnvol ved(face) должна определять для грани face с областью R наличие или отсутствие ситуаций пересечения, охватывания ИЛИ заключения внутри. Как это можно сделать наиболее эффективно? Прежде всего подпрограмма выполняет простейший тест: имеет ли место экстент-непересечение грани face с областью R7 Если нет, то лучше всего обойти все вершины полигона face, проверяя каждую вершину и каждое ребро на Пересечение с областью. Поскольку область R - выпуклая, то легко проверить, лежит ли вершина внутри R. (Как именно?) Так же просто проверить, пересекает ли ребро грани одно из горизонтальных или вертикальных ребер области R. (Как?)
Как только в процессе обхода грани face выясняется, что ее вершина находится внутри области R или ее ребро пересекает R, тестирование прекращается и функция islnvol ved() возвращает true. С другой стороны, если все вершины грани находятся вне области R и ни одно ребро с ней не пересекается, то в таком случае грань face или не пересекается с областью R, или заключает ее внутри себя. С целью различить эти две ситуации подпрограмма проверяет, лежит ли какая-нибудь вершина области R внутри данной грани. Это может быть сделано посредством теста на четность, который рассматривался в разделе «Заполнение полигонально-определенных областей».
13.5.2. Другие определения простой области