2009-01-02 29 views
26

मैं त्रिकोण में बहुभुज को तोड़ने के लिए एक एल्गोरिदम या लाइब्रेरी (बेहतर) की तलाश में हूं। मैं डायरेक्ट 3 डी एप्लिकेशन में इन त्रिकोणों का उपयोग करूँगा। सबसे अच्छे उपलब्ध विकल्प क्या हैं?छेद के साथ पॉलीगॉन त्रिभुज

यहाँ मैं अब तक क्या पाया है:

  1. Ben Discoe's notes
  2. FIST: Fast Industrial-Strength Triangulation of Polygons
  3. मुझे पता है कि CGAL ट्राईऐन्ग्युलेशंस प्रदान करता है, लेकिन यकीन है कि अगर यह छेद का समर्थन करता है नहीं कर रहा हूँ।

मैं वास्तव में इस क्षेत्र में पूर्व अनुभव वाले लोगों की कुछ राय की सराहना करता हूं।

संपादित करें: यह एक 2 डी बहुभुज है।

+0

क्या आपको 2 डी (त्रिकोण) या 3 डी (टेट्राहेड्रा) की आवश्यकता है? –

+0

यह एक 2 डी बहुभुज –

उत्तर

18

जोनाथन शेवचुक का Triangle library असाधारण है; मैंने इसे अतीत में त्रिकोण को स्वचालित करने के लिए उपयोग किया है। आप इसे छोटे/संकीर्ण त्रिभुज इत्यादि से बचने के लिए कह सकते हैं, ताकि आप किसी भी त्रिकोण के बजाय "अच्छे" त्रिभुज के साथ आ सकें।

vtkDelaunay2D

इस एल्गोरिथ्म काफी अच्छी तरह से काम करता है:

+0

मैं झुका सकता हूं कि त्रिभुज वास्तव में एक महान उपकरण है। इसने प्रतिष्ठित "जे एच एच विल्किन्सन पुरस्कार न्यूमेरिकल सॉफ्टवेयर" भी जीता, "हर 4 साल में केवल एक बार दिया गया। – batty

+0

इस पर चयनित उत्तर बदलना क्योंकि मुझे वास्तव में यह काम करने के लिए मिला है। –

+0

यहां सबसे बड़ा लाभ यह है कि त्रिभुज त्रिभुज के अलग वर्टेक्स और इंडेक्स बफर बनाने में बहुत आसान बनाता है। इसे प्यार करना! –

2

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

संपादित करें: इस तकनीक का एक आम विस्तार पतवार पर कमजोर त्रिकोणों को कम करना है, जहां सबसे लंबा किनारा या छोटा आंतरिक कोण किसी दिए गए मान से अधिक है। यह एक बेहतर अवतल हलचल बन जाएगा।

+1

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

+0

@ कैमिली - छेद के साथ एक त्रिभुज बहुभुज हमेशा बाधित होता है। बहुभुज किनारों और छेद परिभाषाओं, बाधाओं से हैं।यदि एक त्रिकोण किनारे एक छेद पार किया, तो छेद आंशिक रूप से कवर किया जाएगा। यदि यह बहुभुज किनारे पार करता है, तो टीआईएन उस बहुभुज का त्रिभुज नहीं होगा। –

11

CGAL आप की जरूरत उपकरण है: Constrained Triangulations

आप बस अपनी बहुभुज की कमी के रूप में (सबसे अच्छा (छेद की सीमाओं सहित) है कि आप सभी कोने डालने, और फिर निर्धारित होगा की सीमाओं प्रदान कर सकते हैं Vertex_handles के जोड़े के रूप में बाधाएं)।

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

Polyboolean:

+0

यह साधारण मामलों के लिए एक अच्छा पर्याप्त समाधान है। जहां आप छेद के नीचे छेद, और छेद overlapping है, यह खत्म हो जाता है। मैं स्पष्ट आंतरिक और बाहरी सीमाएं पसंद करता हूं। –

+1

यदि आपके पास छेद ओवरलैपिंग है, तो आपको वास्तव में उन छेदों की सूची बनाए रखना चाहिए जिन्हें आपने पहले ही दर्ज किया है (केवल अंदर/बाहर टैग के बजाय)। इसके अलावा, यह वही है। – Camille

+0

"प्रत्येक बार जब आप बाधा पार करते हैं"? मैं इसे कैसे समझूं? –

17

आप वहाँ पुस्तकालयों में से कुछ और अधिक विकल्प देने के लिए। मैंने कभी यह कोशिश नहीं की, लेकिन यह आशाजनक लग रहा है: http://www.complex-a5.ru/polyboolean/index.html

सामान्य पॉलीगॉन क्लिपर। यह अभ्यास में बहुत अच्छी तरह से काम करता है और त्रिकोण और क्लिपिंग और छेद छेद करता है: http://www.cs.man.ac.uk/~toby/alan/software/

मेरी व्यक्तिगत सिफारिश: जीएलयू (ओपनजीएल यूटिलिटी लाइब्रेरी) से टेस्सेलेशन का उपयोग करें। कोड जीपीसी से तेज, चट्टान ठोस है और कम त्रिकोण उत्पन्न करता है। आपको libed का उपयोग करने के लिए प्रारंभिक ओपनजीएल-हैंडल या इस तरह की कुछ भी आवश्यकता नहीं है।

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


आम तौर पर मेरी सलाह कुछ ऐसा करने के लिए होगी जो काम करता है और अपना खुद का त्रिकोण लिखना शुरू नहीं करता है।

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

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

+0

अपनी सभी टीआईएन सामग्री भी लिखें, और कई अपमानजनक मामलों के बारे में 100% सहमत हैं। इस कारण से कभी भी अपने स्वयं के libs से नहीं चलेगा, हालांकि वहाँ कुछ नई सीजी किताबें उत्कृष्ट हैं। –

1

यह परिमित तत्व विश्लेषण में एक आम समस्या है। इसे "स्वचालित जाल पीढ़ी" कहा जाता है। Google ने this site को वाणिज्यिक और ओपन सोर्स सॉफ़्टवेयर के लिंक के साथ पाया। वे आमतौर पर शुरू करने के लिए ज्यामिति के किसी प्रकार का सीएडी प्रतिनिधित्व मानते हैं।

0

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

यह बाधाओं (छेद/सीमाएं/आदि) का समर्थन करता है, साथ ही सतह को त्रिभुजित करता है जो XY विमान में आवश्यक नहीं है। यह उन कुछ विशेषताओं का भी समर्थन करता है जिन्हें मैंने कहीं और नहीं देखा है (अल्फा मानों पर नोट देखें)।

1

कोशिश libtess2

https://code.google.com/p/libtess2/downloads/list

मूल एसजीआई GLU tesselator (उदार लाइसेंस के साथ) पर आधारित है। बहुत सारे छोटे mallocs के आसपास कुछ स्मृति प्रबंधन मुद्दों को हल करता है।

5

मुझे पॉली 2tri लाइब्रेरी मिली है जो मुझे त्रिभुज के लिए आवश्यक है। यह अन्य पुस्तकालयों (libtess सहित) की तुलना में एक बहुत साफ जाल पैदा करता है, और यह भी छेद का समर्थन करता है। इसे भाषाओं के एक समूह में परिवर्तित कर दिया गया है। लाइसेंस New BSD है, इसलिए आप इसे किसी भी प्रोजेक्ट में उपयोग कर सकते हैं।

Poly2tri library on Google Code

+2

मैंने अपने स्वयं के लिए पाया यह बहुत दुर्घटनाग्रस्त है। – SAKrisT

0

मैं सी # में एक 3 डी बहुभुज triangulator कान कतरन विधि का उपयोग कर लागू किया है। इसका उपयोग करना आसान है, छेद का समर्थन करता है, संख्यात्मक रूप से मजबूत है, और आभासी (आत्म-अंतरण नहीं) उत्तल/गैर-उत्तल बहुभुज का समर्थन करता है।

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