При разработке одного приложения возникла проблема разграничения доступа для регионов.
Встала проблема определения принадлежности объекта к какому-либо региону России по его GPS координатам
Первое, что мы начали использовать — это API Google,
после того как прописали алиасы к возвращаемым строкам и оплаты доступа (чтобы убрать лимит на запросы) все заработало.
И все было нормально пока гугл не сменил выдачу, например было раньше: Moskovskaya oblast', стало Moscow oblast'
Тут то и было решено не надеяться на гугл, а определять регион своими силами.
Первым, что пришло на ум было: распарсить возвращаемые данные Яндекса (в яндекс-картах версии 1.x был модуль для работы с регионами)
Так и поступили, получилось 2 таблицы.
В одной хранились названия регионов, во второй координаты многоугольника, описывающие регион. (83 — регионы и 8500 — точки )
Был найден алгоритм, для проверки лежит ли точка в многоугольнике. Код был переписан с Си на PHP, разбирать как он работает нет смысла, он просто работает.
$sx,$sy — координаты точки, которую проверяем
$coords — координаты точек выпуклого многоугольника (отсортированы в порядке обхода):
$coords = array(
array('x'=> 66.6634, 'y' => '66.4433'),
и тп.
)
$x, $y — названия ключей в массиве
Пример вызова:
Вернет true, если точка лежит внутри многоугольника.
Теперь просто перебором областей для точки мы получаем ответ.
Всё бы было хорошо, но 8500 точек границ регионов для России — это очень мало. Разброс получится +- 50 км
Чтобы получить точность больше – нам нужно больше точек границ регионов.
Поискав на просторах был найден ресурс, который нам свободно отдает эти точки: gis-lab.info/qa/rusbounds-rosreestr.html (спасибо энтузиастам за вашу работу)
Я почему-то выбрал формат KML (наверное потому, знал чем его открывать — это формат, который поддерживает Google Earth)
Распарсил данные и теперь таблицы получились пожирнее. Таблица с координатами точек границ регионов стала 620 000 точек (34 мб)
Теперь если проверять по старому алгоритму принадлежность точки к многоугольнику региона — на стареньком Core 2 Duo — около 70 секунд.
Не вариант. Алгоритм нужно оптимизировать:
Например, Москва:
Имеем 2,064 точек многоугольника (на самом деле несколько многоугольников):
Но сейчас нам достаточно определить всего-лишь возможность, что точка будет в этой области. Поэтому мы воспользуемся алгоритмом обхода точек и построения выпуклого многоугольника.
algolist.manual.ru
вот его реализация на PHP:
На выходе мы получим массив точек выпуклого многоугольника.
Для Москвы; 19 точек:
На рисунке первым слоем отмечены все 2500 точек Москвы + слой, который мы получили после расчета выпуклого многоугольника.
Сгенерируем для каждого региона такую область.
Теперь доработаем наш алгоритм и будем сначала проверять возможность, что точка может лежать в области – таких областей может быть несколько.
Теперь после прогона всех областей, мы прогоним области, в которых возможно, что лежит точка, алгоритмом описанным выше.
Итого: 0.177сек на слабеньком Core 2 Duo
На самом деле есть еще одна сложность – это анклавы (Москва лежит внутри Московской области, как и Питер, было решено использовать приоритеты, сначала проверяется лежит ли точка в Москве, а потом уже в Московской области)
Встала проблема определения принадлежности объекта к какому-либо региону России по его GPS координатам
Первое, что мы начали использовать — это API Google,
после того как прописали алиасы к возвращаемым строкам и оплаты доступа (чтобы убрать лимит на запросы) все заработало.
И все было нормально пока гугл не сменил выдачу, например было раньше: Moskovskaya oblast', стало Moscow oblast'
Тут то и было решено не надеяться на гугл, а определять регион своими силами.
Первым, что пришло на ум было: распарсить возвращаемые данные Яндекса (в яндекс-картах версии 1.x был модуль для работы с регионами)
Так и поступили, получилось 2 таблицы.
В одной хранились названия регионов, во второй координаты многоугольника, описывающие регион. (83 — регионы и 8500 — точки )
Был найден алгоритм, для проверки лежит ли точка в многоугольнике. Код был переписан с Си на PHP, разбирать как он работает нет смысла, он просто работает.
$sx,$sy — координаты точки, которую проверяем
$coords — координаты точек выпуклого многоугольника (отсортированы в порядке обхода):
$coords = array(
array('x'=> 66.6634, 'y' => '66.4433'),
и тп.
)
$x, $y — названия ключей в массиве
public static function into_poly($sx, $sy, &$coords, $x='x', $y='y')
{
Profiler::start('Detect collision', __FUNCTION__);
$pj=0;
$pk=0;
$wrkx=0;
$yu = 0;
$yl = 0;
$n = count($coords);
for ($pj=0; $pj<$n; $pj++)
{
$yu = $coords[$pj][$y]>$coords[($pj+1)%$n][$y]?$coords[$pj][$y]:$coords[($pj+1)%$n][$y];
$yl = $coords[$pj][$y]<$coords[($pj+1)%$n][$y]?$coords[$pj][$y]:$coords[($pj+1)%$n][$y];
if ($coords[($pj+1)%$n][$y] - $coords[$pj][$y])
$wrkx = $coords[$pj][$x] + ($coords[($pj+1)%$n][$x] - $coords[$pj][$x])*($sy - $coords[$pj][$y])/($coords[($pj+1)%$n][$y] - $coords[$pj][$y]);
else
$wrkx = $coords[$pj][$x];
if ($yu >= $sy)
if ($yl < $sy)
{
if ($sx > $wrkx)
$pk++;
if (abs($sx - $wrkx) < 0.00001) return 1;
}
if ((abs($sy - $yl) < 0.00001) && (abs($yu - $yl) < 0.00001) && (abs(abs($wrkx - $coords[$pj][$x]) + abs($wrkx - $coords[($pj+1)%$n][$x]) - abs($coords[$pj][$x] - $coords[($pj+1)%$n][$x])) < 0.0001))
return 1;
}
if ($pk%2)
return 1;
else
return 0;
}
Пример вызова:
$coords = array(
array('lng'=> 66.6634, 'lat' => '66.4433'),
array('lng'=> 66.6534, 'lat' => '66.4433'),
array('lng'=> 66.6434, 'lat' => '66.4433'),
array('lng'=> 66.6334, 'lat' => '66.4433'),
);
$in = into_poly(66.4455, 66.2255, &$coords, $x='lng', $y='lat');
Вернет true, если точка лежит внутри многоугольника.
Теперь просто перебором областей для точки мы получаем ответ.
Всё бы было хорошо, но 8500 точек границ регионов для России — это очень мало. Разброс получится +- 50 км
Чтобы получить точность больше – нам нужно больше точек границ регионов.
Поискав на просторах был найден ресурс, который нам свободно отдает эти точки: gis-lab.info/qa/rusbounds-rosreestr.html (спасибо энтузиастам за вашу работу)
Я почему-то выбрал формат KML (наверное потому, знал чем его открывать — это формат, который поддерживает Google Earth)
Распарсил данные и теперь таблицы получились пожирнее. Таблица с координатами точек границ регионов стала 620 000 точек (34 мб)
Теперь если проверять по старому алгоритму принадлежность точки к многоугольнику региона — на стареньком Core 2 Duo — около 70 секунд.
Не вариант. Алгоритм нужно оптимизировать:
Например, Москва:
Имеем 2,064 точек многоугольника (на самом деле несколько многоугольников):
Но сейчас нам достаточно определить всего-лишь возможность, что точка будет в этой области. Поэтому мы воспользуемся алгоритмом обхода точек и построения выпуклого многоугольника.
algolist.manual.ru
вот его реализация на PHP:
public static function sort_points($mass, $x = 'x', $y = 'y'){
$current=0;
$next=0;
$p1 = $mass[0];
$mass2 = array();
//определяем первую точку
for ($i=1; $i<count($mass); $i++){
if ( ($p1[$y] > $mass[$i][$y]) || ($p1[$y] == $mass[$i][$y] && $p1[$x] < $mass[$i][$x]) ) {
$p1 = $mass[$i];
$current = $i;
}
}
$n = count($mass);
$p0 = $p1;
$p0[$x]--;
$mass2[] = $mass[$current];
$first = $current;
//начинаем перебор всех элементов
do{
$cmax_not_set=1;
for ( $i=0; $i<$n; $i++ ) {
$key = $i;
//продолжаем если такой элемент уже выбран
if ( $mass[$current][$x] == $mass[$key][$x] && $mass[$current][$y] == $mass[$key][$y] ) continue;
//берем 1ю точку
if ($cmax_not_set) {
$next = $key;
$cmax_not_set=0;
continue;
}
$v1_x = $mass[$key][$x] - $mass[$current][$x];
$v1_y = $mass[$key][$y] - $mass[$current][$y];
$v2_x = $mass[$next][$x] - $mass[$current][$x];
$v2_y = $mass[$next][$y] - $mass[$current][$y];
//магия
$c = $v1_x * $v2_y - $v1_y * $v2_x;
if ( $c > 0 ) $next = $key;
// if ( ($c==0) && ( self::_dist($mass[$current], $mass[$key], $x, $y) > self::_dist($mass[$current], $mass[$next], $x, $y) ) ) $next = $key;
}
//записываем найденный элемент в массив
$mass2[] = $mass[$next];
$current = $next;
}while($first != $next);
return $mass2;
}
На выходе мы получим массив точек выпуклого многоугольника.
Для Москвы; 19 точек:
На рисунке первым слоем отмечены все 2500 точек Москвы + слой, который мы получили после расчета выпуклого многоугольника.
Сгенерируем для каждого региона такую область.
Теперь доработаем наш алгоритм и будем сначала проверять возможность, что точка может лежать в области – таких областей может быть несколько.
Теперь после прогона всех областей, мы прогоним области, в которых возможно, что лежит точка, алгоритмом описанным выше.
Итого: 0.177сек на слабеньком Core 2 Duo
На самом деле есть еще одна сложность – это анклавы (Москва лежит внутри Московской области, как и Питер, было решено использовать приоритеты, сначала проверяется лежит ли точка в Москве, а потом уже в Московской области)
