2012-12-12 18 views
5

संभव डुप्लिकेट:
Rasterizing a 2D polygonइसके भीतरी क्षेत्र सहित एक बहुभुज रेखापुंज के लिए एक कुशल मानक एल्गोरिथ्म है

मैं अपने भीतर के क्षेत्र सहित एक बहुभुज रेखापुंज करने की जरूरत है (के सभी टाइल्स का निर्धारण एक ग्रिड जो बहुभुज के अंदर स्थित है)। वर्तमान में मैं एक साधारण ब्रेसनहेम का उपयोग करके सीमा टाइल्स निर्धारित करता हूं लेकिन बहुभुज के "अंदर" रास्टर को रास्टर करने के लिए अब तक कोई कुशल तरीका नहीं है (जो अवतल भी हो सकता है)। अब तक मेरा दृष्टिकोण टाइल रेंज को आयताकार तक सीमित करना है जिसमें बहुभुज समेत प्रत्येक टाइल केंद्र के लिए निर्धारित किया गया है कि क्या यह बहुभुज घुमावदार एल्गोरिदम का उपयोग करके अंदर या बाहर स्थित है। यह अक्षम है क्योंकि इसमें प्रत्येक टाइल के लिए प्रत्येक बहुभुज सीमा खंड की जांच शामिल है। पहले दृश्य से निश्चित रूप से एक तेज दृष्टिकोण होना चाहिए उदा। sth। घुमावदार सीमा का उपयोग कर घुमाने की तरह। क्या कोई मानक एल्गोरिदम है जो इस समस्या को हल करता है और शायद सी ++ में लाइब्रेरी कार्यान्वयन भी करता है?

+1

नेट पर बहुत सारे संसाधन हैं। Google खोज का उपयोग करने वाले पहले दो यहां दिए गए हैं: http://alienryderflex.com/polygon_fill/ और http://ezekiel.vancouver.wsu.edu/~cs442/lectures/raster/polyfill/poly.pdf – NPE

+0

@Potatoswatter : लिंक के लिए धन्यवाद। जैसा कि मैंने कहा था कि मुझे भी अंदरूनी लोगों की जरूरत है और घुमावदार नियमों को जानते हैं, इसलिए मुझे लगता है कि यह एक डुप्लिकेट नहीं है, लेकिन त्रिभुजीकरण और त्रिकोणों को रास्टरिंग करने का तरीका हो सकता है। – Martin

+0

@NPE: कूल, पहला लिंक बिल्कुल वही है जो मैं ढूंढ रहा था। यदि आप इसे उत्तर देते हैं तो मैं इसे तुरंत स्वीकार कर सकता हूं – Martin

उत्तर

6

काफी नेट पर कुछ संसाधनों उदाहरण के लिए, कर रहे हैं:

+0

वह एल्गोरिदम कुछ बहुभुजों के साथ काम नहीं करेगा जिनमें अक्षरों के समानांतर किनारों के साथ समान समन्वय होते हैं (वाई समन्वय यदि स्कैनलाइन क्षैतिज है, तो x समन्वय है यदि स्कैनलाइन है ऊर्ध्वाधर)। उदाहरण के लिए, यह अक्ष-समांतर खंडों के बहुभुज पर असफल हो जाएगा जो एक पत्र टी या पी को बाध्य करता है। – gvlasov

संबंधित मुद्दे