को रास्टराइज करना मुझे बिंदुओं की सूची के रूप में प्रतिनिधित्व किए गए बंद 2 डी बहुभुज से बाइनरी बिटमैप बनाने की आवश्यकता है। क्या आप कृपया मुझे ऐसा करने के लिए कुशल और पर्याप्त सरल एल्गोरिदम को इंगित कर सकते हैं, या इससे भी बेहतर, कुछ सी ++ कोड?एक 2 डी बहुभुज
बहुत बहुत धन्यवाद!
पीएस: मैं अपनी परियोजना पर निर्भरता जोड़ने से बचना चाहता हूं। हालांकि अगर आप ओपन-सोर्स लाइब्रेरी का सुझाव देते हैं, तो मैं हमेशा कोड देख सकता हूं, इसलिए यह भी उपयोगी हो सकता है।
आपके द्वारा इच्छित जादू Google वाक्यांश या तो "शून्य-शून्य घुमावदार नियम" या "यहां तक कि विषम बहुभुज भरना" है।
दोनों लागू करना बहुत आसान और पर्याप्त सबसे प्रयोजनों के लिए तेजी से कर रहे हैं:
के लिए विकिपीडिया प्रविष्टियां देखें। कुछ चतुरता के साथ, उन्हें एंटीअलाइज्ड भी बनाया जा सकता है।
जटिलता हे (पिक्सेल में क्षेत्र)
आप pygame में नियमित बहुभुज भरण की जाँच कर सकते हैं। draw_fillpoly फ़ंक्शन देखें।
एल्गोरिदम बहुत सरल है। यह उन सभी पदों को पाता है जो प्रत्येक खंड वाई अक्ष के साथ छेड़छाड़ करता है। इन चौराहे को क्रमबद्ध किया जाता है, और फिर क्षैतिज रूप से चौराहे की प्रत्येक जोड़ी भरता है।
यह जटिल और अंतरंग आकार को संभालेगा, लेकिन जाहिर है कि आप इस एल्गोरिदम को बड़ी मात्रा में सेगमेंट के साथ क्रश कर सकते हैं।
बहुत संबंधित नहीं है लेकिन btw पीट आप pygame बनाने के लिए कमाल कर रहे हैं :) – yairchu
की एक मजबूत implimentation के लिए Darel Rex Finley's Efficient Polygon Fill, या इसे की Blender's version देखें। (बहुभुज उलट जा सकता है और एक ही परिणाम उपज)
यह एक अजीब/विधि है जो स्वयं लाइनों अन्तर्विभाजक का समर्थन करता है, ऐसी स्थितियों का पता लगाने के जटिल कोड की जरूरत के बिना, और घुमावदार पर निर्भर नहीं करता भी भरने है।
अद्यतन, मुझे लगता है कि से अधिक पाशन टाल Darel रेक्स की विधि के एक अनुकूलित संस्करण सभी का समन्वय करता है प्रत्येक y-पिक्सेल के लिए बनाया है।
स्टैंड अकेले कार्यान्वयन:
speedup संभावना घातीय होगा, एक त्वरित परीक्षण से, अपने 7.5X चारों ओर तेजी से (11x जब round कॉल को हटाने), एक मनमाना हाथ एक 2540x1600 क्षेत्र, YMMV से अधिक आड़ी-तिरछी रेखाएं खींची का उपयोग कर।
@plinth: क्या यह सरल बहुभुज के लिए ओवर-मार नहीं है? – yairchu
एक साधारण बहुभुज क्या है? @static_rtti निर्दिष्ट नहीं करता है कि कितने अंक या बहुभुज हमेशा उत्तल होंगे, इसलिए एक सामान्य समाधान सही उत्तर है। एनजेडब्लूडब्लू और ईओ बट-सरल हैं और खुद को स्कैनलाइन उन्मुख समाधान, आदि इत्यादि के लिए उधार देते हैं। – plinth
@plinth: धन्यवाद, यह वही है जो मैं ढूंढ रहा था! गुगलिंग सामान मुश्किल हो सकता है जब आपके पास उस जादू वाक्यांश नहीं है :-) –