मित्रों को नमस्कार।

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



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

इसलिए, हमें हाथ से खींची गई आकृति के साथ समानता का प्रतिशत निर्धारित करने की आवश्यकता है:

बुनियादी ज्यामिति

एल्गोरिथ्म को लागू करने के लिए, हमें विमान पर बुनियादी ज्यामिति सूत्र चाहिए।

[F1] खंड लंबाई:

len = sqrt((x2-x1)^2 + (y2-y1)^2); 

[F2] दिशा वैक्टर और सामान्य रेखा:

 //     directX = x2-x1; directY = y2-y1; //      normaleX = -directY; normaleY = directX; 

[F3] विमान में एक रेखा का समीकरण Ax + By + C = 0

रेखा के समीकरण से गुणांक A, B और C प्राप्त करने के लिए, इस रेखा के दो बिंदुओं को जानकर आप यह कर सकते हैं:

 A = -normaleX; B = -normaleY; C = -A*x1 - B*y1; 

[F4] बिंदु की स्थिति अपेक्षाकृत सीधी है।

हम मान लेते हैं कि बिंदु रेखा से ऊपर है यदि सूत्र + + + C मानों को प्रतिस्थापित करते समय शून्य से अधिक मान देता है। यदि मान शून्य है, तो बिंदु इस रेखा के अंतर्गत आता है। कल्पना करें कि रेखा का पहला बिंदु स्क्रीन के बाईं ओर स्थित है, और दूसरा दाईं ओर है, और इसलिए, इस पंक्ति के ऊपर (स्क्रीन के शीर्ष पर) झूठ बोलने वाले सभी बिंदु समीकरण में एक पंक्ति को प्रतिस्थापित करते समय एक सकारात्मक मान देंगे। यह समझना बहुत महत्वपूर्ण है कि पहला (प्रारंभिक) बिंदु कहां है, और दूसरा (अंतिम) बिंदु कहां है: यदि आपके पास अंक हैं p = {x, y} और q = {x, y} , और आप सूत्र का उपयोग करके दिशा (और सामान्य वेक्टर) की गणना करते हैं। :

 directX = qx-px; directY = qy-py; 

, फिर पहला (प्रारंभिक) बिंदु p होगा, और दूसरा (अंतिम) बिंदु q होगा।

[F5] एक खंड के एक बिंदु को मानते हुए

यदि यह इन बिंदुओं से होकर गुजरने वाली रेखा पर स्थित है, और यदि यह खंड के दो बिंदुओं के बीच स्थित है, तो बिंदु o खंड खंड pq से संबंधित है। सदस्यता एल्गोरिथ्म इस प्रकार है:

- निर्धारित करें कि बिंदु रेखा पर स्थित है ( [F4] )
- हम सेगमेंट ( [F4] ) सेशन और oq की लंबाई पाते हैं, अगर इनमें से कम से कम एक वैल्यू सेगमेंट pq की लंबाई से अधिक है, तो पॉइंट o सेगमेंट pq के अंदर नहीं है।

[एफ ६] असीम रूप से लंबी लाइनों का चौराहा बिंदु

 // ,     l1 = {p1,p2}; l2 = {p1,p2}; // d = (l2.p2.y-l2.p1.y)*(l1.p2.x-l1.p1._x) - (l2.p2.x-l2.p1.x)*(l1.p2.y-l1.p1.y); a = (l2.p2.x-l2.p1.x)*(l1.p1.y-l2.p1._y) - (l2.p2.y-l2.p1.y)*(l1.p1.x-l2.p1.x) //   x0 = l1.p1.x + a*(l1.p2.x-l1.p1.x)/d y0 = l1.p1.y + a*(l1.p2.y-l1.p1.y)/d 

ध्यान रखें कि यदि d = 0 है , तो रेखाएं समानांतर हैं।

[F7] दो खंडों का प्रतिच्छेदन बिंदु। एक अनंत रेखा और एक रेखा खंड का प्रतिच्छेदन बिंदु।

यदि दो अंत खंडों या एक अनंत रेखा और अंत खंड की जांच की जाती है, तो आपको पहले दो अनंत रेखाओं ( [F6] ) के प्रतिच्छेदन बिंदु को निर्धारित करना चाहिए और जांचना चाहिए कि यह बिंदु सभी शामिल खंडों ( [F5] ) से संबंधित है या नहीं।

त्रिभुज - सब कुछ के आधार के रूप में एक प्राथमिक बहुभुज

जैसा कि आप जानते हैं, एक त्रिभुज सबसे सरल बहुभुज है। बहुभुज की कई गणना त्रिकोण के साथ जुड़ी हुई हैं, इसलिए मैं उनके साथ काम करने के लिए कई सूत्र दूंगा।

[F8] त्रिकोण का ज्यामितीय केंद्र

त्रिकोण का केंद्र (या सेंट्रोइड ) त्रिकोण के बिंदुओं के निर्देशांक का अंकगणितीय माध्य है। यह सूत्र द्वारा निर्धारित किया जाता है:

 x0 = (a.x+b.x+cx)/3; y0 = (a.y+b.y+cy)/3; 

[F9] त्रिभुज का क्षेत्रफल

त्रिभुज के बिंदुओं के केवल निर्देशांक को जानते हुए, आप इन पक्षों को कोण के साइन द्वारा दो पक्षों की लंबाई को गुणा करके इसका क्षेत्रफल निर्धारित कर सकते हैं।

[F10] विमान पर बहुभुज

विमान में बहुभुज P को वर्टिकल के सेट द्वारा परिभाषित किया गया है: v1, v2, ..., vn , जहां n वर्टिस की संख्या है। बहुभुज में किनारे होते हैं जो आसन्न कोने को जोड़कर बनते हैं: e1 = {v1, v2}, e2 = {v2, v3}, ..., en = {vn, v1} ।

[F11] बहुभुज बाउंडिंग बॉक्स

बाउंडिंग बॉक्स सीमा = {x, y, चौड़ाई, ऊंचाई} ऑब्जेक्ट द्वारा परिभाषित किया गया है, जहां x और y बहुभुज के कोने के न्यूनतम निर्देशांक हैं, और चौड़ाई और ऊंचाई के बीच के अधिकतम और न्यूनतम निर्देशांक के बीच अंतर हैं।

[F12] बहुभुज केंद्र

केंद्र का आम तौर पर अलग-अलग अस्तित्व होता है, उदाहरण के लिए, एक बिंदु प्रणाली का केंद्र या क्षेत्र के ऊपर द्रव्यमान का केंद्र ... हम द्रव्यमान के केंद्र का उपयोग करेंगे, जिसकी गणना निम्नलिखित एल्गोरिथम द्वारा की जाती है। आपको बहुभुज को त्रिभुजों में तोड़ने की आवश्यकता है, चाहे जो भी हो, आप केवल क्रम में कोने का उपयोग कर सकते हैं। हम त्रिभुजों और उनके क्षेत्रों के केंद्रों के उत्पादों का योग पाते हैं और इस राशि को बहुभुज के कुल क्षेत्रफल से विभाजित करते हैं। बहुभुज क्षेत्र की गणना उसके त्रिभुजों के क्षेत्रों के योग के रूप में की जाती है।

 //    var triangles:Array = ... ; //   var centerX:Number = 0; var centerY:Number = 0; //   var polygonSquare:Number = 0; // for (i=0; i<triangles.length; i++) { var triangle = triangles[i]; centerX += triangle.center.x*triangle.square; centerY += triangle.center.y*triangle.square; polygonSquare += triangle.square; } centerX /= polygonSquare; centerY /= polygonSquare; 

[F13] बहुभुज के सापेक्ष बिंदु की स्थिति

इस बिंदु पर बहुभुज के अंदर एक बिंदु स्थित होता है, जो कि इस बिंदु को "नीचे" है , जब सभी किनारों के संबंध में घड़ी की दिशा में। रेखा के सापेक्ष बिंदु की स्थिति को सूत्र F4 द्वारा निर्धारित किया जा सकता है। यदि बिंदु सभी किनारों के संबंध में "ऊपर" है , तो यह बहुभुज के बाहर स्थित है

[F14] एक अनंत रेखा और एक बहुभुज का अंतर

बहुभुज पी के साथ लाइन एल के चौराहे के बिंदुओं को निर्धारित करने के लिए, सभी खंडों e1, e2 ... सूत्र [F7] का उपयोग करके लाइन l के प्रतिच्छेदन के सभी बिंदुओं को खोजना आवश्यक है।

आकृतियों की समानता का निर्धारण

तो हमारे पास प्रवेश द्वार पर क्या है? हमारे पास मूल ड्राइंग है - टेम्प्लेट बहुभुज को वर्टिकल v1, v2, ..., vn के सेट द्वारा परिभाषित किया गया है, और ड्रॉ बहुभुज है जिसमें ड्रॉइंग प्रोसेस के दौरान प्राप्त बिंदुओं के एक सेट से बना है। इससे पहले कि आप उनकी तुलना करना शुरू करें, ड्रा बहुभुज को टेम्पलेट बहुभुज के लिए "कम" होना चाहिए। यानी यह संपीड़न (स्केल) और विस्थापन (ट्रांसलेशन) के परिवर्तन को लागू करने के लिए आवश्यक है ताकि बहुभुज के केंद्र मेल खाते हैं और ड्रॉ बहुभुज के बाउंडिंग बॉक्स के अधिकतम समान आयाम (सीमा और बैंडविड्थ) हैं। टेम्पलेट के साथ:



बहुभुज कमी एल्गोरिथ्म:

 //   var template = ... ; //   var draw = ... ; //    var scaleW:Number = template.bounds.width/draw.bounds.width; //    var scaleH:Number = template.bounds.height/draw.bounds.height; //    var scale:Number = (scaleW+scaleH)/2; //    draw.matrixScale(scale); // //   X var dx:Number = draw.centerWeight.x-template.centerWeight.x; //   Y var dy:Number = draw.centerWeight.y-template.centerWeight.y; //    draw.matrixTranslate(dx, dy); 

ध्यान रखें कि केंद्र-वे बहुभुज के द्रव्यमान का केंद्र है।

आप दो एल्गोरिदम द्वारा आंकड़ों की समानता निर्धारित कर सकते हैं, चलो उन्हें रेडियल और डायमेंशनल कहते हैं। चलो उन्हें अलग ले जाएं।

रेडियल एल्गोरिदम

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



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

कुल मिलाकर एल्गोरिथ्म

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



UPD: एक आयामी एल्गोरिथ्म का एक उदाहरण यहाँ है ।

संदर्भ

एक्शनस्क्रिप्ट में कार्यान्वयन के लिए उपयोग की जाने वाली लाइब्रेरी: FPGeometry2d.swc और FPGeomControl.swc ।