Алгоритм попадения точки в регион.

Собственно сабж.
Тут смысл такой регион задан набором точек (их координат), и задана точка, надо
определить поподает ли точка в этот регион, критерий оптимизности
1. шустрость проверки
2. кол-во кушаемой оперативы на хранение региона.

Пока нашёл только две реализации но обе мне не нравятся:
1.
Смотрел реализации в gtk (gdk) и qt, судя по

Код (Text):

1. typedef struct _RGNDATA { // rgnd  
2.     RGNDATAHEADER rdh;
3.     char          Buffer[1];
4. } RGNDATA;
5.  
6. и
7.  
8. typedef struct _RGNDATAHEADER { // rgndh  
9.     DWORD dwSize;
10.     DWORD iType;
11.     DWORD nCount;
12.     DWORD nRgnSize;
13.     RECT  rcBound;
14. } RGNDATAHEADER;

Win32 реализация особо не отличается.
Метод сводится к разбиению на ректы, и хранению в таком виде, ну а потом поиск
точки в них.
Явный минус такой реализации, в хранений ректов, хотя поиск поидее шустрый.

2.
Есть ещё мат. реализация сводится к методу трассировки луча, храним сами точки, но в поиске прощитываем
ничётак функи.
Мне кажется мат. реализация будет не шустрее но как обосновать не знаю, хотя по
хранению в большинстве случаев выигрывает.

Хотелось бы услышать мнения (если кто занимался данной темой) о том что я упустил.
Может есть ещё какие методы по оптимизней (может плохо искал ), или в этих есть
какие-то хитрые плюсы незря же они узаются (думаю метод ректов не только в
win32, gtk, qt).

 

, IMHO лучше и проще реализуется, к тому же в одной из книг по программированию реальных игр (правда в 3D), приводится именно этот алгоритм, хотя сравнением не занимался. И ещё можно на первом этапе использовать Bounding box, или даже разбивать его на несколько более мелких.

 

"использовать Bounding box" в дополнение к алгоритму 2 это естественно,
а вот "использовать Bounding box, или даже разбивать его на несколько более мелких"
это как раз и есть метод 1.

 

Сорри, подумал про другой метод: разбивку многоугольника на треугольники.

Тут конечно же всё зависит от точности определения. IMHO c помощью ректов как раз это и делается - достигается хорошая скорость при приемлимой точности, благо этот метот позволяет хорошо варьировать эти параметры.

 

Если точек, описывающих регион, не очень много, и сам регион постоянно меняется, то IMHO лучше прощитывать сумму углов с рассматриваемой точки, та все точки, описывающие регион. Если точка внутри региона, то сумма углов 360 градусов. Можно зделать комбинацию с Bounding box.

 

Операции прощёта углов скорее всего будут требовать использование
тригонометрических функов (или нет? ), а это притормозит процесс определения
или приведёт к выбору оптимизации тригоны в ущерб либо памяти, либо камня...
ИМХО от тригонометрии и плавающих точек лучше отказаться.

 

Bohdan200
Если регион представляет собой бублик или нечто вроде подковы и точка приходится на центр дырки этого региона, метод суммы углов покажет, что точка внутри.

 

Да, на каждый угол надо считать 1 арккосинус и 1 квадратный корень. Зато метод 100% точный. А если регион постоянно меняется, то постоянно разбивать его на рэкт-ы быстро не получится... Ну это всего лиш один из классических методов, иногда он себя оправдывает.

 

Ну с бублином не выйдет, ркгион одноконтурный должен быть. А угол берется с учотом знака, т.е. для подковы он будет около 0

 

С учётом последнего предложения оговорюсь что регион может быть "дырявым" и местами впуклым .

 

P_F

Если только специфика задачи не позволит хранить все точки в полярных координатах с центром в точке, которую нужно проверить на предмет попадания в регион. Тогда подсчёт суммы углов сведётся к арифметическому сложению.

 

Есть ещё способ: если точку взять за центр декартовой системы и тянуть из неё прямые по осям (поочередно по всем 4-м векторам), то при нахождении в регионе прямая пересечет границу региона 1 раз. В остальных случаях точка за пределами региона. При нахождении одной из границ, с которой луч из точки пересекается 1 раз, остальные можно не проверять.

 

2cresta:
"если точку взять за центр декартовой системы" тогда надо пересчитать все
координаты вершин, но это не особая проблема, а вот сам способ чё то не особо
понятен (на первый взгляд у меня возникло много вариантов - опровержений, может я
не понял?), нелзя ли по подробней или где мона почитать...

 

cresta
Так покатит только в случае выпуклости региона

 

Что значит "невыпуклый регион" ?
Пример можно?

Если я правильно понял суть "невыпуклого региона", то точка принадлежит региону, если количество пересечений с границами нечетное. Это же справедливо и для традиционных "выпуклых" регионов.
На примере того же тора или подковы все корректно.
Где читал про этот способ не помню, давно уже было... Соответственно и ссылки привести не могу.

 

не знаю как ты опровергал, но идея доказательнтва тривиальна: ведь каждый раз переходя через границу мы меняем состояние "внутри" на состояние "снаружи" или наоборот. и если мы, таким образом, прошли по некоторой непрерывной траектории до точки про которую мы стопудов знаем снаружи она или внутри, то зная количество переходов, точнее чётность/нечётность этого количества, мы можем ответить на вопрос, внутри была исходная точка или нет. Единственное что может сбить -- это если пройти по границе по касательной. Но с этим можно бороться.

 

Касательная - частный случай, который надо заранее оговорить: принадлежит к региону сама граница региона или нет.
А в остальном всё верно: четное - вне региона, нечетное - внутри.

 

Алгоритм простой и самый эффективный (его уже упоминали): из искомой точки проводим луч (именно луч, лучше горизонтальный или вертикальный, чтобы легче было определять точки пересечения луча с отрезками ломаной, ограничивающей твою область) и подсчитываем число пересечений N луча с упомянутыми отрезками ломаной. Если N - нечетное, точка внутри контура, если четное - вне контура. Алгоритм работает и в случае многосвязной области (с дырками).
Я использовал этот алгоритм аж еще на 286 проце - для одной обучающей игры по истории, в которой нужно было определять страну по положению указателя мыши, да еще в динамике по времени. Количество точек в карте мира составляло несколько тысяч. И все достаточно быстро работало, задержек не было.

 

cresta, crypto
Это как раз и есть "метод трассировки луча", ссылку на который привел P_F (правда битую - с матерным хвостом "]мат." ) И случаи касания там тоже рассмотрены

P_F

Нужно различать идею метода и его конкретную реализацию. Если мы берем горизонтальный луч (или вертикальный - без разницы) y=y0, то необходимым условием его пересечения с отрезком (x1,y1,x2,y2) является попадание y0 между y1 и y2. Поэтому отбраковка непересекаемых отрезков производится достаточно быстро (особенно для целочисленных x,y) и только при наличии пересечения\касания производятся доп.вычисления.

А также дополнение к методу 2 при большом числе проверяемых отрезков. Для ускорения поиска потенциально пересекаемых отрезков я юзаю такой способ индексирования (для обработки векторных карт). При использовании горизонтального луча разбиваем область на N горизонтальных полос, пробегаемся по всем отрезкам и записываем в соответсвующие полосы 1) массив или список индексов отрезков, проходящих через эту полосу, 2) габариты (Xmin,Xmax). При проверке попадания точки (x0,y0) выбираем по y0 соответсвующую полосу (если пустая, то на выход), смотрим попадание x0 в (Xmin,Xmax) и затем перебираем соответствующий массив отрезков (индексов) для поиска и подсчета пересечений

 

crypto
А какой длины брать луч?