Количество попадании точки в полигоны в mySQL

[Maksimilian]

на данный момент смогу только на словах.
И так. Город Москва, есть много доставщиков пиццы, или курьерская служба. Они заходят на наш сайт на яндекс карте выбирают географию своей деятельности, рисуют полигон-многоугольник согласно своей территории деятельности.Кто то охватывает юг, кто то центр, кто несколько улиц и тд. Полигон (в смысле вершины полигона) вытягиваем из яндекс карт(в смысле координаты вершин) и сохраняем в Mysql (но в каком формате сохранить?-вопрос!).
Получается у нас база с кучами полигонами.
Далее,если кто то хочет заказать пиццу, заходит на сайт, пишет свой адрес и! (здесь и есть наша основная задача) на основании вводных данных адреса, в базе (лучше в Mysql) делается подборка в какие полигоны входит адрес. На практике-выборка тех компании которые осуществляют доставку именно по этой географической территории. Погрешность естественно нужна минимальная.
Вот и вся задача. Я уверен давно есть готовое решение на данную задачу. но как всегда истина где то рядом но не снами ))
Есть возможность делать запрос на сторонние серверы или на яндекс карты на предмет принадлежности точки полигону,но это только, когда имеется несколько полигонов,а когда достигает счет до 10 тыс, то вопрос отпадает...

[Voltron]

Если речь о принадлежности точки полигону, то вам нужна база с пространственными расширениями (Spatial Extensions). В таких базах есть специальные функции для проверки взаимоотношений двух геометрических объектов. Для MySQL почитать можно здесь, список функций. Получение точки из адреса (т.е. геокодирование) это уже несколько другая задача.

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

[Maksimilian]

Спасибо Voltron!
Все верно, вторую задачу- геокодирование делается через яндекс карты и сохраняется в базе.
НО вчера протестировали в MySQL (Spatial Extensions) и что то погрешности достигали значительных высот. При радиусе 5 км полигона (полигон с 8-ю вершинами , в смысле 8-угольник),при выявлении точки ( адреса ) на принадлежность к полигону погрешность достигала до 350 метров. А при радиусе 50 км, достигала аж до 10 Км. Что и заставил мне запостится на форуме ))
Может у кого то тоже была такая проблема или не правильно настроили mySQL?

[Voltron]

Возможно, у вас просто данные в разных СК?

[Maksimilian]

Возможно, у вас просто данные в разных СК?

нууу данные все берутся от яндекс. Имею ввиду система координат.
где то есть примеры по mysql spartial?

[trir]

В MySQL нет такой функции, там есть только MBR поиск.

1. "OpenGIS Simple Features Specification For SQL" (99-049)
http://www.opengeospatial.org/standards/sfs
Стандарт определяющий работу с пространственными данными в БД
2. Компания MySQL AB «MySQL. Справочник по ячзыку.» Пер. с англ. – М.: Изда-тельский дом «Вильямс», 2005. – 432 с. ISBN 5-8459-0804-3 (рус.)
Глава 7. Пространственные расширения в MySQL
в MySQL 99-049 реализован частично, что именно читай в книжке или в документации
3. Никулин Е. А. «Компьютерная геометрия и алгоритмы машиной графики.» - СПб.; БХВ-Петербург, 2005. - 576.: ил. ISBN 5-94157-264-6
Параграф 1.1.2.8. Тесты ориентации точки относительно полигона

Мой вариант, правда он не работает - где то ошибка

Код: Выделить всё

CREATE DEFINER=`root`@`localhost` FUNCTION `rad_test_ring`(l linestring, q point) RETURNS double
BEGIN
  declare done bool default false;
  declare I, Col int default 1;
  declare s, b, mV, minp double default 0;
  declare W, V, np point;

  set minp = 0.00001;
  set Col = NumPoints(l);
  Repeat
   set np = PointN(l, I);
   set V = Point(X(np) - X(q), Y(np) - Y(q));
   if (abs(X(V)) < minp) and (abs(Y(V)) < minp) then
    Return 0;
    set done = true;
   end if;
   if I <> 1 then
    set b = ang2(W, V);
    if (pi() - abs(b)) < minp then
     Return 0;
     set done = true;
    end if;
   end if;
   set W = Point(X(V), Y(V));
   set s = s + b;
   set I= I + 1;
  Until done or (I > (Col - 1)) End Repeat;
  if Not Done then
   Return abs(b);
   /* Return sign(pi() - abs(s)); */
  end if;
END

Забыл функцию ang2

Код: Выделить всё

FUNCTION `ang1`(x1 double, y1 double, x2 double, y2 double) RETURNS double
BEGIN
  declare d, ang double;
  set d = x1*y2 - x2*y1;
  set ang = acos((x1*x2 + y1*y2)/(sqrt(pow(x1, 2) + pow(y1, 2))*sqrt(pow(x2, 2) + pow(y2, 2))));
  if d = 0 then
   Return ang;
  else
   Return sign(d)*ang;
  end if;
END

Код: Выделить всё

FUNCTION `ang2`(p1 point, p2 point) RETURNS double
BEGIN
  return ang1(X(p1), Y(p1), X(p2), Y(p2));
END

[Voltron]

В MySQL нет такой функции, там есть только MBR поиск.

Возможно, я не прав, но почему-то документация говорит об обратном.

[bim2010]

http://local.wasp.uwa.edu.au/~pbourke/g ... nsidepoly/
http://forums.mysql.com/read.php?23,201913,201913

[trir]

http://dev.mysql.com/doc/refman/5.6/en/ ... jects.html

11.17.5.4.2. Functions That Test Spatial Relationships Between Geometries

Note

MySQL originally implemented these functions such that they used object bounding rectangles and returned the same result as the corresponding MBR-based functions. As of MySQL 5.6.1, corresponding versions are available that use precise object shapes. These versions are named with an ST_ prefix. For example, Contains() uses object bounding rectangles, whereas ST_Contains() uses object shapes.

As of MySQL 5.6.1, there are also ST_ aliases for existing spatial functions that were already exact. For example, ST_IsEmpty() is an alias for IsEmpty()

В версии MySQL 5.6.1 появились функции с префиксом ST_ которые таки да, но для скачивания доступно версия MySQL Community Server 5.5.22, или я чего то не понимаю.