Для решения этой задачи наиболее широкое распространение получил тест пересечения (crossing) или тест на четность-нечетность (odd-even lest). Пусть р - точка внутри многоугольника. Любой луч, исходящий из точки р в бесконечность, должен пересечь нечетное количество ребер многоугольника. Любой луч, исходящий из точки, расположенной извне многоугольника, и пересекающий его, должен пересечься с четным количеством его ребер прежде, чем уйдет в бесконечность. Следовательно, можно так определить внутреннюю точку многоугольника: провести через эту точку прямую и, взяв в качестве исходной точку на этой прямой, заведомо расположенную извне многоугольника, двигаться вдоль прямой и
nnn^uuTkinaTk ifnnuuprTHn прпргрирний г прппями uunrnvmnuuura пг> Tf>y ППП ПП1СЯ uf> fivnPT
достигнута тестируемая точка. Если в этот момент окажется, что зафиксированное количество пересечений нечетно, тестируемая точка принадлежит внутренней области многоугольника, а в противном случае - внешней. На рис. 7.46 заливкой показаны внутренние области, найденные таким способом в многоугольнике с самопересекающимися ребрами в виде пятиконечной звезды.
Тест четности-нечетности легко встраивается в стандартные алгоритмы отображения, причем в качестве "испытательных" прямых используются строки растра.
Но в некоторых случаях желательно закрасить звезду так, как показано на рис. 7.47. Это можно сделать с помощью теста охватыва-ния (binding test). В этом тесте многоугольник рассматривается как своего рода узел из нескольких петель, завязанный вокруг точки или линии. Идея состоит в том, что в тестируемой точке помещается начало системы полярных координат. Далее рассматривается зондирующий луч, исходящий из этой точки, второй конец которого движется вдоль контура многоугольника (направление движения значения не имеет). В тесте фиксируется количество полных оборотов (Minding number) IV, которое совершит этот луч в процессе обхода
^ ---- 0--------, , -----г - - I-- У I --- ----