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

Скрипт проверки вхождения точки в многоугольник (то есть проверяем, внутри многоугольника точка, или снаружи), с учётом попадания на грани и вершины многоугольника. Здесь реализован метод трассировки луча (учёт числа пересечений) Сама проверка состоит из последовательного вызова скрипта для каждой пары вершин многоугольника. Скрипт проверяет, пересекает ли луч, направленный вправо, отрезок между указанными вершинами. Если пересекает, то возвращается результат -1, если нет, то 1. Если же точка лежит на отрезке, то вернётся 0. В скрипт нужно передать шесть координат – координаты X, Y вершин многоугольника и координаты X, Y проверяемой точки. Все вершины многоугольника должны проверяться последовательно. При этом можно перебирать их как по часовой стрелке, так и против часовой стрелки. Вызов скрипта может происходить, например, так:

r1 = check_point(x1, y1, x2, y2, x0, y0)
r2 = check_point(x2, y2, x3, y3, x0, y0)
r3 = check_point(x3, y3, x4, y4, x0, y0)
r4 = check_point(x4, y4, x1, y1, x0, y0)

res = r1*r2*r3*r4

Собственно, скрипт проверки точки:

s_ax = argument0
s_ay = argument1
s_bx = argument2
s_by = argument3
s_mx = argument4
s_my = argument5

ax = s_ax - s_mx
ay = s_ay - s_my
bx = s_bx - s_mx
by = s_by - s_my

s = sign(ax * by - ay * bx)
if (s == 0 && (ay == 0 || by == 0) && ax * bx <= 0)
    return 0
if ((ay < 0) ^ (by < 0))
{
    if (by < 0)
        return s
    return -s
}      
return 1

Тут пример, показывающий работоспособность (все вершины можно перемещать мышкой). Действие происходит в событии draw контроллера. Использован “китайский” код, но исключительно для того, чтобы не усложнять понимание принципа работы. Например, в Студии можно все вершины передавать массивом – таким образом можно реализовать проверку с динамичным числом вершин. В примере используется многоугольник из 5 вершин, но на практике их может быть любое количество.

Leave a Reply

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.