خطوط متعددة ناعمة مع الحد الأدنى من التشوه

Question

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

أرغب في تنعيم الخطوط المتعددة، لكن خوارزمية المتوسط ​​العادية تميل إلى تقليص المساحة:

for (int i = 0; i < (V.Length-1); i++)
{
   PointF prev = V[i-1]; //I have code that wraps the index around.
   PointF next = V[i+1];       
   PointF pt = V[i];

   float ave_x = one_third * (prev.X + next.X + pt.X);
   float ave_y = one_third * (prev.Y + next.Y + pt.Y);

   smooth_polyline[i] = new PointF(ave_x, ave_y);
}

تحتوي خطوطي المتعددة على آلاف النقاط وعادةً ما تكون الزاوية بين قطعتين متجاورتين أقل من درجة واحدة.

هل هناك طريقة أفضل لتنعيم هذه المنحنيات، وهو أمر يفصل بين القمم بشكل متساوٍ، دون التأثير على المساحة كثيرًا؟

Answer 1

يمكنك الاطلاع على الأدبيات المتعلقة بـ "تبسيط المنحنى" مثل خوارزمية دوجلاس-بيكر أو هذه الورقة http://www.cs.ait.ac.th/~guha/papers/simpliPoly.pdf.

ربما لن يعمل هذا بشكل جيد إذا كنت بحاجة إلى رؤوس متباعدة بشكل متساوٍ حتى عندما تكون مقاطع الخطوط المتجاورة التي تحددها متداخلة تقريبًا.

Answer 2

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

Answer 3

يمكنك أيضًا استخدام الخطوط للاستكمال - ما عليك سوى البحث في ويكيبيديا

Answer 4

قام شخص ما بنقل خوارزميتين للتنعيم إلى لغة C#، بترخيص CPOL (مجاني)، انظر هنا:

https://github.com/RobinCK/smooth-polyline