प्वाइंट अनुक्रम इंटरपोलेशन

Question

अंतरिक्ष में बिंदुओं के मनमाना अनुक्रम को देखते हुए, आप उनके बीच एक चिकनी निरंतर इंटरपोलेशन कैसे तैयार करेंगे?

2 डी और 3 डी समाधान का स्वागत है। समाधान जो मनमानी ग्रैन्युलरिटी और समाधानों पर अंक की एक सूची उत्पन्न करते हैं जो बेजियर वक्र के लिए नियंत्रण बिंदु उत्पन्न करते हैं, उनकी भी सराहना की जाती है।

इसके अलावा, यह एक पुनरावृत्ति समाधान देखने के लिए अच्छा होगा जो वक्र के शुरुआती वर्गों को अनुमानित कर सकता है क्योंकि इसे अंक प्राप्त हुए हैं, ताकि आप इसके साथ आकर्षित कर सकें।

Answer 1

Catmull-Rom spline सभी नियंत्रण बिंदुओं के माध्यम से पारित होने की गारंटी है। मुझे यह अन्य प्रकार के स्प्लिंस के लिए मध्यवर्ती नियंत्रण बिंदु समायोजित करने की कोशिश करने से अधिक आसान लगता है।

यह PDF by Christopher Twigg स्पिन के गणित के लिए एक अच्छा संक्षिप्त परिचय है। सबसे अच्छा सारांश वाक्य है:

Catmull-रोम splines सी 1 निरंतरता, स्थानीय नियंत्रण, और प्रक्षेप है, लेकिन के भीतर अपने नियंत्रण अंकों की उत्तल पतवार झूठ मत बोलो।

एक और तरीके से कहा, यदि अंक दाईं ओर एक तेज झुकाव इंगित करते हैं, तो स्पिनलाइन दाईं ओर मोड़ने से पहले बैंक छोड़ जाएगी (उस दस्तावेज़ में एक उदाहरण चित्र है)। उन मामलों की मजबूती नियंत्रण में बदल जाती है, इस मामले में उदाहरण मैट्रिक्स में अपने टाउ पैरामीटर का उपयोग कर।

कुछ डाउनलोड करने योग्य डायरेक्टएक्स कोड के साथ another example है।

Answer 2

क्या आपने यूनिक्स स्पलीन कमांड देखा है? क्या आप जो चाहते हैं उसे करने में मजबूर हो सकते हैं?

Answer 3

एक तरीका Lagrange polynominal है, जो एक बहुपद का उत्पादन करने का एक तरीका है जो सभी दिए गए डेटा बिंदुओं के माध्यम से जाएगा।

विश्वविद्यालय में अपने पहले वर्ष के दौरान, मैंने 2 डी में ऐसा करने के लिए एक छोटा सा टूल लिखा, और आप find it on this page कर सकते हैं, इसे लग्रेंज सॉल्वर कहा जाता है। विकिपीडिया के पृष्ठ में नमूना कार्यान्वयन भी है।

यह कैसे काम करता है इस प्रकार है: आपके पास एन-ऑर्डर बहुपद, p(x) है, जहां n आपके पास अंक की संख्या है। इसमें a_n x^n + a_(n-1) x^(n-1) + ...+ a_0 है, जहां _ सबस्क्रिप्ट है, ^ शक्ति है। इसके बाद आप युगपत समीकरण के एक सेट में इस बारी:

p(x_1) = y_1 
p(x_2) = y_2 
... 
p(x_n) = y_n 

आप एक संवर्धित मैट्रिक्स में ऊपर कनवर्ट करते हैं, और गुणांक a_0 ... a_n के लिए हल। फिर आपके पास एक बहुपद है जो सभी बिंदुओं के माध्यम से जाता है, और अब आप बिंदुओं के बीच अंतर कर सकते हैं।

नोट हालांकि, यह आपके उद्देश्य के अनुरूप नहीं हो सकता है क्योंकि यह वक्रता आदि को समायोजित करने का कोई तरीका नहीं प्रदान करता है - आप एक ऐसे समाधान से फंस गए हैं जिसे बदला नहीं जा सकता है।

Answer 4

दुर्भाग्यवश लग्रेंज या बहुपद इंटरपोलेशन के अन्य रूप अंक के मनमाने ढंग से सेट पर काम नहीं करेंगे। वे केवल एक सेट पर काम करते हैं जहां एक आयाम में उदा। एक्स

एक्स _मैं < एक्स _{मैं + 1}

अंकों की आर्बिटरी सेट, उदा के लिए एक हवाई जहाज उड़ान मार्ग, जहां प्रत्येक बिंदु एक (रेखांश, अक्षांश) जोड़ी है, आप वर्तमान रेखांश & अक्षांश और वेग के साथ हवाई जहाज की यात्रा को मॉडलिंग करना बेहतर होगा। उस दर को समायोजित करके जिस पर हवाई जहाज बदल सकता है (इसके कोणीय वेग) इस पर निर्भर करता है कि यह अगले रास्ते के करीब कितना करीब है, आप एक चिकनी वक्र प्राप्त कर सकते हैं।

परिणामस्वरूप वक्र गणितीय रूप से महत्वपूर्ण नहीं होगा और न ही आपको बेझिझक नियंत्रण बिंदु देगा। हालांकि एल्गोरिदम समरूप रूप से सरल होगा, चाहे वे रास्ते बिंदुओं की संख्या के बावजूद और मनमाने ढंग से ग्रैन्युलरिटी पर बिंदुओं की एक इंटरप्लाटेड सूची उत्पन्न कर सकें। इसके लिए आपको आगे के बिंदुओं का पूरा सेट प्रदान करने की आवश्यकता नहीं होगी, आप बस सेट के अंत में आवश्यकतानुसार मार्ग बिंदु जोड़ सकते हैं।

Answer 5

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

Answer 6

Google "ऑर्थोगोनल रिग्रेशन"।

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

परिशिष्ट

शोर डेटा की उपस्थिति में, सम्मानित RANSAC एल्गोरिथ्म भी बाहर की जाँच के लायक है।

Answer 7

3 डी ग्राफिक्स दुनिया में, NURBS लोकप्रिय हैं। आगे की जानकारी आसानी से googled है।

Answer 8

आपको B-splines पर एक नज़र रखना चाहिए। बेजियर वक्रों पर उनका लाभ यह है कि प्रत्येक भाग केवल स्थानीय बिंदुओं पर निर्भर होता है। तो एक बिंदु को स्थानांतरित करने से वक्र के कुछ हिस्सों पर कोई प्रभाव नहीं पड़ता है, जहां बहुत दूर हैं, जहां "दूर" स्पलीन के पैरामीटर द्वारा निर्धारित किया जाता है।

लैंग्रेंज बहुपद के साथ समस्या यह है कि एक बिंदु जोड़ना वक्र के प्रतीत होता है मनमाना भागों पर अत्यधिक प्रभाव डाल सकता है; उपर्युक्त वर्णित कोई "स्थानीयता" नहीं है।

Answer 9

मैं एक ही समस्या के साथ आया और इसे दूसरे दिन कुछ दोस्तों के साथ लागू किया। मैं जिथूब पर उदाहरण प्रोजेक्ट साझा करना चाहता हूं।

https://github.com/johnjohndoe/PathInterpolation
यह कांटा करने के लिए स्वतंत्र महसूस।