Клуб API Карт

Проверить вхождение тысяч точек в сотню полигонов

Sonic-Sanka
16 апреля 2014, 09:15

Доброго времени уважаемые пользователи!

Подскажите пожалуйста алгоритм решения следующей задачи: имеются записи в бд (id, name lat, long) в размере 12000. На карте имеется порядка 100 полигонов.

Нужно: присвоить каждую точку одному из полигонов (они все граничат друг с другом, но не пересекаются) и записать id этого полигона в эту точку.

Как я вижу решение: запулить все записи в yml файл и запустить цикл нахождения вхождения точки в полигон (берем точку, пробегаем по массиву полигонов до первого вхождения), затем ajax обновляем точку.

Я не гуру в YM возможен ли такой алгоритм? Или есть другой способ? Если первое, то каким образом я могу доставать по одной точке из большучего файла xml?

 

Или воспользоваться функцией из поста http://clubs.ya.ru/mapsapi/replies.xml?item_no=10675 :

function inPolygon (polygon, point) {
var c = 0;

for (var i = 0, points = polygon.getPoints(), j = points.length - 1; i < points.length; j = i++) {
if ((((points[i].getLat() <= point.getLat()) && (point.getLat() < points[j].getLat())) || ((points[j].getLat() <= point.getLat()) && (point.getLat() < points[i].getLat()))) &&
(point.getLng() > (points[j].getLng() - points[i].getLng()) * (point.getLat() - points[i].getLat()) / (points[j].getLat() - points[i].getLat()) + points[i].getLng())
) {
c = !c;
}
}
return c;
}

и использовать ее вне карты?

2 комментария

Здравствуйте, в своем проекте я решал такую задачу средствами бд (но у меня не mysql), проверяя вхождение точки в полигон запросом. http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html

Похожая задача, возможно поможет? (средствами php) - http://stackoverflow.com/questions/5065039/find-point-in-polygon-php

+1

Через spatial или по bbox выбираем из базы полигоны в которые может попасть точка, потом на всякий проверяем и записываем.

Работает со скоростью тысячи точек vs сотни тысяч полигонов / sec