Алгоритм нахождения точек внутри выбранной области

Question

[enchikiben]

Доброе время суток.

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



Я только смог до думаться до следующей мысли.

1. Находим центр фигуры по координатам.
lat_center = сумма всех lat поделенная на количество lng_center = сумма всех lng поделенная на количество 2. В цикле строю условие для координат

1.  
2.                 $x_query        =       array();
3.                 // строим условия для x
4.                 foreach($x as $value){
5.                         if (max($value,$x_center)==$value) {
6.                                 $x_query[] = "`t3`.`lat_ya` <= ".$value;                               
7.                         } else {
8.                                 $x_query[] = "`t3`.`lat_ya` >= ".$value;
9.                         }
10.                 }              
11.                
12.                 $y_query        =       array();
13.                 // строим условия для y
14.                 foreach($y as $value){
15.                         if (max($value,$y_center)==$value) {
16.                                 $y_query[] = "`t3`.`lng_ya` <= ".$value;
17.                         } else {
18.                                 $y_query[] = "`t3`.`lng_ya` >= ".$value;
19.                         }
20.                 }
21.  
22.  

3. Далее строю запрос и получаю его 

1.  
2. SELECT *
3. FROM `_perm_houses` as `t3`
4. WHERE
5. (
6. `t3`.`lat_ya` >= 56.234189 AND
7. `t3`.`lat_ya` >= 56.235627 AND
8. `t3`.`lat_ya` <= 56.236925 AND
9. `t3`.`lat_ya` <= 56.240583 AND
10. `t3`.`lat_ya` <= 56.238459 AND
11. `t3`.`lat_ya` >= 56.235348
12. ) AND (
13. `t3`.`lng_ya` <= 58.010264 AND
14. `t3`.`lng_ya` >= 58.007918 AND
15. `t3`.`lng_ya` >= 58.008186 AND
16. `t3`.`lng_ya` >= 58.009228 AND
17. `t3`.`lng_ya` <= 58.011346 AND
18. `t3`.`lng_ya` <= 58.010509
19. ) ;
20.  
21.  

Когда выделенная область прямоугольная и ее стороны параллельны осям координат, скажем так, он находит без проблем, а когда область более точно выделенная возникают проблемы.

Может есть какой алгоритм? Искал ни чего подобного не нашел.

За ранее благодарен.
______________________

Текст подготовлен в Редакторе Блогов от © SoftCoder.ru

Answer 1

[Horse]

Точка x,y находится внутри многоугольника тогда и только тогда, когда луч (x,y) (x+m,y) пересекает многоугольник непарное количество раз. М — очень большое число.

Comments

[MiXei4]

Это если многоугольник выпуклый. Иначе не катит.

[MiXei4]

Или катит? :) Сам загнался, извиняюсь.

[Всеволод]

Катит, катит. Очень крутое правило. Интересно, оно доказуемо?

[VaiMR]

Катит, если разбивать невыпуклый многоугольник на несколько выпуклых.

[MikhailEdoshin]

Смысл использования «большого M» в том, чтобы получить точку, которая заведомо находится вне многоугольника. В конкретной задаче может быть удобным брать, например, (0, 0). Насколько я помню, это работает для любых фигур, т. е. и для невыпуклых многоугольников тоже; Мартин Гарднер даже описывал фокус, основанный на этом принципе.

[Sannis]

Да, это работает для любого, если учесть что в случае использования плавающих чисел вероятность попасть по касательной очень мала.

[Horse]

Алгоритм работает для любого ЗАМКНУТОГО многоугольника. Не нужно разбивать на выпуклые. Проблемой может оказать только то, что луч (x,y) (x+m,y) может на определенном отрезке совпадать с гранью многоугольки.

[Sannis]

Многоугольники по определению замкнуты, а про касания я вроде упомянул, да. Ниже дал хорошую ссылку по этому поводу.

[Sannis]

*VaiMR дал ссылку*

[Horse]

Просто акцент поставил на слове, чтобы кто-то как-то понял в чем суть алгоритма.

[Teivaz]

Этот метод используется в компьютерной графики для определения положения точки (внутри/снаружи). Вполне решаемая задача.

[Horse]

> Этот метод используется в компьютерной графики для определения положения точки (внутри/снаружи). Вполне решаемая задача
Ну конеычно решаемая, и очень легко), но в компьютерной графике такой необходимости не встречал.

Answer 2

[Akr0n]

В студенчестве, для случаев с выпуклыми многоугольниками я выяснял принадлежность точки с помощью равенства площадей самого многоугольника и суммы площадей треугольников, образованных точкой и всеми вершинами многоугольника. Если сумма больше площади (+некая погрешность вычислений), то точка лежит вне многоугольника.

Answer 3

[Ogra]

ru.wikipedia.org/wiki/Алгоритм_точки_в_многоугольнике

Думаю, что подобный алгоритм через SQL не реализовать(Хотя можно попробовать определить функцию), поэтому:
1. «Рисуете» вокруг вашей области ограничивающий прямоугольник со сторонами параллельными координатной сетке. (X_min, Y_min, X_max, Y_max)
2. Выбираете все точки, принадлежащие этому прямоугольнику (простой, быстрый запрос)
3. Проверяете все эти точки скриптом.

Answer 4

[Storyline]

Можно воспользоваться этим простым классом
https://github.com/xopbatgh/sb-polygon-pointer

Достаточно указать координаты полигона и координаты точки

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

Это правило достаточно просто проверить с помощью листа бумаги и карандаша

Comments

[foxy78658]

Класное решение, жаль не понимаю на php.
Как тоже самое на js или как его подключить?

Answer 5

[VaiMR]

Horse, Akr0n Дали два правильных варианта. Еще один.
Обходите вершины по порядку (по часовой стрелке или против) и проверяете с какой стороны от отрезка лежит искомая точка. В результате получите "+", "-" или «0». «0» — точка лежит на отрезке, "+" с одной стороны (зависит как обходить), "-" — с другой. Если получили все плюсы или все минусы, то точка внутри полигона. Вот хорошие статьи на эту тему

Comments

[Sannis]

Только для выпуклого годится :(

[Александр]

тогда стоит решить задачу разбития впуклого многоугольника на выпуклые ;)

Answer 6

[xdenser]

суммируем углы между лучами (x,y)-(x1,y1) ....(x,y)-(xN,yN), где (x1,y1)… (xN,yN) координаты вершин, обходя их в том порядке в котором они связаны. (углы могут быть отрицательными)
если лежит внутри — то будет 2pi

Comments

[xdenser]

конечно, нужно задавать погрешность.

Answer 7

[mgyk]

MYSQL имеет spatial index'ы. Почитайте документацию на эту тему. Если храним в базе POLYGON то вхождение в него точки находится очень быстро.
dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html

Comments

[lashtal]

spatial extensions в mysql — чья-то злая шутка. Он поддерживает только операции над прямоугольниками, ограничивающими объекты (minimum bounding rectangles), а не над самими объектами.
Currently, MySQL does not implement these functions according to the specification. Those that are implemented return the same result as the corresponding MBR-based functions.