आंशिक त्रिभुज (प्रतिबंधित त्रिभुज) को पूरा करने के लिए एल्गोरिदम

Question

एक विमान में बिंदुओं के एक सेट को देखते हुए और एक अपूर्ण triangulation of the convex hull of the points (केवल कुछ किनारों को दिया जाता है), मैं त्रिभुज को पूरा करने के लिए एक एल्गोरिदम की तलाश में हूं (प्रारंभिक दिए गए किनारों को चाहिए तय रहो)। आप मान सकते हैं कि आंशिक त्रिकोण को पूरा करना संभव है लेकिन यह बहुत अच्छा होगा अगर आप इसे जांचने के लिए एल्गोरिदम भी सुझा सकते हैं।

अद्यतन "आपको अंक आर^2 के एक सेट का एक उत्तल हॉल दिया गया है, जो मूल रूप से इसके अंदर कुछ बिंदुओं के साथ एक बहुभुज है। हम उन बिंदुओं के सेट को त्रिकोण करना चाहते हैं जो स्वयं पर एक सीधा मामला है, लेकिन आपको कुछ किनारों को भी दिया जाता है कि आप जिन त्रिभुज के साथ आते हैं उन्हें उन किनारों का उपयोग करना चाहिए। "

Answer 1

शायद यह एक बेवकूफ उत्तर है, लेकिन क्या आप केवल एक बाधित डेल्यूने त्रिकोण का उपयोग नहीं कर सकते? ज्ञात किनारों को बाधाओं के रूप में जोड़ें।

सीजीएएल में nice implementation है। टूल triangle में समान विशेषताएं हैं और शुरुआत करना आसान है, लेकिन (शायद) थोड़ा कम लचीलापन है।

Answer 2

मुझे पता चला कि पुस्तक "कम्प्यूटेशनल ज्यामिति: एक परिचय" विषय का विस्तृत उपचार है हालांकि यह छद्म कोड को लागू करने के लिए तैयार नहीं है।

सबसे आसान एल्गोरिदम एक लालची है जो सभी संभावित किनारों को दर्शाता है और फिर उन्हें पहले से जोड़े गए युगों के साथ छेड़छाड़ से बचकर एक-एक करके जोड़ता है। O (n^2 log n) पर चलने वाले समय को कम करने के तरीके के बारे में पुस्तक में एक लंबी चर्चा है।

फिर एक ओ (एन लॉग एन) एल्गोरिदम है जो पहले दिए गए किनारों के साथ उत्तल हल को नियमित करता है और फिर व्यक्तिगत रूप से प्रत्येक मोनोटोन पॉलीगॉन को त्रिकोणीय करता है।