पॉलीगॉन एल्गोरिदम में पॉइंट कभी-कभी

Question

पर पॉइंट में मैंने स्टैक ओवरव्लो को "पॉलीगॉन पॉइंट" रेट्रैसिंग एल्गोरिदम पर देखा जो मैंने अपने PHP कोड में लागू किया था। अधिकांश समय, यह अच्छी तरह से काम करता है, लेकिन कुछ जटिल मामलों में, जटिल बहुभुज और दुष्चक्र के साथ, यह विफल रहता है और यह कहता है कि पॉलीगॉन में यह बिंदु नहीं है।

उदाहरण के लिए:
आपको here मेरे पॉलीगॉन और पॉइंट क्लासेस मिलेगा: प्वाइंटइन पॉलीगॉन विधि पॉलीगॉन क्लास में है। फ़ाइल के अंत में, दिए गए बहुभुज (Google धरती पर सत्य) के अंदर झूठ बोलने वाले दो बिंदु हैं। दूसरा एक अच्छी तरह से काम करता है, लेकिन पहले एक गाड़ी है :(।

आप आसानी से this KML file का उपयोग कर गूगल अर्थ पर बहुभुज देख सकते हैं।

Answer 1

किया गया है :-) मैं भी कूच गर्त stackoverflows रंज-सुझाव, आपके संदर्भ और this thread सहित। दुर्भाग्यवश कोई भी सुझाव नहीं (कम से कम मैंने कोशिश की) वास्तविक जीवन परिदृश्य के लिए निर्दोष और पर्याप्त थे: जैसे उपयोगकर्ता फ्री पॉलीगॉन को Google मानचित्र पर फ्रीहैंड में प्लॉट करते हैं, "दुष्परिणाम" दाएं बनाम बाएं मुद्दे, नकारात्मक संख्याएं और इसी तरह।

पीआईपी-एल्गोरिदम सभी मामलों में काम करना चाहिए, भले ही बहुभुज में सौ हजार अंक (काउंटी-सीमा, प्रकृति पार्क और इसी तरह) शामिल हों - इससे कोई फर्क नहीं पड़ता कि बहुभुज "पागल" है।

//Point class, storage of lat/long-pairs 
class Point { 
    public $lat; 
    public $long; 
    function Point($lat, $long) { 
     $this->lat = $lat; 
     $this->long = $long; 
    } 
} 

//the Point in Polygon function 
function pointInPolygon($p, $polygon) { 
    //if you operates with (hundred)thousands of points 
    set_time_limit(60); 
    $c = 0; 
    $p1 = $polygon[0]; 
    $n = count($polygon); 

    for ($i=1; $i<=$n; $i++) { 
     $p2 = $polygon[$i % $n]; 
     if ($p->long > min($p1->long, $p2->long) 
      && $p->long <= max($p1->long, $p2->long) 
      && $p->lat <= max($p1->lat, $p2->lat) 
      && $p1->long != $p2->long) { 
       $xinters = ($p->long - $p1->long) * ($p2->lat - $p1->lat)/($p2->long - $p1->long) + $p1->lat; 
       if ($p1->lat == $p2->lat || $p->lat <= $xinters) { 
        $c++; 
       } 
     } 
     $p1 = $p2; 
    } 
    // if the number of edges we passed through is even, then it's not in the poly. 
    return $c%2!=0; 
} 

व्याख्यात्मक परीक्षण:

$polygon = array(
    new Point(1,1), 
    new Point(1,4), 
    new Point(4,4), 
    new Point(4,1) 
); 

function test($lat, $long) { 
    global $polygon; 
    $ll=$lat.','.$long; 
    echo (pointInPolygon(new Point($lat,$long), $polygon)) ? $ll .' is inside polygon<br>' : $ll.' is outside<br>'; 
} 

test(2, 2); 
test(1, 1); 
test(1.5333, 2.3434); 
test(400, -100); 
test(1.01, 1.01); 

आउटपुट:

2,2 is inside polygon 
1,1 is outside 
1.5333,2.3434 is inside polygon 
400,-100 is outside 
1.01,1.01 is inside polygon 

तो मैं एक खगोल-app से कुछ स्रोत के आधार पर एक नई एल्गोरिथ्म का निर्माण समाप्त हो गया,

अब यह एक साल से अधिक है क्योंकि मैंने उपरोक्त एल्गोर पर स्विच किया है कई साइटों पर ithm। "एसओ-एल्गोरिदम" के विपरीत अब तक कोई शिकायत नहीं हुई है। इसे क्रिया here (राष्ट्रीय माइक्रोलॉजिकल डेटाबेस, डैनिश के लिए खेद है) में देखें। आप बहुभुज प्लॉट कर सकते हैं, या "कॉम्यून" (एक काउंटी) का चयन कर सकते हैं - आखिरकार हजारों अंकों के साथ हजारों अंकों के साथ बहुभुज की तुलना करें)। बहुभुज की सीमा पर नहीं -

अद्यतन ध्यान दें, यह एल्गोरिथ्म बहुभुज अंदर लक्षित कर रहा है geodata/अक्षांश, lngs जो बहुत ही सटीक (n'th दशमलव) हो सकता है, इसलिए पर विचार "बहुभुज में" के रूप में । 1,1 को बाहर माना जाता है, क्योंकि यह सीमा पर है। 1.0000000001,1.01 नहीं है।