🕗 ✊🏼 🐏 यह निर्धारित करने की समस्या कि कोई बिंदु बहुभुज का है या नहीं 👨🏽‍⚖️ 🚋 🚶

नमस्ते, प्रिय हभ्रवचन!
एंड्रॉइड के लिए एक एप्लिकेशन विकसित करने की प्रक्रिया में, जिसमें ग्राफिक आदिम (अंक, रेखाएं, दीर्घवृत्त, आयताकार, आदि) के साथ उपयोगकर्ता इंटरैक्शन शामिल है, बल्कि एक अप्रिय स्थिति पैदा हुई: उपयोगकर्ता एक मनमाना बहुभुज सेट कर सकता है और इसे निष्क्रिय कर सकता है, हालांकि, भविष्य में इसकी संभावना है। इस बहुभुज को सक्रिय करने के लिए और इसके साथ काम करना जारी रखें (उदाहरण के लिए, इसे किसी अन्य स्थान पर ले जाएं या कोने जोड़ / हटाएं) यह निष्क्रिय वस्तु के लिए आवश्यक है यह निर्धारित करने के लिए कि उपयोगकर्ता ने किसी को छुआ है या नहीं वस्तु, यानी एक बिंदु बहुभुज का है या नहीं, इस सवाल को हल करना आवश्यक था।

इस समस्या को व्यापक रूप से कम्प्यूटेशनल ज्यामिति में जाना जाता है और मैं इस विषय पर अपने शोध के परिणामों पर आपका ध्यान आकर्षित करता हूं।

परिचय

कम्प्यूटेशनल ज्यामिति में, यह आमतौर पर माना जाता है कि बहुभुज सरल है, अर्थात। आत्म-चौराहों के बिना, लेकिन समस्या को जटिल आकार के बहुभुज के लिए भी माना जाता है। यह समस्या अक्सर निम्नलिखित विधियों द्वारा हल की जाती है:

चौराहों की संख्या को ध्यान में रखते हुए विधि द्वारा, जो यह बताता है कि बिंदु P को छोड़ने वाली किरण कितनी बार बहुभुज की सीमाओं को काटती है। यदि चौराहों की संख्या विषम है, तो यह घोषित किया जाता है कि बिंदु बहुभुज के अंदर है, अगर बाहर भी।
क्रांतियों की संख्या के लिए लेखांकन की विधि, जो क्रांतियों की संख्या की गणना करती है, जो बहुभुज की उन्मुख सीमा किसी दिए गए बिंदु P के आसपास होती है । बीजगणितीय टोपोलॉजी में, इस संख्या को घुमावदार संख्या कहा जाता है। एक बिंदु को बहुभुज के बाहर झूठ बोलने पर ही माना जाता है यदि क्रांतियों की संख्या शून्य है, अन्यथा बिंदु बहुभुज के समोच्च के अंदर स्थित है।

यदि बहुभुज सरल है (अर्थात स्वयं-चौराहे नहीं हैं), तो दोनों विधियां सभी बिंदुओं के लिए समान परिणाम देती हैं। हालांकि, यदि बहुभुज का एक जटिल आकार है, तो विधियां कुछ बिंदुओं के लिए अलग-अलग परिणाम दे सकती हैं। उदाहरण के लिए, यदि बहुभुज स्वयं के साथ प्रतिच्छेद करता है, तो चौराहों के लिए लेखांकन की विधि का उपयोग करते समय, चौराहे के क्षेत्र में बिंदुओं को बाहर के बिंदुओं के रूप में परिभाषित किया जाता है। हालांकि, क्रांतियों की संख्या के लिए लेखांकन की विधि का उपयोग करते समय समान बिंदुओं को बहुभुज के अंदर झूठ माना जाएगा (आंकड़ा देखें)।

चौराहों की संख्या और इसके अनुकूलन के लिए लेखांकन की विधि को इस लेख में विस्तार से वर्णित किया गया है, इसलिए आइए समस्या को हल करने के लिए दूसरे एल्गोरिथ्म को देखें।

गति पैमाइश विधि

यह विधि सटीक रूप से यह निर्धारित करती है कि एक बिंदु एक बहुभुज के अंदर स्थित है, यह तुलना करके कि बहुभुज एक बिंदु के आसपास कितनी बार लपेटता है। एक बिंदु केवल एक बहुभुज से संबंधित नहीं है यदि घुमावदार संख्या शून्य है।

एक निरंतर दो-आयामी वक्र C को बिंदु C (u) = C (x (u), y (u) , जहां 0 ≤ u and 1 और C (0) = C (1) द्वारा परिभाषित किया गया है। इसके अलावा, P एक बिंदु है जो वक्र C पर झूठ नहीं बोलता है । हम वेक्टर सी (पी, यू) (बिंदु पी से वक्र सी तक ) की घोषणा करते हैं:

और यूनिट वेक्टर w (P, u) :

।

जो एक निरंतर कार्य करता है W (P): C → S ¹ , वक्र C के बिंदु C (u) को बिंदु w (P, u) पर इकाई चक्र S ¹ = {(x, y) पर मैप करता है । x2 + y2 = 1} । इस मानचित्रण को ध्रुवीय निर्देशांक में दर्शाया जा सकता है:

।

जहां where (u) रेडियन में सकारात्मक वामावर्त घुमाव है।
तब बिंदु P के चारों ओर निरंतर वक्र C की क्रांतियों wn (P, C) की संख्या एक पूर्णांक संख्या के बराबर होती है जब W (P) इकाई C के चारों ओर वक्र C को घुमाता है। यह समरूप वर्ग S ¹ से मेल खाती है और अभिन्न के माध्यम से गणना की जा सकती है:

जब वक्र C लंबवत V ₀ , V ₁ , ..., V _n = V _{0 के} साथ एक बहुभुज होता है, तो अभिन्न कोणों के संकेत योग में कम हो जाता है, जिस पर बहुभुज V _i V _{+ 1 के} प्रत्येक किनारे बिंदु P के विपरीत होता है । इस प्रकार, यदि, _i , PV _i और PV _{i + 1 के} बीच के कोण के बराबर है, तो:

(1)

यह आंकड़ा दिखाता है कि आप कोणों के संकेत योग का रेखांकन कैसे कर सकते हैं।

जाहिर है, सूत्र (1) बहुत प्रभावी नहीं है क्योंकि यह आर्कोसिन के त्रिकोणमितीय फ़ंक्शन का उपयोग करता है, जो कम्प्यूटेशनल रूप से मांग है। इस सूत्र को अधिक प्रभावी के साथ बदलना आवश्यक है।

क्रांतियों के लिए लेखांकन की विधि का अनुकूलन

यूनिट सर्कल पर कोई भी बिंदु Q लें। फिर, जैसा कि वक्र W (P) S ^{1 के} चारों ओर घूमता है, यह बिंदु Q को कई बार पार करता है। अगर हम मानते हैं (+1) जब वक्र Q वामावर्त से गुजरता है, और (-1) जब वक्र दक्षिणावर्त से गुजरता है, तो संचित राशि कुल बार कितनी बार W 1 (P) S ^{1 के} चारों ओर घूमती है और wn (P) के बराबर होती है , C) बिंदु P के चारों ओर निरंतर वक्र C के क्रांतियों की संख्या है । इसके अलावा, यदि हम बिंदु P पर उत्पत्ति के साथ अनंत रे R को लेते हैं और सदिश Q की दिशा में गुजरते हैं, तो किरण R और वक्र C का चौराहा उस बिंदु से मेल खाता है जहां W (P) Q से गुजरता है । एक गणितीय उपकरण विकसित करने के लिए, सकारात्मक और नकारात्मक संक्रमणों के बीच अंतर करना आवश्यक है, जहां सी दाएं से बाएं या बाएं से दाएं दिशाओं में आर को काटता है। यह सामान्य वेक्टर के स्केलर उत्पाद को C और वेक्टर q = Q की दिशा के संकेत द्वारा निर्धारित किया जा सकता है, और बहुभुज के प्रत्येक किनारे के लिए स्केलर उत्पाद की गणना करना आवश्यक है। बिंदु P पर उत्पत्ति के साथ एक क्षैतिज किरण R के लिए, यह जांचने के लिए पर्याप्त है कि क्या रिब का अंत किरण के ऊपर या नीचे है। यदि कोई धार नीचे से ऊपर तक सीधी किरण को पार करती है, तो प्रतिच्छेदन धनात्मक (+1) है, लेकिन यदि यह ऊपर से नीचे की ओर एक धार को पार करता है, तो चौराहा ऋणात्मक (-1) है। चौराहे के निशान का योग क्रांतियों की संख्या w (P, C) देता है ।

इसके अलावा, किनारे और बीम के चौराहे के वास्तविक बिंदु की गणना करने से बचना संभव है। ऐसा करने के लिए, यह निर्धारित करने के लिए पर्याप्त है कि किनारे बीम के साथ किस तरफ झुकते हैं। यदि आरोही किनारा बिंदु P के दाईं ओर किरण को काटता है, तो P , किनारे के बाईं ओर है, क्योंकि त्रिकोण V _i V V _{+ 1} P उन्मुख वामावर्त है। यदि अवरोही छोर किरण को बाईं ओर पार करता है, तो बिंदु P किनारे के दाईं ओर होता है, क्योंकि त्रिकोण V _i V _{I + 1} उन्मुख दक्षिणावर्त है।

बाईं ओर आकृति आरोही किनारे और दाईं ओर अवरोही किनारे को दर्शाती है।

अंत में, मैं कहना चाहूंगा कि गति के लिए लेखांकन की विधि को किसी दिए गए बहुभुज के कोने की पूरी गणना की आवश्यकता है, और यह, मेरी राय में, इसकी खामी है। हालांकि, यह कार्यान्वयन की आसानी और वर्टीकल के लूप एन्यूमरेशन के प्रत्येक पुनरावृत्ति पर गुणन के केवल दो संचालन की उपस्थिति से मुआवजा से अधिक है।

युपीडी:

कार्यान्वयन

संभवतः व्यर्थ में मैंने तुरंत स्रोत कोड संलग्न नहीं किया, इसलिए मैं खुद को सही कर रहा हूं।

स्रोत कोड

public class Polygon { //       private ArrayList<Float> xPoints = new ArrayList<Float>(); private ArrayList<Float> yPoints = new ArrayList<Float>(); //   get  set ,     // ,      public boolean ontains(float _pointX, float _pointY) { float windingNumber = 0; //    float startX = 0; float startY = 0; float endX = 0; float endY = 0; int count = xPoints.size(); for (int i = 1; i <= count; i++) { startX = xPoints.get(i - 1); startY = yPoints.get(i - 1); if (i == count) { endX = xPoints.get(0); endY = yPoints.get(0); } else { endX = xPoints.get(i); endY = yPoints.get(i); } if (startY <= _pointY) { if (endY > _pointY) { //   if (isLeft(startX, startY, endX, endY, _pointX, _pointY) > 0) { //  P     ++windingNumber; } } } else { if (endY <= _pointY) { //   if (isLeft(startX, startY, endX, endY, _pointX, _pointY) < 0) { //  P    --windingNumber; } } } } return (windingNumber != 0); } // start*  end* -  ,  . point* -   P,   private float isLeft(float _startX, float _startY, float _endX, float _endY, float _pointX, float _pointY) { return ((_endX - _startX) * (_pointY - _startY) - (_pointX - _startX) * (_endY - _startY)); } }

प्राथमिक स्रोत: जियोमेट्री एल्गोरिदम डॉट कॉम

यह निर्धारित करने की समस्या कि कोई बिंदु बहुभुज का है या नहीं

परिचय

गति पैमाइश विधि

क्रांतियों के लिए लेखांकन की विधि का अनुकूलन

कार्यान्वयन

More articles: