GPS座標によるロシアの任意の地域へのオブジェクトの帰属を決定する問題が発生しました
最初に使用を開始したのはGoogle APIです。
返された行のエイリアスを登録し、アクセスの支払いを行った後（要求の制限を削除するため）、すべてが機能しました。
そして、グーグルが発行を変更するまで、すべてが順調でした。たとえば、それは以前のことでした。モスコフスカヤ州 '、モスクワ州になりました'
その後、Googleに依存せず、独自に地域を決定することにしました。
最初に思いついたのは、返されたYandexデータを解析することです（Yandexマップバージョン1.xには、地域を操作するためのモジュールがありました）
彼らはそうしました、それは2つのテーブルを明らかにしました。
1つは領域の名前、2つ目は領域を記述するポリゴンの座標が格納されていました。 （83-地域と8500-ポイント）
ポイントがポリゴン内にあるかどうかをチェックするアルゴリズムが見つかりました。 コードはCからPHPに書き直されました。どのように動作するかを解析することは意味がなく、動作するだけです。
$ sx、$ sy-チェックしているポイントの座標
$ coords-凸多角形の点の座標（トラバーサル順でソート）：
$ coords = 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 kmになります
より正確にするには、より多くの地域境界のポイントが必要です。
広大な範囲を検索すると、これらのポイントを自由に提供してくれるリソースが見つかりました： gis-lab.info/qa/rusbounds-rosreestr.html （あなたの仕事に熱心な人に感謝します）
何らかの理由で、KML形式を選択しました（おそらく、それを開く方法を知っていたためです-これはGoogle Earthをサポートする形式です）
データを解析したところ、テーブルが太くなっています。 リージョンの境界のポイントの座標を持つテーブルは620,000ポイント（34 mb）になりました
古いアルゴリズムに従って、ポイントがリージョンポリゴンに属していることを確認すると-古い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ポイントすべて+凸多角形の計算後に取得したレイヤーをマークしています。
地域ごとにこのような領域を生成します。
ここで、アルゴリズムを改良し、最初にポイントがエリア内にある可能性をチェックします-そのようなエリアがいくつかある可能性があります。
ここで、すべてのエリアを実行した後、上記のアルゴリズムを使用して、ポイントが存在する可能性のあるエリアを追い出します。
合計：弱いCore 2 Duoで0.177秒
実際、もう1つの難点があります-これらは飛び地です（モスクワはモスクワ地域内にあり、ピーターと同様に、優先順位を使用することに決めました。まず、ポイントがモスクワにあるかどうかを確認し、次にモスクワ地域にあります）