Главная       Научный калькулятор
Меню

На рисунке изображена очень сложная замкнутая ломаная. Она ограничивает некоторую часть плоскости (многоугольник). Как, отметив на рисунке любую точку, по возможности быстрее определить, принадлежит эта точка многоугольнику или нет?


Решение:

Думаю что можно так: провести из этой точки луч, который не пересекает вершины ломаной. Тогда, если количество пересечений этого луча с ломаной нечетное, то точка лежит внутри многоугольника, ограниченного ломаной. Если количество пересечений луча четное, то точка лежит вне многоугольника.
     Объяснить это можно так: если закрасить внутренность многоугольника черным, а внешнюю область белым, то выполняется следующее:
1) двигаясь по лучу от исходной точки, при каждом пересечении отрезка ломаной, цвет текущей области меняется на противоположный;
2) кроме того, если мы так двигаемся по лучу до тех пор, пока уже не будет пересечений с ломаной (а такое рано или поздно всегда случится, потому что многоугольник - ограниченное множество на плоскости), то в конце мы всегда оказываемся в белой области.
       Таким образом, если мы начинали из белой области (т. Е извне многоугольника), то количество перемен цвета (т.е. Пересечений с отрезками ломаной) будет четным. И если начинали из черной области (изнутри) то, количество перемен цвета будет нечетным.
     Луч обязательно надо проводить не через вершину ломаной, потому что иначе после такого пересечения цвет области может не поменяться. Например, это случится когда угол, через вершину которого проходит луч, лежит целиком по одну сторону от луча.