Точка в многоугольнике

[ANRI]

Даны натуральное число n(n>2) и действительные числа g,h,x1,y1,x2,y2,...,xn,yn.Точки с координатами (xi,yi) (i=1,...,n) являются вершинами произвольного многоугольника,заданными впорядке обхода его по периметру.Определить,лежит ли точка с координатами (g,h) внутри многоугольника.Здесь может оказаться полезной подпрограмма вычисления координат точки пересечения двух прямых.

[WinMain]

В графической библиотеке Windows API есть готовая функция PtInRegion, которая определяет, находится ли заданная точка внутри замкнутого контура (региона).

[Decoder]

Если фигура является выпуклым многоугольником, то можно применить такой метод: для каждого отрезка по периметру многоугольника определять, с какой стороны от него находится данная точка. Если точка находится внутри многоугольника, то при обходе контура по часовой стрелке, она будет всё время находится справа от каждого из отрезков. Если же обходить контур против часовой стрелки, то точка будет всегда слева от всех отрезков. Если фигура может иметь произвольную форму, то её нужно условно разбить на треугольники (т.е. выполнить алгоритм триангуляции) и проверять каждый треугольник. Если точка находится в одном из них, то она находится внутри фигуры.
Чтобы проверить, с какой стороны от отрезка находится точка, можно воспользоваться такой функцией:
Код cpp:
// Положение точки относительно прямой
int CheckPoint(POINT a, POINT b, POINT c)
{
return (b.x-a.x)*(b.y-c.y)-(b.y-a.y)*(b.x-c.x);
}

Если точка B находится на прямой АС, то функция вернёт ноль. Если точка B находится справа от прямой АC, то возвращаемое значение будет больше 0. Если же возвращаемое значение будет отрицательным, то это означает, что точка находится слева от прямой.