5

मैं एल्गोरिदम के लिए नेट के चारों ओर स्काउटिंग कर रहा हूं जो आपको 2 डी बहुभुज के विस्तार के स्तर (एलओडी) प्रस्तुतिकरण बनाने में सक्षम बनाता है, लेकिन कोई भी सभ्य संदर्भ नहीं ढूंढ पा रहा हूं। हो सकता है कि मैं गलत खोज शब्द का उपयोग कर रहा हूं, लेकिन सभी खोज परिणाम 3 डी एलओडी एल्गोरिदम के लिए हैं, जो मुझे लगता है, (?) वास्तव में 2 डी में लागू नहीं किया जा सकता है।2 डी स्तर का विस्तार (एलओडी) एल्गोरिदम

मुझे यकीन है कि 3 डी ग्राफिक्स के हमले से पहले, कई लोग 2 डी एलओडी एल्गोरिदम पर काम करेंगे। कोई सुराग या पॉइंटर्स जहां मैं अधिक जानकारी प्राप्त कर सकता हूं? धन्यवाद!

+1

दिलचस्प, शायद आकार-सरलीकरण, छवि अमूर्तता या यहां तक ​​कि संपीड़न की तलाश में? एलओडी के लिए क्या आवश्यकताएं हैं? जैसा कि इच्छा में संकुचित हो जाएगा? क्या यह स्मृति के लिए या गहराई को अनुकरण करने के लिए प्रदर्शन के लिए है? –

+0

मैं मौजूदा (विरासत) एल्गोरिदम के प्रदर्शन में सुधार करने के लिए देख रहा हूं। अनिवार्य रूप से, मैं बहुभुज का एक उचित 'सिकुंक-रैप' अनुमान चाहता हूं, जहां प्रमुख बाहरी विशेषताएं संरक्षित हैं, और आंतरिक विवरण छिपे हुए हैं। सुझाए गए कीवर्ड के लिए +1। धन्यवाद! – tathagata

उत्तर

4

स्पष्ट सबसे कमजोर एल्गोरिदम के अलावा जो बहुभुज से प्रत्येक एनएच वर्टेक्स (एन द्वारा शिखर की संख्या को कम करने) को लेना होगा, यहां कुछ 3 डी एल्गोरिदम से प्रेरित एक विचार है।

आमतौर पर, 3 डी में, आवश्यक मात्रा में कम योगदान देने वाले चेहरे को हटाने के लिए आवश्यक है। ऐसा करने के लिए, हम मॉडल के "सबसे स्पष्ट" क्षेत्रों को सरल बनाने का प्रयास करते हैं। खंडों सी और सी + 1 के बीच

  1. कंप्यूट सभी कोणों:

    2 डी में अब आप इस अनुवाद कर सकें "खंडों उन दोनों के बीच सबसे छोटा कोण है कि सरल करने के लिए एक पहला भोली कार्यान्वयन हो सकता है। बहुभुज

  2. एक दिया सीमा से नीचे सभी कोणों ले लो (या एम छोटी से छोटी कोण लेने के लिए)
  3. खंडों हम 2. (में पहचान को सरल की जगह [पाई, पाई + 1] और [पाई + 1, पी 2 ] [पीआई, पीआई + 2] द्वारा)
  4. 1 से दोहराएं जब तक कि हमने हमारे बहुभुज को पर्याप्त रूप से कम नहीं किया है

बेशक, यह इष्टतम नहीं है लेकिन यह गुणवत्ता और गति के बीच एक अच्छा व्यापार होना चाहिए। कोण के बजाय, आप ([, पाई पाई + 2]) दो खंडों (पाई + 1) के बीच बिंदु और संभावित सरलीकृत खंड के बीच कम से कम दूरी का समय लग सकता

संपादित करें:

एक और कलन विधि मैं अगर मैं बहुत ज्यादा प्रदर्शन जरूरत नहीं थी की कोशिश करेंगे:

  1. पर विचार करें एक Catmull-रोम पट्टी
  2. Tesselate अंक की वांछित संख्या में इस पट्टी का नियंत्रण बिंदुओं के रूप में मूल बहुभुज कोने

अंत में, मैं उस लिंक पर आप के लिए कुछ स्रोत कोड मिला: http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html, साथ ही जुड़े एल्गोरिदम: http://www.geom.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm

+0

सुझावों के लिए धन्यवाद। मुझे लगता है कि मैं आपके द्वारा सुझाए गए एल्गोरिदम के संयोजन का उपयोग करने में सक्षम हूं और एक ने जरुज को जो कुछ भी चाहिए, उसे हासिल करने के लिए ऊपर दिया। +1।दुर्भाग्यवश, मैं दोनों उत्तरों को सही के रूप में चिह्नित नहीं कर सकता, इसलिए इसे सही के रूप में चिह्नित करना, लेकिन जुराज द्वारा सुझाए गए 'डगलस-पेकर एल्गोरिदम' समान रूप से अच्छे हैं। – tathagata

+0

हाँ, मुझे राम डगलस पेकर एल्गोरिदम के बारे में पता नहीं था, लेकिन मुझे यह पसंद है। इसके साथ अच्छी बात यह है कि जब आप उदाहरण के लिए अपने अधिकतम अंक प्राप्त कर चुके हैं तो आप आसानी से रुक सकते हैं। –

4

Douglas-Peucker algorithm के लिए खोज जो पोलीलाइंस आसान बनाने के लिए प्रयोग किया जाता है, लेकिन बहुभुज का समर्थन करने के लिए बढ़ाया जा सकता है। मैंने यही उपयोग किया है। यदि आपको इसकी ज़रूरत है तो स्थलीय रूप से स्थिर एक्सटेंशन भी हैं।

+0

+1 मुझे इस शांत एल्गोरिदम के बारे में बताने के लिए +1। यह काम कर सकता है लेकिन मुझे इसे अपने संदर्भ में देखना होगा। और यह एक बात है जिसे मैंने प्रश्न में उल्लेख करने से चूक दिया, लेकिन मुझे नहीं पता कि शब्दों में इसे कैसे समझाया जाए, लेकिन ऊपर दिए गए मुख्य प्रश्न पर मेरी टिप्पणी देखें। – tathagata