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

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

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

image

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

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
  • Вопрос задан
  • 9477 просмотров
Пригласить эксперта
Ответы на вопрос 7
Horse
@Horse
Точка x,y находится внутри многоугольника тогда и только тогда, когда луч (x,y) (x+m,y) пересекает многоугольник непарное количество раз. М — очень большое число.
Ответ написан
Akr0n
@Akr0n
В студенчестве, для случаев с выпуклыми многоугольниками я выяснял принадлежность точки с помощью равенства площадей самого многоугольника и суммы площадей треугольников, образованных точкой и всеми вершинами многоугольника. Если сумма больше площади (+некая погрешность вычислений), то точка лежит вне многоугольника.
Ответ написан
Ogra
@Ogra
ru.wikipedia.org/wiki/Алгоритм_точки_в_многоугольнике

Думаю, что подобный алгоритм через SQL не реализовать(Хотя можно попробовать определить функцию), поэтому:
1. «Рисуете» вокруг вашей области ограничивающий прямоугольник со сторонами параллельными координатной сетке. (Xmin, Ymin, Xmax, Ymax)
2. Выбираете все точки, принадлежащие этому прямоугольнику (простой, быстрый запрос)
3. Проверяете все эти точки скриптом.
Ответ написан
VaiMR
@VaiMR
Horse, Akr0n Дали два правильных варианта. Еще один.
Обходите вершины по порядку (по часовой стрелке или против) и проверяете с какой стороны от отрезка лежит искомая точка. В результате получите "+", "-" или «0». «0» — точка лежит на отрезке, "+" с одной стороны (зависит как обходить), "-" — с другой. Если получили все плюсы или все минусы, то точка внутри полигона. Вот хорошие статьи на эту тему
Ответ написан
@xdenser
суммируем углы между лучами (x,y)-(x1,y1) ....(x,y)-(xN,yN), где (x1,y1)… (xN,yN) координаты вершин, обходя их в том порядке в котором они связаны. (углы могут быть отрицательными)
если лежит внутри — то будет 2pi
Ответ написан
mgyk
@mgyk
MYSQL имеет spatial index'ы. Почитайте документацию на эту тему. Если храним в базе POLYGON то вхождение в него точки находится очень быстро.
dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html
Ответ написан
@Storyline
Можно воспользоваться этим простым классом
https://github.com/xopbatgh/sb-polygon-pointer

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

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

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

5a6483d0315dd084509986.png
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы