هيكل مستقيم (خوارزمية)

الهيكل المستقيم (بالإنجليزية: Straight Skeleton) هو بنية هندسية تُستخرج من مضلع مستوٍ عبر عملية تقلص متجانس لأضلاعه باتجاه الداخل، بحيث تتحرك الأضلاع بشكل متوازٍ وبسرعة ثابتة. ينتج عن هذه العملية مخطط داخلي مكوّن حصريًا من مقاطع مستقيمة، يمثل المسارات التي تتبعها رؤوس المضلع أثناء عملية التقلص.Aichholzer, O., Aurenhammer, F., Alberts, D., & Gärtner, B. (1996). A novel type of skeleton for polygons. Journal of Universal Computer Science, 1(12), 752–761. يُستخدم هذا المفهوم في مجالات متعددة مثل النمذجة المعمارية، وتوليد أسطح الأسقف، والتخطيط العمراني، والرسوميات الحاسوبية، ومعالجة الصور الهندسية Felkel, P., & Obdržálek, Š. (1998). Straight skeleton implementation. Proceedings of Spring Conference on Computer Graphics 
Biedl, T., Held, M., Huber, S., Kaaser, D., & Palfrader, P. (2015). Weighted straight skeletons in the plane. Computational Geometry, 48(2), 120–133.

تصغير|بديل=The shrinking process, the straight skeleton (blue) and the roof model.|عملية الانكماش، والهيكل المستقيم (الأزرق)، ونموذج السقف.
 التعريف الرياضي 

يُعرّف الهيكل المستقيم لمضلع بسيط 𝑃 على أنه مجموعة النقاط التي تمثل مسارات حركة رؤوس المضلع أثناء تقلص أضلاعه داخليًا بمعدل ثابت، مع الحفاظ على توازي الأضلاع طوال مدة العملية.[1]

تُنتج هذه العملية

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

ويمثل هذا الهيكل نوعًا خاصًا من التحليل البنيوي للشكل الهندسي، يختلف عن المحور الوسيط (Medial Axis) الذي يسمح بوجود أقواس منحنية.Blum, H. (1967). A transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form.

 الخوارزميات الحسابية 

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

اقترح آيشهولتس وأوبريست (Aichholzer & Aurenhammer) أول خوارزمية عملية لحساب الهيكل المستقيم بزمن حسابي من رتبة

𝑂(𝑛log𝑛)O(nlogn) في الحالات الخاصة و𝑂(𝑛log⁡2𝑛)O(nlog2n) في الحالات العامة.Aurenhammer, F. (1991). Voronoi diagrams — a survey of a fundamental geometric data structure. ACM Computing Surveys, 23(3), 345–405

كما طوّر فيلتكامب (Veltkamp) ورفاقه خوارزميات أكثر استقرارًا عددياً للتعامل مع الحالات الخاصة والزوايا الحادة.Veltkamp, R. C., & Hagedoorn, M. (1999). State of the art in shape matching. Technical Report, Utrecht University

 التطبيقات 

تشمل التطبيقات الأساسية للهيكل المستقيم:

 جيومترية العمارة الرقمية: توليد الأسقف متعددة الميول انطلاقًا من مخططات أفقية.[2]
 التخطيط العمراني: تقسيم القطع الأرضية غير المنتظمة.Held, M. (2001). On computing straight skeletons by means of kinetic data structures. Computational Geometry, 16(2), 107–121
 الرسوميات الحاسوبية: حساب المسارات الداخلية وتحليل الأشكال.[3]
 التصنيع الرقمي: توليد مسارات القطع CNC.Choi, B. K., & Jerard, R. B. (1998). Sculptured Surface Machining. Springer

 مقارنة نقدية: الهيكل المستقيم والمورفينغ الهندسي التركيبي 
 حدود الهيكل المستقيم 
تعتمد خوارزمية الهيكل المستقيم على مبدأ الإزاحة المتوازية (Parallel Offsetting)، مما يجعل التحول الهندسي الناتج:
 تحولًا انكماشيًا فقط،
 محافظًا على البنية الطوبولوجية العامة للشكل،
 غير قادر على توليد تحولات شكلية جذرية.

وقد أشار باير وآخرون إلى أن هذا النوع من الخوارزميات محدود بطبيعته الحركية، ولا يمكنه توليد انتقالات هندسية عميقة بين أشكال مختلفة الطبيعة الهندسية  Mitra, N. J., Guibas, L. J., & Pauly, M. (2006). Partial and approximate symmetry detection for 3D geometry. ACM SIGGRAPH.

 التحول الهندسي التركيبي 
في المقابل، يعتمد هذا التحول (أو المورفينغ) على:
تصغير|jتحول هندسي تركيبي بين مضلع خارجي غير منتظم ومستطيل داخلي. جيث لا يتم التحول عبر إزاحات متتالية بسيطة
 التقسيمات المتتابعة،
 إدخال بُنى وسيطة،
 استخدام المنصفات الهندسية (bisectors)،
 وإعادة بناء البنية الداخلية تدريجيًا.

هذا النوع من المورفينغ لا يقتصر على تقليص الشكل، بل يقوم بـ:

 إعادة صياغة كاملة للبنية الهندسية الداخلية للشكل.

وتشير دراسات حديثة في مجال تحويل الأشكال الهندسية (Shape Transformation) إلى أن الأساليب التركيبية القائمة على البنى الوسيطة تتفوق على الأساليب الحركية البحتة في:

 التحكم الطوبولوجي،
 الاستقرار العددي،
 وإمكانية الانتقال بين أشكال غير متجانسة هندسيًا Alexa, M. (2002). Recent advances in mesh morphing. Computer Graphics and Applications, IEEE Botsch, M., Pauly, M., Gross, M., & Kobbelt, L. (2010). Polygon Mesh Processing. AK Peters.

 التحول من اللاانتظام إلى الانتظام 

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

في المقابل، يسمح المورفينغ التركيبي القائم على التقسيمات المتتابعة والبنى الوسيطة بتحقيق هذا النوع من التحولات العميقة، حيث يتم:

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

وقد أظهرت دراسات في المورفينغ الهندسي أن هذه المقاربة تتيح تحكمًا أعلى في البنية النهائية مقارنة بالأساليب القائمة على الإزاحة فقط Hormann, K., & Greiner, G. (2000). MIPS: An efficient global parametrization method. Curve and Surface Design Floater, M. S., & Hormann, K. (2005). Surface parameterization: a tutorial and survey. Advances in Multiresolution for Geometric Modelling.

 الخلاصة 

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

 المراجع 

تصنيف:هندسة متقطعة

en:Straight skeleton