14.4.3. ПОЛОЖЕНИЕ ТОЧКИ ОТНОСИТЕЛЬНО ПРЯМОУГОЛЬНИКА

Если вершины многоугольника упорядочены по часовой стрелке, то точка расположена внутри этого многоугольника, если она всегда находится справа от наблюдателя, совершающего обход сторон многоугольника в соответствии с порядком вершин. Если многоугольник выпуклый, то левая часть неравенства (14.16) имеет отрицательное значение для всех сторон многоугольника. В этом случае решение задачи очевидно.

Если многоугольник не является выпуклым, то найти решение уже не так просто. Можно показать, что любая точка, расположенная внутри невыпуклого многоугольника П, принадлежит выпуклому многоугольнику, образованному сторонами многоугольника П и их продолжениями ([3.7, р. 236-241]). Однако построение таких многоугольников представляет трудную задачу. При решении некоторых прикладных задач они могут задаваться заранее, как это бывает, например, в случаях, когда невыпуклый многоугольник построен как некоторое объединение выпуклых многоугольников. Затрата усилий на построение таких многоугольников может быть оправдана и в том случае, когда требуется проверка расположения относительно определенного невыпуклого многоугольника для значительного числа точек.

Другой способ решения, который применим к любому многоугольнику, предусматривает проведение через точку Р прямой,

Рис. 14.5. Многоугольник, рассматриваемый в примере 14.4. Левые части первого (левого) набора неравенств для точки А с координатами (3.1) имеют значения -6, - 15, - 28 и - 17. Левая часть первого неравенства для точки В с координатами (1,2) имеет значение 3

определение ее пересечения со всеми сторонами многоугольника П и использование критерия четности, описанного в разд. 8.1. Решение ряда систем уравнений более трудоемко, чем определение знаков системы неравенств. Кроме того, необходимо учесть затраты на сортировку точек пересечения. Таким образом, данный метод целесообразно применять лишь для работы с невыпуклыми многоугольниками. (Естественно, ситуация резко меняется, если требуется найти все точки, лежащие внутри многоугольника.)

Пример 14.4. Рассмотрим выпуклый многоугольник с вершинами , и (5, —4) (рис. 14.5). Пусть X и — координаты точки Р. Данный случай определяется следующими неравенствами: