GPS निर्देशांक द्वारा क्षेत्र का सटीक निर्धारण

एक अनुप्रयोग विकसित करते समय, क्षेत्रों के लिए अभिगम नियंत्रण की समस्या थी।

यह समस्या रूस के किसी भी क्षेत्र से उसके जीपीएस समन्वय द्वारा किसी वस्तु के संबंधित को निर्धारित करने में उत्पन्न हुई

Google API का उपयोग करने के लिए पहली चीज हमने शुरू की है,
लौटे पंक्तियों के लिए उपनाम दर्ज करने और पहुँच के लिए भुगतान करने (अनुरोधों पर सीमा हटाने के लिए) के बाद, सब कुछ काम किया।
और सब कुछ ठीक था जब तक कि Google ने जारी किया, उदाहरण के लिए, यह पहले था: मोस्कोव्स्काया ओब्लास्ट ', यह मॉस्को ओब्लास्ट बन गया'
तब यह Google पर भरोसा नहीं करने का फैसला किया गया था, लेकिन इस क्षेत्र को अपने दम पर निर्धारित करने के लिए।




पहली बात जो मन में आई वह थी: लौटे यैंडेक्स डेटा को पार्स करना (यांडेक्स मैप्स संस्करण 1.x में क्षेत्रों के साथ काम करने के लिए एक मॉड्यूल था)
तो उन्होंने किया, यह 2 टेबल निकला।
एक में, क्षेत्रों के नाम संग्रहीत किए गए थे, दूसरे में, उस क्षेत्र का वर्णन करने वाले बहुभुज के निर्देशांक। (83 - क्षेत्र और 8500 - अंक)

एक एल्गोरिथ्म यह जांचने के लिए पाया गया कि कोई बिंदु बहुभुज में है या नहीं। कोड को C से PHP में फिर से लिखा गया है, यह पार्स करने का कोई मतलब नहीं है कि यह कैसे काम करता है, यह सिर्फ काम करता है।

$ sx, $ sy - उस बिंदु के निर्देशांक जो हम जाँच रहे हैं
$ कोर्ड्स - एक उत्तल बहुभुज के बिंदुओं के निर्देशांक (ट्रैवर्सल ऑर्डर में क्रमबद्ध):
$ कोर्ड्स = सरणी (
सरणी ('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');


यदि बिंदु बहुभुज के अंदर स्थित है, तो सही है।

अब केवल उन बिंदुओं के लिए क्षेत्रों की गणना करके हम उत्तर प्राप्त करते हैं।

सब कुछ ठीक होगा, लेकिन रूस के लिए क्षेत्रीय सीमाओं के 8500 अंक बहुत कम हैं। प्रसार + - 50 किमी होगा

अधिक सटीकता प्राप्त करने के लिए, हमें क्षेत्रीय सीमाओं के अधिक बिंदुओं की आवश्यकता है।
विशाल विस्तार की खोज करते हुए, एक संसाधन पाया गया कि ये अंक हमें स्वतंत्र रूप से देते हैं: gis-lab.info/qa/rusbounds-rosreestr.html (आपके काम के लिए उत्साही लोगों के लिए धन्यवाद)
किसी कारण से, मैंने KML प्रारूप चुना (शायद इसलिए कि मैं जानता था कि इसे कैसे खोला जाए - यह एक प्रारूप है जो Google धरती का समर्थन करता है)
मैंने डेटा को पार्स किया और अब टेबल्स फेट रहे हैं। क्षेत्रों की सीमाओं के बिंदुओं के निर्देशांक वाली एक तालिका 620,000 अंक (34 mb) बन गई है

अब यदि आप पुराने एल्गोरिदम के अनुसार जांचते हैं कि बिंदु क्षेत्र बहुभुज से संबंधित है - पुराने कोर 2 डुओ पर - लगभग 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 बिंदुओं को चिन्हित करती है और जो परत हम उत्तल बहुभुज की गणना के बाद प्राप्त करते हैं।
हम प्रत्येक क्षेत्र के लिए ऐसा क्षेत्र उत्पन्न करेंगे।

अब हम अपने एल्गोरिथ्म को परिष्कृत करेंगे और पहले इस संभावना की जांच करेंगे कि बिंदु क्षेत्र में झूठ हो सकता है - ऐसे कई क्षेत्र हो सकते हैं।
अब, सभी क्षेत्रों के माध्यम से चलने के बाद, हम उन क्षेत्रों को बाहर निकाल देंगे जिनमें यह संभव है कि एक बिंदु झूठ है, जो ऊपर वर्णित एल्गोरिथ्म का उपयोग कर रहा है।
कुल: कमजोर कोर 2 डुओ पर 0.177 वर्ग

वास्तव में, एक और कठिनाई है - ये एन्क्लेव हैं (मास्को मॉस्को क्षेत्र के अंदर स्थित है, पीटर की तरह, यह प्राथमिकताओं का उपयोग करने का निर्णय लिया गया था, पहले यह जांचता है कि बिंदु मॉस्को में स्थित है, और फिर मॉस्को क्षेत्र में)