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

[Dmi7ry]

Скрипт проверки вхождения точки в многоугольник (то есть проверяем, внутри многоугольника точка, или снаружи), с учётом попадания на грани и вершины многоугольника.
Здесь реализован метод трассировки луча (учёт числа пересечений)

Сама проверка состоит из последовательного вызова скрипта для каждой пары вершин многоугольника. Скрипт проверяет, пересекает ли луч, направленный вправо, отрезок между указанными вершинами.
Если пересекает, то возвращается результат -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 вершин, но на практике их может быть любое количество.

[VladTheCat]

Dmy7ry, опередил меня :D Причем и по времени и по качеству. Делал я для себя что-то подобное, хотел доработать и выложить. Теперь не буду, так как твой пример гораздо лучше. Спасибо и плюс заслужены (я бы еще денег за это дал, но пока нету :D )

[Dmi7ry]

Dmy7ry, опередил меня :D Причем и по времени и по качеству. Делал я для себя что-то подобное, хотел доработать и выложить. Теперь не буду, так как твой пример гораздо лучше. Спасибо и плюс заслужены (я бы еще денег за это дал, но пока нету :D )

Мопед не мой, я просто разместил объяву (с) :)
Скрипт под с++ взят с интернета и адаптирован под GM. Хотя признаюсь, до этого я перелопатил кучу статей и несколько гораздо более сложных вариантов кода.

[Fur]

Dmi7ry, я не очень понимаю смысл этой строки:

Код:

s = sign(ax * by - ay * bx);

Да и сам принцип работы скрипта проверки отрезка и луча на пересечение доходит до меня с трудом.

Также вот это условие можно сократить до трех проверок:

Код:

(s == 0 && (ay == 0 || by == 0) && ax * bx <= 0)

Код:

(s == 0 && ay*by == 0 && ax * bx <= 0)

[Dmi7ry]

Dmi7ry, я не очень понимаю смысл этой строки:

Код:

s = sign(ax * by - ay * bx);

Это вычисление, с какой стороны от отрезка лежит точка: выше, ниже или на отрезке. Подробности можете нагуглить (положение точки относительно прямой).

Да и сам принцип работы скрипта проверки отрезка и луча на пересечение доходит до меня с трудом.

Опять же - гугл - можно найти множество вариантов решения и объяснений.

Также вот это условие можно сократить до трех проверок:

Код:

(s == 0 && (ay == 0 || by == 0) && ax * bx <= 0)

Код:

(s == 0 && ay*by == 0 && ax * bx <= 0)

Это чтобы было видно логику проверок (в коде последовательно проверяются все случаи, когда луч пересекает отрезки или вершины отрезков). Кроме того, это ещё и не самый оптимальный вариант алгоритма. Есть и более короткие/быстрые, но читаемость у них гораздо меньше.
Например:

Код:

ax = a.x - m.x;
ay = a.y - m.y;
bx = b.x - m.x;
by = b.y - m.y;

if ((ay ^ by) >= 0)
{
    if ((ax|ay)==0 || (bx|by)==0) return 0;
    if ((ay|by)!=0) return 1;
    return ((ax^bx)>>31) + 1;
}
mp = ax*by - ay*bx;
return (((mp>>32)^ay)>>31)-((((-mp)>>32)^ay)>>31);

Такой вариант я использую на более взрослых языках (возможно, что что-либо некорректно перевёл сейчас и оно будет не правильно работать в GM)
Возвращаясь к замене (ay == 0 || by == 0) на ay*by == 0 - тут также есть некоторый риск переполнения при умножении, в результате которого результат получится 0.
Для GM это не так актуально (потому что изначально используются достаточно большие диапазоны), а вот для других языков очень даже актуально.
Например, при использовании 16 бит для результата, умножение 256*256 даст даст в результате 0. Впрочем, для 32 бит (или даже 64) такая вероятность, хоть и мизерная,
тоже есть (в частности, при использовании плавающей арифметики).