Определение принадлежности точки многоугольнику

Заполнение сплошных областей

Заполнение внутренности сплошной области занимает важное место в растровой графике. Большинство задач о заполнении двумерной фигуры относится к одному из двух типов: заполнение внутренности многоугольника, заданного своими вершинами или ребрами, и заполнение внутренности области, ограниченной замкнутым контуром, представленным своей растровой разверткой. Из вышесказанного вытекает ряд подзадач.

Многоугольник- плоская фигура, ограниченная несамопересекающейся замкнутой ломаной линией. Пусть эта ломаная задается набором вершин. Задача состоит в различении внутренних и внешних точек многоугольника. Решение достаточно просто. Выпустим из тестируемой точки произвольный луч и найдем количество его пересечений с границей многоугольника. Если это количество нечетно, точка лежит внутри, в противном случае - вне многоугольника. Прохождение луча через некоторую вершину не рассматриваем, т.к. его можно обойти. Но обход вершин связан с определенными трудностями, требуется много проверок. Проверка пересечения с произвольным лучом также неудобна. Поэтому лучше принять соглашение о направлении пересекающего луча. Приняли горизонтальное направление. Это позволило также исключить из рассмотре-

ения все горизонтальные отрезки многоугольника. Что делать при по-

падании тестирующего луча на вершину? Пересечение не засчитывает-

ся, если вершина является верхней для отрезка и засчитывается в лю-

бом другом случае. Следовательно, для точек максимума пересечение

игнорируется, для точек минимума считается дважды. Для прочих вер-

шин засчитывается единичное пересечение. Зная аналитическое урав-

нение прямой и вышеизложенный алгоритм, можно написать программу.

Дата добавления: 2014-01-11