|
Название: Принадлежность точки многоугольнику Отправлено: Dmi7ry от Ноябрь 02, 2013, 18:48:32 Скрипт проверки вхождения точки в многоугольник (то есть проверяем, внутри многоугольника точка, или снаружи), с учётом попадания на грани и вершины многоугольника.
Здесь реализован метод трассировки луча (http://ru.wikipedia.org/wiki/Задача_о_принадлежности_точки_многоугольнику) (учёт числа пересечений) Сама проверка состоит из последовательного вызова скрипта для каждой пары вершин многоугольника. Скрипт проверяет, пересекает ли луч, направленный вправо, отрезок между указанными вершинами. Если пересекает, то возвращается результат -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 вершин, но на практике их может быть любое количество. Название: Re: Принадлежность точки многоугольнику Отправлено: VladTheCat от Ноябрь 02, 2013, 19:15:42 Dmy7ry, опередил меня :D Причем и по времени и по качеству. Делал я для себя что-то подобное, хотел доработать и выложить. Теперь не буду, так как твой пример гораздо лучше. Спасибо и плюс заслужены (я бы еще денег за это дал, но пока нету :D )
Название: Re: Принадлежность точки многоугольнику Отправлено: Dmi7ry от Ноябрь 02, 2013, 21:09:27 Dmy7ry, опередил меня :D Причем и по времени и по качеству. Делал я для себя что-то подобное, хотел доработать и выложить. Теперь не буду, так как твой пример гораздо лучше. Спасибо и плюс заслужены (я бы еще денег за это дал, но пока нету :D ) Мопед не мой, я просто разместил объяву (с) :)Скрипт под с++ взят с интернета и адаптирован под GM. Хотя признаюсь, до этого я перелопатил кучу статей и несколько гораздо более сложных вариантов кода. Название: Re: Принадлежность точки многоугольнику Отправлено: Fur от Июнь 29, 2014, 20:59:49 Dmi7ry, я не очень понимаю смысл этой строки:
Код: s = sign(ax * by - ay * bx); Да и сам принцип работы скрипта проверки отрезка и луча на пересечение доходит до меня с трудом.Также вот это условие можно сократить до трех проверок: Код: (s == 0 && (ay == 0 || by == 0) && ax * bx <= 0) Код: (s == 0 && ay*by == 0 && ax * bx <= 0) Название: Re: Принадлежность точки многоугольнику Отправлено: Dmi7ry от Июнь 29, 2014, 22:34:19 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; Такой вариант я использую на более взрослых языках (возможно, что что-либо некорректно перевёл сейчас и оно будет не правильно работать в GM)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); Возвращаясь к замене (ay == 0 || by == 0) на ay*by == 0 - тут также есть некоторый риск переполнения при умножении, в результате которого результат получится 0. Для GM это не так актуально (потому что изначально используются достаточно большие диапазоны), а вот для других языков очень даже актуально. Например, при использовании 16 бит для результата, умножение 256*256 даст даст в результате 0. Впрочем, для 32 бит (или даже 64) такая вероятность, хоть и мизерная, тоже есть (в частности, при использовании плавающей арифметики). |