मुझे आश्चर्य है कि बड़ी संख्या में अंक (ओ (1 मिलियन) संग्रह के अंदर या बाहर हैं या नहीं (ओ (10)) बहुभुज के लिए? उत्तरार्द्ध जरूरी नहीं है, लेकिन उनमें छेद नहीं है। फिलहाल मैं अपनी स्थिति को बाउंडिंग बक्से की तुलना करके अंकों की संख्या काट देता हूं, फिर शेष अंक पर this क्रॉसिंग-नंबर विधि का उपयोग करें। वहाँ शायद एक तेजी से विधि है?पॉइंट-इन-पॉलीगॉन बड़ी संख्या में अंक
मान लिया जाये कि आप अक्ष गठबंधन बाउंडिंग बॉक्स है, तो आप अपने एक्स से अंक की सूची को सॉर्ट, समन्वय सकता सूची अंक द्विआधारी खोज और से अंदर या बाउंडिंग बॉक्स के बाहर जाना पर स्थान ढूंढने संभावित रूप से एक बार में बड़ी संख्या में अंक छोड़ दें। वाई समन्वय के लिए दोहराएं। फिर con शेष बिंदुओं के साथ पहले के रूप में tinue। आप बाउंडिंग बॉक्स के भीतर परीक्षण को तेज करने के लिए बहुभुज त्रिभुज प्रदर्शन कर सकते हैं।
सबसे अच्छा प्रदर्शन करेगा जब विमान का क्षेत्र बहुभुज के क्षेत्र से कहीं अधिक है, और बहुभुज उचित रूप से कॉम्पैक्ट हैं (यानी लंबे और पतले नहीं हैं, जो आपको कई झूठी सकारात्मक दे सकते हैं)।
मैं शायद क्वाड्री उत्पन्न करते समय निर्धारित समय के सटीक स्तर पर "बहुभुज के अंदर या बाहर" के किसी भी स्तर पर तेज़ मोटा परीक्षण के लिए Quadtree का उपयोग करता हूं।
प्रत्येक लुकअप ओ (लॉग एन) है, जो जितना तेज़ हो सके उतना तेज़ होगा। क्वाड्री के एक सेल के भीतर स्थित बिंदुओं के लिए जो "किनारे हैं" के रूप में चिह्नित हैं, तो आपको पारंपरिक पॉइंट-इन-पॉलीगॉन परीक्षण करना होगा।
इसके लिए एक कुशल matplotlib फ़ंक्शन है: matplotlib.nxutils.points_inside_poly()। एल्गोरिदम this page पर प्रलेखित है।
उत्तल बहुभुज की एक (संभवतः लंबी) सूची में बहुभुज को प्री-प्रोसेस करने के लिए उपयुक्त होना चाहिए। एक बात के लिए यह आपके बाध्यकारी बक्से को और अधिक प्रभावी बना देगा। –
यदि आप परिणामस्वरूप उत्तल बहुभुज (जैसे सभी घड़ी की दिशा) के किनारों को उन्मुख कर सकते हैं, तो आप एक तेज विधि (विधि 3 [यहां] (http://paulbourke.net/geometry/insidepoly/) का उपयोग कर सकते हैं। – 9000