استيفاء تسلسل النقاط

Question

بالنظر إلى تسلسل اعتباطي للنقاط في الفضاء، كيف يمكنك إنتاج استيفاء مستمر وسلس فيما بينها؟

نرحب بالحلول ثنائية وثلاثية الأبعاد.كما يتم تقدير الحلول التي تنتج قائمة من النقاط ذات التفاصيل التعسفية والحلول التي تنتج نقاط تحكم لمنحنيات بيزيير.

أيضًا، سيكون من الرائع رؤية حل تكراري يمكنه تقريب الأجزاء المبكرة من المنحنى عند حصوله على النقاط، حتى تتمكن من الرسم به.

Answer 1

ال خط كاتمول-روم ويضمن المرور عبر جميع نقاط المراقبة.أجد أن هذا أكثر فائدة من محاولة ضبط نقاط التحكم المتوسطة لأنواع أخرى من الخطوط.

هذا PDF من تأليف كريستوفر تويج يحتوي على مقدمة مختصرة لطيفة لرياضيات الخط.أفضل جملة مختصرة هي:

تتمتع Catmull-Rom slines بالاستمرارية C1 ، والتحكم المحلي ، والاستيفاء ، ولكن لا تقع في بدن محدب نقاط التحكم الخاصة بهم.

وبعبارة أخرى، إذا كانت النقاط تشير إلى انحناء حاد إلى اليمين، فإن الخط سوف يميل إلى اليسار قبل أن يتحول إلى اليمين (هناك صورة مثال في تلك الوثيقة).يمكن التحكم في ضيق تلك المنعطفات، في هذه الحالة باستخدام معلمة تاو في مصفوفة المثال.

هنا مثال آخر مع بعض كود DirectX القابل للتنزيل.

Answer 2

طريقة واحدة هي لاغرانج متعدد الأسماء, ، وهي طريقة لإنتاج متعدد الحدود الذي سيمر عبر جميع نقاط البيانات المعطاة.

خلال سنتي الأولى في الجامعة، كتبت أداة صغيرة للقيام بذلك بتقنية ثنائية الأبعاد، ويمكنك القيام بذلك تجده في هذه الصفحة, ويسمى لاغرانج حلالا.تحتوي صفحة ويكيبيديا أيضًا على نموذج للتنفيذ.

كيفية العمل كالتالي:لديك متعدد الحدود من الرتبة n، 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 3

يجب عليك إلقاء نظرة على ب-الخطوط.ميزتها على منحنيات بيزيير هي أن كل جزء يعتمد فقط على النقاط المحلية.لذا فإن تحريك نقطة ما ليس له أي تأثير على أجزاء المنحنى البعيدة، حيث يتم تحديد "البعيد" بواسطة معامل الخط.

المشكلة في كثيرة حدود لانغرانج هي أن إضافة نقطة يمكن أن يكون له تأثيرات شديدة على الأجزاء التي تبدو اعتباطية من المنحنى؛ليس هناك "محلية" كما هو موضح أعلاه.

Answer 4

هل نظرت إلى يونكس خدد يأمر؟هل يمكن إجبار ذلك على فعل ما تريد؟

Answer 5

هناك العديد من الخوارزميات للاستيفاء (والاستقراء) بين مجموعة من النقاط التعسفية (لكن النهائية).يجب عليك التحقق وصفات عددية, ، فهي تتضمن أيضًا تطبيقات C++ لتلك الخوارزميات.

Answer 6

لسوء الحظ، فإن لاغرانج أو الأشكال الأخرى من الاستيفاء متعدد الحدود لن تعمل على مجموعة عشوائية من النقاط.إنهم يعملون فقط على مجموعة ذات بعد واحد على سبيل المثال.س

س_أنا <س_أنا+1

لمجموعة عشوائية من النقاط، على سبيل المثال.مسار رحلة الطائرة، حيث تكون كل نقطة عبارة عن زوج (خط الطول وخط العرض)، سيكون من الأفضل لك ببساطة تصميم رحلة الطائرة باستخدام خطوط الطول والعرض والسرعة الحالية.من خلال ضبط المعدل الذي يمكن أن تدور به الطائرة (سرعتها الزاوية) اعتمادًا على مدى قربها من نقطة الطريق التالية، يمكنك تحقيق منحنى سلس.

لن يكون المنحنى الناتج ذا أهمية رياضية ولا يمنحك نقاط تحكم أكثر بيزييرًا.ومع ذلك، ستكون الخوارزمية بسيطة من الناحية الحسابية بغض النظر عن عدد نقاط الطريق ويمكن أن تنتج قائمة محرفة من النقاط بتفاصيل عشوائية.ولن يتطلب الأمر أيضًا تقديم مجموعة كاملة من النقاط مقدمًا، بل يمكنك ببساطة إضافة نقاط الطريق إلى نهاية المجموعة كما هو مطلوب.

Answer 7

خطرت لي نفس المشكلة ونفذتها مع بعض الأصدقاء في ذلك اليوم.أحب مشاركة المشروع النموذجي على جيثب.

https://github.com/johnjohndoe/PathInterpolation
لا تتردد في شوكة ذلك.

Answer 8

جوجل "الانحدار المتعامد".

في حين تحاول تقنيات المربعات الصغرى تقليل المسافة العمودية بين خط الملاءمة وكل f(x)، فإن الانحدار المتعامد يقلل من المسافات المتعامدة.

إضافة

في ظل وجود بيانات صاخبة، الجليلة رانساك الخوارزمية تستحق التدقيق أيضًا.

Answer 9

في عالم الرسومات ثلاثية الأبعاد، تحظى NURBS بشعبية كبيرة.مزيد من المعلومات يمكن البحث عنها بسهولة في جوجل.