عدد التعديلات للمستخدم (user_editcount) | 2 |
اسم حساب المستخدم (user_name) | 'YasmeenAlslman' |
عمر حساب المستخدم (user_age) | 889328 |
المجموعات (متضمنة غير المباشرة) التي المستخدم فيها (user_groups) | [
0 => '*',
1 => 'user'
] |
ما إذا كان المستخدم يعدل من تطبيق المحمول (user_app) | false |
ما إذا كان المستخدم يعدل عبر واجهة المحمول (user_mobile) | false |
المجموعات العالميَّة التي يمتلكها الحساب (global_user_groups) | [] |
هوية الصفحة (page_id) | 8982806 |
نطاق الصفحة (page_namespace) | 0 |
عنوان الصفحة (بدون نطاق) (page_title) | 'خوارزمية الهيكل المحدب' |
عنوان الصفحة الكامل (page_prefixedtitle) | 'خوارزمية الهيكل المحدب' |
آخر عشرة مساهمين في الصفحة (page_recent_contributors) | [
0 => 'JarBot',
1 => 'MenoBot',
2 => 'Mr.Ibrahembot',
3 => 'YasmeenAlslman'
] |
عمر الصفحة (بالثواني) (page_age) | 154132 |
أول مستخدم ساهم في الصفحة (page_first_contributor) | 'YasmeenAlslman' |
فعل (action) | 'edit' |
ملخص التعديل/السبب (summary) | 'adding photos and links' |
نموذج المحتوى القديم (old_content_model) | 'wikitext' |
نموذج المحتوى الجديد (new_content_model) | 'wikitext' |
نص الويكي القديم للصفحة، قبل التعديل (old_wikitext) | '{{مقالة غير مراجعة|تاريخ = نوفمبر 2022}}
{{يتيمة|تاريخ=نوفمبر 2022}}
إن الخوارزميات التي تبني هياكلاً [[انغلاق محدب|محدبة]] (convex hull) لها العديد من الاستخدامات [[انغلاق محدب|الواسعة]] في [[رياضيات|الرياضيات]] [[علم الحاسوب|وعلوم الحاسوب]].
في [[هندسة رياضية حاسوبية|الهندسة الحسابية]] ، تم اقتراح العديد من الخوارزميات لحساب الهيكل المحدب لمجموعة نقاط محددة، وكل خوارزمية من هذه الخوارزميات لها درجة مختلفة من [[تحليل الخوارزميات|تعقيد العمليات الحسابية]].
إن خوارزمية الهيكل المحدب [[بنية بيانات|تمثل]] الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة و واضحة و من الممكن تقدير تعقيد هذه الخوارزميات ب ''n'' والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. او من الممكن تقديرها ب ''h'' والتي تمثل عدد النقاط على حدود الهيكل المحدب.
.
== الحالة المستوية لبناء الهيكل المحدب ==
في البداية لنعتبر ان الحالة العامة لبناء الهيكل المحدب تكون مدخلاتها عبارة عن مجموعة محددة غير مرتبة من النقاط على مستوى ديكارت. وهناك حالة خاصة للمدخلات سيأتي فيما بعد توضيحها بحيث تكون فيها النقاط المدخلة مرتبة على حدود مضلع بسيط.
إذا لم تكن جميع النقاط على نفس الخط، فإن الهيكل المحدب يكون [[مضلع محدب|مضلعًا محدبًا]] رؤسه تكون أحد هذه النقاط. واكثر هذه الحلات شيوعا هي عندما تكون نقاط الهيكل المضلع مرتبة على طول حدوده في اتجاه عقارب الساعة أو عكس عقارب الساعة. و في بعض التطبيقات يكون من الملائم تمثيل مضلع محدب كتقاطع لمجموعة من أنصاف المستويات .
=== الحد الأدنى من التعقيد الحسابي ===
إن معرفة التعقيد الحسابي لبناء الهيكل المحدب المضلع لمجموعة من النقاط في فضاء ثنائي الابعاد، يتم تمثيله بسهولة وذلك لامتلاكه نفس التعقيد الحسابي الموجود في خوارزمية [[تصنيف (عام)|ترتيب]] النقاط، باستخدام الإسقاط التالي: لكل مجموعة من الارقام المراد ترتيبها <math>x_1,\dots,x_n</math> نقوم بإنشاء النقاط التالية في فضاء ثنائي الابعاد <math>(x_1, x^2_1),\dots,(x_n, x^2_n)</math>
ولأن كل نقطة من هذه النقاط تقع على [[قطع مكافئ|القطع المكافئ]] و الذي يعد بطبيعته [[دالة محدبة|منحنى محدب]] فانه من السهل ايجاد النقاط التي شكلت الهيكل المحدب حيث تكون على طول حدود القطع المكافئ، و التي يمكن الحصول عليها من خلال ترتيب الأرقام <math>x_1,\dots,x_n</math> . و من الواضح ان عملية تحويل الارقام لنقاط تستهلك و[[تعقيد الوقت|قتا يمكن تمثيله بمنحنى خطي]]، وهذا يؤكد على عدم امكانية حساب الهيكل المحدب لمجموعة من النقاط في الحالة العامة بوقت اسرع من وقت ترتيب مجموعة من الأرقام.
إن نموذج شجرة القرار (Decision tree model) مستخدم في اثبات أن الحد الادنى من التعقيد الحسابي المطلوب لترتيب مجموعة من الأرقام هو Ω ( ''n'' log ''n'' ). و يجب التنويه هنا إلى أن هذا التعقيد الحسابي مرتبط فقط بعمليات المقارنة وليس بالعمليات الحسابية المستخدمة في ترتيب هذه الأرقام. ولكن لا يمكن أبدا استخدام هذه الطريقة لحساب الهياكل المحدبة. ولذلك فان الطريقة الأكثر ملائمة لحساب الهيكل المحدب بنفس التعقيد الحسابي هي شجرة القرار الجبري (algebraic decision tree model) <ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>
و نتيجة لأن نماذج حسابات الكمبيوتر التي تسمح بترتيب مجموعة من الارقام في وقت حسابي اسرع من ''O''( ''n'' log ''n'' ) ،مثل استخدام خوارزمية ترتيب الاعداد الصحيحة، فإن حساب الهياكل المحدبة المستوية يمكن ايجادها بطريقة أسرع: كخوارزمية جرهام للبحث Graham scan algorithm المكونة من عملية ترتيب واحدة متبوعة بعمل إضافي يمكن تمثيله بوقت حسابي خطي.
=== الخوارزميات المعتمدة على المخرجات ===
يمكن تصنيف التعقيد الحسابي لبناء الهيكل المحدب بناءً على: عدد النقاط المدخلة - والتي ذكرنا سابقاً أن الحد الأدنى لتعقيدها الحسابي يمكن حصره ب (Ω ( ''n'' log ''n'' - أو على عدد النقاط التي ستشكل الهيكل المحدب (h) و يمكن تسميتها ب بالخوارزميات المعتمدة على المخرجات و التي تستهلك تعقيد حسابي أكثر فاعلية من Θ ( ''n'' log ''n'' ) في حال كان h=o(n).
ان الحد الأدنى [[تحليل الخوارزميات|للتعقيد الزمني]] في أسوأ حالة لخوارزميات الهيكل المحدب المعتمدة على المخرجات هي Ω (n log h) في فضاء ثنائي الأبعاد.<ref name="ps" /> و هناك العديد من الخوارزميات تصل لهذا الحد الأدنى من التعقيد الزمني. وقد تم تقديم أقدمها بواسطة (كركباترك وسايدل) [[ديفيد جي. كيركباتريك|Kirkpatrick]] و[[رايموند زايدل|Seidel]] في عام 1986 (الذين أطلقوا عليها اسم خوارزمية الهيكل المحدب القصوى. (the ultimate convex hull algorithm) ). ومن ثم تم تطوير خوارزمية أبسط بكثير بواسطة (شان) Chan في عام 1996، و سميت على اسمه ( خوارزمية Chan).
=== خوارزميات الهيكل المحدب ===
خوارزميات الهيكل المحدب المدرجة أدناه مرتبة حسب تاريخ نشرها الأول. و نجد أن التعقيد الحسابي لكل خوارزمية قد مُثِل بعدد النقاط المدخلة n وعدد نقاط الهيكل المحدب h.
ملاحظة: قد تكون ''h'' مساوية ل ''n في أسوأ الحالات.''
* خوارزمية '''جارفيس مارس''' او (خوارزمية '''تغليف الهدايا''') – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الاكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 و تبعهم آر جارفيس في عام 1973 [[تحليل الخوارزميات|بتعقيد زمني]] يقدر ب<nowiki/>[[تمثيل O الكبرى|O]](nh). و في أسوأ الحالات يكون [[تمثيل O الكبرى|Θ]] (n ''<sup>2</sup>'').
* خوارزمية '''جراهام''' – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما ، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل [[رونالد غراهام|رونالد جراهام]] في عام 1972. و تستغرق وقتاً يقدر بO ( ''n'' ) في حال كانت النقاط المدخلة مرتبة بناء على احد الاحداثيات او بناء على متجه ثابت.
* خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 و أ. بيكات 1978. و كخوارزمية الترتيب السريع (Quick sort) فان تعقيدها الزمني هو O(n log n) و من الممكن ان تتراجع لتصل الى ''O'' ( ''n'' <sup>2</sup> ) في أسوء الحالات.
* خوارزمية '''فرق تسد''' – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ و فرانكو بريراتا (Franco Preparata and Hong) بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.
* خوارزمية اندرو ('''[[wikibooks:Algorithm Implementation/Geometry/Convex hull/Monotone chain|السلسلة الرتيبة]]''') – O(n log n) تم نشر هذه الخوارزمية عام 1979 بواسطة اندرو AM Andrew. و يمكن اعتبار هذه الخوارزمية كنوع من خوارزمية جراهام ، التي ترتب النقاط من خلال إحداثياتها. و إذا تم ترتيب النقاط المدخلة فإن الخوارزمية تستغرق وقتاً يقدر ب O (n).
* '''خوارزمية''' '''الهيكل''' '''المحدب''' '''المتزايد''' - O (n log n) تم صايغتها عام 1984 بواسطة مايكل كاليMichael Kallay.
* '''خوارزمية كيركباتريك - سيدل''' - ''O'' ( ''n'' log ''h'' ) هي أول خوارزمية من الخوارزميات المعتمدة على المخرجات و تستخدم تقنية "marriage-before-conquest" في البرمجة الخطية محدودة الأبعاد. وقد تم نشرها بواسطة [[ديفيد جي. كيركباتريك|Kirkpatrick]] and [[رايموند زايدل|Seidel]] عام 1986.
* '''خوارزمية تشان''' - O (n log h) نشرها تيموثي تشين في عام 1996. وهي خوارزمية مثلى من الخوارزميات المعتمدة على المخرجات وتعد أبسط من سابقاتها. و تدمج بين خوارزمية جارفيس واي خوارزمية تستغرق وقتا يقدر ب O(n log n) -مثل خوارزمية جرهام - .
=== '''استدلال توسان و عقل''' ===
غالبًا ما يتم استخدام الاستدلال البسيط التالي كخطوة أولى في تنفيذ خوارزميات الهيكل المحدب لتحسين الأداء. وقد قام<nowiki/>[[سليم عقل]] و توسان باستحداث طريقة فعالة لايجاد الهيكل المحدب و تعتمد هذه الطريقة على استبعاد اكبر عدد ممكن من النقاط التي لا يمكن ان تشكل الهيكل المحدب من خلال إيجاد النقطتين اللتين تحتويان على أدنى وأعلى إحداثيات في محور x ، و أدنى وأعلى نقطتي إحداث في محور y. (كل من هذه العمليات تستغرق [[تمثيل O الكبرى|O]] (n)) و هذه النقاط الأربع تشكل [[رباعي أضلاع|محدباً رباعياً]] ، و جميع النقاط التي تقع في هذا الرباعي (باستثناء الرؤوس الأربعة المختارة في البداية) ليست جزءًا من الهيكل المحدب أو يمكن أن نضيف الى الشكل الرباعي النقاط التي تحتوي على أصغر وأكبر مجاميع من إحداثيات x و y وكذلك تلك التي تحتوي على أصغر وأكبر اختلافات في إحداثيات x و y ، و هطذا يصبح لدينا محدب ثماني غير منتظم ، ثم نقوم بالتخلص من جميع النقاط التي بداخل الشكل الثماني بأمان.
و إذا كانت النقاط عبارة عن متغيرات عشوائية -وهذا يكون فقط لفئة معينة و شائعة من دوال الكثافة الاحتمالية- فإن عملية التخلص من النقاط التي ذكرناها في الخطوة السابقة ستجعل الخوارزمية تستغرق زمناً خطياً، و حتى في اسوء الحالات فان الوقت المستغرق قد يصل الى ''n'' <sup>2</sup> .<ref>[[Luc Devroye]] and [[Godfried Toussaint]], "A note on linear expected time algorithms for finding convex hulls," ''Computing'', Vol. 26, 1981, pp. 361-366.</ref>
=== '''مشاكل خوارزمية الهيكل المحدب المتغير''' ===
ان في كل ما تم ذكره سابقا كانت النقاط المدخلة معروفة مسبقا، و لذلك فإننا يجب أن نأخذ بعين الاعتبار الخطوتين التاليتين عند بناء الهيكل المحدب:<ref name="ps" />
* '''مشاكل بناء الهيكل المحدب عبر الإنترنت''': حين يتم وصول نقاط الإدخال بالتتابع واحدة تلو الأخرى. سيتم اعادة حساب الهيكل المحدب لمجموعة النقاط الحالية بكفاءة، بعد إدخال كل نقطة.
* '''الصيانة الدورية للهيكل المحدب المتغير''': يجب تحديث الهيكل المحدب بعد كل عملية إدخال أو حذف. وذلك لإمكانية ادخال النقاط و حذفها بالتسلسل.
قد يؤدي إدخال نقطة إلى زيادة عدد رؤوس الهيكل محدب بمقدار 1 على الأكثر ، والعكس صحيح بالنسبة للحذف.
يمكن التعامل مع النقاط المدخلة للهيكل المحدب عبر الإنترنت خلال وقت يقدر ب O (log n) لكل نقطة ، و هذا على أفضل تقدير. و يمكن التعامل مع النقاط المدخلة للهيكل المحدب المتغير خلال وقت يقدر ب O (log <sup>2</sup> ''n'' ) لكل عملية.<ref name="ps" />
=== المضلع البسيط ([[مضلع بسيط]]) ===
يتم تقسيم الهيكل المحدب [[مضلع بسيط|لمضلع بسيط]] إلى أجزاء من خلال جعل أحدها هو المضلع نفسه و أما باقي الهيكل فعبارة عن ''جيوب'' تحدها قطعة من حدود المضلع وحافة واحدة من الهيكل. على الرغم من نشر العديد من الخوارزميات لبناء الهيكل المحدب لمضلع بسيط ، فإن نصفها تقريبًا غير صحيح.<ref>{{استشهاد ويب
| مسار = http://cgm.cs.mcgill.ca/~athens/cs601/
| عنوان = A History of Linear-time Convex Hull Algorithms for Simple Polygons
| تاريخ الوصول = October 11, 2020
| الأخير = Aloupis
| الأول = Greg
}}</ref> ويعد مكالوم وآفيس أول من قدم خوارزمية صحيحة.<ref>{{استشهاد|الأخير=McCallum|الأول=Duncan|مؤلف-الأخير2=Avis|مؤلف-الأول2=David|وصلة-مؤلف2=David Avis|DOI=10.1016/0020-0190(79)90069-3|العدد=5|صحيفة=[[Information Processing Letters]]|mr=552534|صفحات=201–206|عنوان=A linear algorithm for finding the convex hull of a simple polygon|المجلد=9|سنة=1979}}</ref> وقد استخدم جرهام و ياو ( {{Harvard citation text|Graham|Yao|1983}} ) و لي ({{Harvard citation text|Lee|1983}}) [[مكدس (بنية بيانات)|بنية بيانات المكدس]] (stack data structure ) واحدة من أجل تبسيط الخوارزمية وتسير هذه الخوارزمية على المضلع في اتجاه عقارب الساعة ، بدءً من النقطة الواقعة أقصى اليسار وخلال ذلك تقوم بتخزين النقاط الموجودة على المحدب ( تلك التي لم يتم تحديدها بعد على أنها داخل الجيوب) في المكدس. في كل خطوة ، تتبع الخوارزمية مسارًا على طول المضلع من قمة المكدس إلى النقطة التالية على ألا تكون ضمن أحد الجيوب المجاورة لأعلى المكدس. و طالما أن اخر نقطتين في أعلى المكدس لا يشكلان محدبا مع النقطة الجديدة نقوم بعملية اخراج النقطة العلوية من المكدس ، ثم ادخال النقطة الجديدة. عندما تنتهي دورة قراءة الخوارزمية للنقاط في اتجاه عقارب الساعة نكون قد عدنا إلى نقطة البداية، وهنا ستكون نتيجة الخوارزمية عبارة عن تسلسل النقاط الموجودة في المكدس وهي ذاتها نقاط المكونة الهيكل.<ref>{{استشهاد|الأخير=Graham|الأول=Ronald L.|وصلة مؤلف=Ronald Graham|مؤلف-الأخير2=Yao|مؤلف-الأول2=F. Frances|وصلة-مؤلف2=Frances Yao|DOI=10.1016/0196-6774(83)90013-5|العدد=4|صحيفة=[[إلزيفير]]|mr=729228|صفحات=324–331|عنوان=Finding the convex hull of a simple polygon|المجلد=4|سنة=1983}}</ref><ref>{{استشهاد|الأخير=Lee|الأول=D. T.|DOI=10.1007/BF00993195|العدد=2|صحيفة=International Journal of Computer and Information Sciences|mr=724699|صفحات=87–98|عنوان=On finding the convex hull of a simple polygon|المجلد=12|سنة=1983}}</ref>
== أنظر أيضا ==
* بدن محدب متعامد
== مراجع ==
{{مراجع}}
== قراءة متعمقة ==
* توماس إتش كورمن ، تشارلز إي ليسرسون ، [[رونالد ريفست|رونالد إل ريفيست]] ، [[كليفورد شتاين|وكليفورد شتاين]] . ''[[مقدمة في الخوارزميات (كتاب)|مقدمة في الخوارزميات]]'' ، الإصدار الثاني. مطبعة معهد ماساتشوستس للتكنولوجيا ومكجرو هيل ، 2001.{{ردمك|0-262-03293-7}}[[النظام القياسي الدولي لترقيم الكتب|رقم ISBN]] [[خاص:BookSources/0-262-03293-7|0-262-03293-7]] . القسم 33.3: العثور على بدن محدب ، ص. 947-957 –
* فرانكو ب .بيراتا ، إس جيه هونغ . ''هياكل محدبة من مجموعات محدودة من النقاط في بعدين وثلاثة أبعاد'' ، Commun. ACM ، المجلد. 20 ، لا. 2 ، ص. 87-93 – 1977.
* <bdi><cite class="citation book cs1" data-ve-ignore="true" id="CITEREFMark_de_BergMarc_van_KreveldMark_OvermarsOtfried_Schwarzkopf2000">[[خاص: BookSources / 978-3-540-65620-3|978-3-540-65620-3]]</cite></bdi> القسم 1.1: مثال: أجسام محدبة (يصف الخوارزميات الكلاسيكية للأجسام المحدبة ثنائية الأبعاد). الفصل 11: هياكل محدبة: ص. 235-250 – يصف خوارزمية عشوائية لهياكل محدبة ثلاثية الأبعاد بسبب كلاركسون وشور).
== روابط خارجية ==
* <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>Weisstein, Eric W. "Convex Hull". MathWorld.
* [http://www.cgal.org/Part/ConvexHullAlgorithms 2D, 3D, and dD Convex Hull] in CGAL, the Computational Geometry Algorithms Library
* [http://www.qhull.org/ Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection]
* [https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html Demo as Flash swf], Jarvis, Graham, Quick (divide and conquer) and Chan algorithms
* [http://wayback.vefsafn.is/wayback/20130721095350/http://michal.is/projects/convex%2Dhull%2Dgift%2Dwrapping%2Dmethod/ Gift wrapping algorithm in C#]
{{شريط بوابات|رياضيات}}
{{غير مصنفة|تاريخ=نوفمبر 2022}}' |
نص الويكي الجديد للصفحة، بعد التعديل (new_wikitext) | '[[ملف:Envoltura convexa de puntos.png|تصغير|الهيكل المحدب لمجموعة من النقاط]]
إن الخوارزميات التي تبني هياكلاً [[انغلاق محدب|محدبة]] (convex hull) لها العديد من الاستخدامات [[انغلاق محدب|الواسعة]] في [[رياضيات|الرياضيات]] [[علم الحاسوب|وعلوم الحاسوب]].
في [[هندسة رياضية حاسوبية|الهندسة الحسابية]] ، تم اقتراح العديد من الخوارزميات لحساب الهيكل المحدب لمجموعة نقاط محددة، وكل خوارزمية من هذه الخوارزميات لها درجة مختلفة من [[تحليل الخوارزميات|تعقيد العمليات الحسابية]].
إن خوارزمية الهيكل المحدب تمثل الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة و واضحة و من الممكن تقدير تعقيد هذه الخوارزميات ب ''n'' والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. او من الممكن تقديرها ب ''h'' والتي تمثل عدد النقاط على حدود الهيكل المحدب.
.
== الحالة المستوية لبناء الهيكل المحدب ==
في البداية لنعتبر أن الحالة العامة لبناء الهيكل المحدب تكون مدخلاتها عبارة عن مجموعة محددة غير مرتبة من النقاط على مستوى ديكارت. وهناك حالة خاصة للمدخلات سيأتي فيما بعد توضيحها بحيث تكون فيها النقاط المدخلة مرتبة على حدود مضلع بسيط.
إذا لم تكن جميع النقاط على نفس الخط، فإن الهيكل المحدب يكون [[مضلع محدب|مضلعًا محدبًا]] رؤسه تكون أحد هذه النقاط. واكثر هذه الحلات شيوعا هي عندما تكون نقاط الهيكل المضلع مرتبة على طول حدوده في اتجاه عقارب الساعة أو عكس عقارب الساعة. و في بعض التطبيقات يكون من الملائم تمثيل مضلع محدب كتقاطع لمجموعة من أنصاف المستويات .
=== الحد الأدنى من التعقيد الحسابي ===
إن معرفة التعقيد الحسابي لبناء الهيكل المحدب المضلع لمجموعة من النقاط في فضاء ثنائي الابعاد، يتم تمثيله بسهولة وذلك لامتلاكه نفس التعقيد الحسابي الموجود في خوارزمية [[تصنيف (عام)|ترتيب]] النقاط، باستخدام الإسقاط التالي: لكل مجموعة من الارقام المراد ترتيبها <math>x_1,\dots,x_n</math> نقوم بإنشاء النقاط التالية في فضاء ثنائي الابعاد <math>(x_1, x^2_1),\dots,(x_n, x^2_n)</math>
ولأن كل نقطة من هذه النقاط تقع على [[قطع مكافئ|القطع المكافئ]] و الذي يعد بطبيعته [[دالة محدبة|منحنى محدب]] فانه من السهل ايجاد النقاط التي شكلت الهيكل المحدب حيث تكون على طول حدود القطع المكافئ، و التي يمكن الحصول عليها من خلال ترتيب الأرقام <math>x_1,\dots,x_n</math> . و من الواضح ان عملية تحويل الارقام لنقاط تستهلك و<nowiki/>[[تعقيد الوقت|قتا يمكن تمثيله بمنحنى خطي]]، وهذا يؤكد على عدم امكانية حساب الهيكل المحدب لمجموعة من النقاط في الحالة العامة بوقت اسرع من وقت ترتيب مجموعة من الأرقام.
إن نموذج شجرة القرار (Decision tree model) مستخدم في اثبات أن الحد الادنى من التعقيد الحسابي المطلوب لترتيب مجموعة من الأرقام هو Ω ( ''n'' log ''n'' ). و يجب التنويه هنا إلى أن هذا التعقيد الحسابي مرتبط فقط بعمليات المقارنة وليس بالعمليات الحسابية المستخدمة في ترتيب هذه الأرقام. ولكن لا يمكن أبدا استخدام هذه الطريقة لحساب الهياكل المحدبة. ولذلك فان الطريقة الأكثر ملائمة لحساب الهيكل المحدب بنفس التعقيد الحسابي هي شجرة القرار الجبري (algebraic decision tree model) <ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>
و نتيجة لأن [[نموذج حوسبة|نماذج حسابات الكمبيوتر]] التي تسمح بترتيب مجموعة من الارقام في وقت حسابي اسرع من ''O''( ''n'' log ''n'' ) ،مثل استخدام خوارزمية ترتيب الاعداد الصحيحة، فإن حساب الهياكل المحدبة المستوية يمكن ايجادها بطريقة أسرع: كخوارزمية جرهام للبحث Graham scan algorithm المكونة من عملية ترتيب واحدة متبوعة بعمل إضافي يمكن تمثيله بوقت حسابي خطي.
=== الخوارزميات المعتمدة على المخرجات ===
يمكن تصنيف التعقيد الحسابي لبناء الهيكل المحدب بناءً على: عدد النقاط المدخلة - والتي ذكرنا سابقاً أن الحد الأدنى لتعقيدها الحسابي يمكن حصره ب (Ω ( ''n'' log ''n'' - أو على عدد النقاط التي ستشكل الهيكل المحدب (h) و يمكن تسميتها ب بالخوارزميات المعتمدة على المخرجات و التي تستهلك تعقيد حسابي أكثر فاعلية من Θ ( ''n'' log ''n'' ) في حال كان h=o(n).
ان الحد الأدنى [[تحليل الخوارزميات|للتعقيد الزمني]] في أسوأ حالة لخوارزميات الهيكل المحدب المعتمدة على المخرجات هي Ω (n log h) في فضاء ثنائي الأبعاد<ref name="ps" />. و هناك العديد من الخوارزميات تصل لهذا الحد الأدنى من التعقيد الزمني. وقد تم تقديم أقدمها بواسطة (كركباترك وسايدل) [[ديفيد جي. كيركباتريك|Kirkpatrick]] و [[رايموند زايدل|Seidel]] في عام 1986 (الذين أطلقوا عليها اسم خوارزمية الهيكل المحدب القصوى. (The ultimate convex hull algorithm) ). ومن ثم تم تطوير خوارزمية أبسط بكثير بواسطة (شان) Chan في عام 1996، و سميت على اسمه ( خوارزمية Chan).
=== خوارزميات الهيكل المحدب ===
خوارزميات الهيكل المحدب المدرجة أدناه مرتبة حسب تاريخ نشرها الأول. و نجد أن التعقيد الحسابي لكل خوارزمية قد مُثِل بعدد النقاط المدخلة n وعدد نقاط الهيكل المحدب h.
ملاحظة: قد تكون ''h'' مساوية ل ''n في أسوأ الحالات.''
* خوارزمية '''جارفيس مارس''' او ([[:en:Gift_wrapping_algorithm|خوارزمية '''تغليف الهدايا''']]) – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الاكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 و تبعهم آر جارفيس في عام 1973 [[تحليل الخوارزميات|بتعقيد زمني]] يقدر ب<nowiki/>[[تمثيل O الكبرى|O]](nh). و في أسوأ الحالات يكون [[تمثيل O الكبرى|Θ]] (n ''<sup>2</sup>'').
* خوارزمية '''جراهام''' – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما ، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل [[رونالد غراهام|رونالد جراهام]] في عام 1972. و تستغرق وقتاً يقدر بO ( ''n'' ) في حال كانت النقاط المدخلة مرتبة بناء على احد الاحداثيات او بناء على متجه ثابت.
* خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 و أ. بيكات 1978. و كخوارزمية الترتيب السريع (Quick sort) فان تعقيدها الزمني هو O(n log n) و من الممكن ان تتراجع لتصل الى ''O'' ( ''n'' <sup>2</sup> ) في أسوء الحالات.
* خوارزمية '''[[خوارزمية فرق تسد|فرق تسد]]''' – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ و فرانكو بريراتا (Franco Preparata and Hong) بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.
* خوارزمية اندرو ('''[[wikibooks:Algorithm Implementation/Geometry/Convex hull/Monotone chain|السلسلة الرتيبة]]''') – O(n log n) تم نشر هذه الخوارزمية عام 1979 بواسطة اندرو AM Andrew. و يمكن اعتبار هذه الخوارزمية كنوع من خوارزمية جراهام ، التي ترتب النقاط من خلال إحداثياتها. و إذا تم ترتيب النقاط المدخلة فإن الخوارزمية تستغرق وقتاً يقدر ب O (n).
* '''خوارزمية''' '''الهيكل''' '''المحدب''' '''المتزايد''' - O (n log n) تم صايغتها عام 1984 بواسطة مايكل كاليMichael Kallay.
* '''خوارزمية كيركباتريك - سيدل''' - ''O'' ( ''n'' log ''h'' ) هي أول خوارزمية من الخوارزميات المعتمدة على المخرجات و تستخدم تقنية "marriage-before-conquest" في البرمجة الخطية محدودة الأبعاد. وقد تم نشرها بواسطة [[ديفيد جي. كيركباتريك|Kirkpatrick]] and [[رايموند زايدل|Seidel]] عام 1986.
* '''خوارزمية تشان''' - O (n log h) نشرها تيموثي تشين في عام 1996. وهي خوارزمية مثلى من الخوارزميات المعتمدة على المخرجات وتعد أبسط من سابقاتها. و تدمج بين خوارزمية جارفيس واي خوارزمية تستغرق وقتا يقدر ب O(n log n) -مثل خوارزمية جرهام - .
=== '''استدلال توسان و عقل''' ===
غالبًا ما يتم استخدام الاستدلال البسيط التالي كخطوة أولى في تنفيذ خوارزميات الهيكل المحدب لتحسين الأداء. وقد قام [[سليم عقل]] و توسان باستحداث طريقة فعالة لايجاد الهيكل المحدب و تعتمد هذه الطريقة على استبعاد اكبر عدد ممكن من النقاط التي لا يمكن ان تشكل الهيكل المحدب من خلال إيجاد النقطتين اللتين تحتويان على أدنى وأعلى إحداثيات في محور x ، و أدنى وأعلى نقطتي إحداث في محور y. (كل من هذه العمليات تستغرق [[تمثيل O الكبرى|O]](n)) و هذه النقاط الأربع تشكل [[رباعي أضلاع|محدباً رباعياً]] ، و جميع النقاط التي تقع في هذا الرباعي (باستثناء الرؤوس الأربعة المختارة في البداية) ليست جزءًا من الهيكل المحدب أو يمكن أن نضيف الى الشكل الرباعي النقاط التي تحتوي على أصغر وأكبر مجاميع من إحداثيات x و y وكذلك تلك التي تحتوي على أصغر وأكبر اختلافات في إحداثيات x و y ، و هطذا يصبح لدينا محدب ثماني غير منتظم ، ثم نقوم بالتخلص من جميع النقاط التي بداخل الشكل الثماني بأمان.
و إذا كانت النقاط عبارة عن متغيرات عشوائية -وهذا يكون فقط لفئة معينة و شائعة من دوال الكثافة الاحتمالية- فإن عملية التخلص من النقاط التي ذكرناها في الخطوة السابقة ستجعل الخوارزمية تستغرق زمناً خطياً، و حتى في اسوء الحالات فان الوقت المستغرق قد يصل الى ''n'' <sup>2</sup> .<ref>[[Luc Devroye]] and [[Godfried Toussaint]], "A note on linear expected time algorithms for finding convex hulls," ''Computing'', Vol. 26, 1981, pp. 361-366.</ref>
=== '''مشاكل خوارزمية الهيكل المحدب المتغير والفوري''' ===
ان في كل ما تم ذكره سابقا كانت النقاط المدخلة معروفة مسبقا، و لذلك فإننا يجب أن نأخذ بعين الاعتبار الخطوتين التاليتين عند بناء الهيكل المحدب:<ref name="ps" />
* '''مشاكل بناء الهيكل المحدب [[خوارزمية فورية|الفوري]]''': حين يتم وصول نقاط الإدخال بالتتابع واحدة تلو الأخرى. سيتم اعادة حساب الهيكل المحدب لمجموعة النقاط الحالية بكفاءة، بعد إدخال كل نقطة.
* '''الصيانة الدورية للهيكل المحدب المتغير''': يجب تحديث الهيكل المحدب بعد كل عملية إدخال أو حذف. وذلك لإمكانية ادخال النقاط و حذفها بالتسلسل.
قد يؤدي إدخال نقطة إلى زيادة عدد رؤوس الهيكل محدب بمقدار 1 على الأكثر ، والعكس صحيح بالنسبة للحذف.
يمكن التعامل مع النقاط المدخلة للهيكل المحدب عبر الإنترنت خلال وقت يقدر ب O (log n) لكل نقطة ، و هذا على أفضل تقدير. و يمكن التعامل مع النقاط المدخلة للهيكل المحدب المتغير خلال وقت يقدر ب O (log <sup>2</sup> ''n'' ) لكل عملية. <ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>
=== المضلع البسيط ([[Simple polygon|Simple Polygon]]) ===
يتم تقسيم الهيكل المحدب [[مضلع بسيط|لمضلع بسيط]] إلى أجزاء من خلال جعل أحدها هو المضلع نفسه و أما باقي الهيكل فعبارة عن ''جيوب'' تحدها قطعة من حدود المضلع وحافة واحدة من الهيكل. على الرغم من نشر العديد من الخوارزميات لبناء الهيكل المحدب لمضلع بسيط ، فإن نصفها تقريبًا غير صحيح. <ref>{{استشهاد ويب
| url = http://cgm.cs.mcgill.ca/~athens/cs601/
| title = A History of Linear-time Convex Hull Algorithms for Simple Polygons
| accessdate = October 11, 2020
| last = Aloupis
| first = Greg
}}</ref> ويعد مكالوم وآفيس أول من قدم خوارزمية صحيحة. <ref>{{استشهاد|last=McCallum|first=Duncan|last2=Avis|first2=David|author2-link=David Avis|DOI=10.1016/0020-0190(79)90069-3|number=5|journal=[[Information Processing Letters]]|mr=552534|pages=201–206|title=A linear algorithm for finding the convex hull of a simple polygon|volume=9|year=1979}}</ref> وقد استخدم جرهام و ياو ( {{Harvard citation text|Graham|Yao|1983}} ) و لي ({{Harvard citation text|Lee|1983}}) [[مكدس (بنية بيانات)|بنية بيانات المكدس]] (stack data structure ) واحدة من أجل تبسيط الخوارزمية وتسير هذه الخوارزمية على المضلع في اتجاه عقارب الساعة ، بدءً من النقطة الواقعة أقصى اليسار وخلال ذلك تقوم بتخزين النقاط الموجودة على المحدب ( تلك التي لم يتم تحديدها بعد على أنها داخل الجيوب) في المكدس. في كل خطوة ، تتبع الخوارزمية مسارًا على طول المضلع من قمة المكدس إلى النقطة التالية على ألا تكون ضمن أحد الجيوب المجاورة لأعلى المكدس. و طالما أن اخر نقطتين في أعلى المكدس لا يشكلان محدبا مع النقطة الجديدة نقوم بعملية اخراج النقطة العلوية من المكدس ، ثم ادخال النقطة الجديدة. عندما تنتهي دورة قراءة الخوارزمية للنقاط في اتجاه عقارب الساعة نكون قد عدنا إلى نقطة البداية، وهنا ستكون نتيجة الخوارزمية عبارة عن تسلسل النقاط الموجودة في المكدس وهي ذاتها نقاط المكونة الهيكل. <ref>{{استشهاد|last=Graham|first=Ronald L.|author-link=Ronald Graham|last2=Yao|first2=F. Frances|author2-link=Frances Yao|DOI=10.1016/0196-6774(83)90013-5|number=4|journal=[[Journal of Algorithms]]|mr=729228|pages=324–331|title=Finding the convex hull of a simple polygon|volume=4|year=1983}}</ref> <ref>{{استشهاد|last=Lee|first=D. T.|DOI=10.1007/BF00993195|number=2|journal=International Journal of Computer and Information Sciences|mr=724699|pages=87–98|title=On finding the convex hull of a simple polygon|volume=12|year=1983}}</ref>
== المراجع ==
{{مراجع}}
== قراءة متعمقة ==
* توماس إتش كورمن ، تشارلز إي ليسرسون ، [[رونالد ريفست|رونالد إل ريفيست]] ، [[كليفورد شتاين|وكليفورد شتاين]] . ''[[مقدمة في الخوارزميات (كتاب)|مقدمة في الخوارزميات]]'' ، الإصدار الثاني. مطبعة معهد ماساتشوستس للتكنولوجيا ومكجرو هيل ، 2001.{{ردمك|0-262-03293-7}}[[ISBN (identifier)|رقم ISBN]] [[Special:BookSources/0-262-03293-7|0-262-03293-7]] . القسم 33.3: العثور على بدن محدب ، ص. 947-957 –
* فرانكو ب .بيراتا ، إس جيه هونغ . ''هياكل محدبة من مجموعات محدودة من النقاط في بعدين وثلاثة أبعاد'' ، Commun. ACM ، المجلد. 20 ، لا. 2 ، ص. 87-93 – 1977.
* <bdi><cite class="citation book cs1" data-ve-ignore="true" id="CITEREFMark_de_BergMarc_van_KreveldMark_OvermarsOtfried_Schwarzkopf2000">[[خاص: BookSources / 978-3-540-65620-3|978-3-540-65620-3]]</cite></bdi> القسم 1.1: مثال: أجسام محدبة (يصف الخوارزميات الكلاسيكية للأجسام المحدبة ثنائية الأبعاد). الفصل 11: هياكل محدبة: ص. 235-250 – يصف خوارزمية عشوائية لهياكل محدبة ثلاثية الأبعاد بسبب كلاركسون وشور).
== روابط خارجية ==
{{ويكي الكتب|Algorithm Implementation|Geometry/Convex hull|Convex hull}}
* <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>Weisstein, Eric W. "Convex Hull". MathWorld.
* [http://www.cgal.org/Part/ConvexHullAlgorithms 2D, 3D, and dD Convex Hull] in CGAL, the Computational Geometry Algorithms Library
* [http://www.qhull.org/ Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection]
* [https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html Demo as Flash swf], Jarvis, Graham, Quick (divide and conquer) and Chan algorithms
* [http://wayback.vefsafn.is/wayback/20130721095350/http://michal.is/projects/convex%2Dhull%2Dgift%2Dwrapping%2Dmethod/ Gift wrapping algorithm in C#]' |
فرق موحد للتغييرات المصنوعة بواسطة التعديل (edit_diff) | '@@ -1,92 +1,85 @@
-{{مقالة غير مراجعة|تاريخ = نوفمبر 2022}}
-{{يتيمة|تاريخ=نوفمبر 2022}}
-
-إن الخوارزميات التي تبني هياكلاً [[انغلاق محدب|محدبة]] (convex hull) لها العديد من الاستخدامات [[انغلاق محدب|الواسعة]] في [[رياضيات|الرياضيات]] [[علم الحاسوب|وعلوم الحاسوب]].
+[[ملف:Envoltura convexa de puntos.png|تصغير|الهيكل المحدب لمجموعة من النقاط]]
+إن الخوارزميات التي تبني هياكلاً [[انغلاق محدب|محدبة]] (convex hull) لها العديد من الاستخدامات [[انغلاق محدب|الواسعة]] في [[رياضيات|الرياضيات]] [[علم الحاسوب|وعلوم الحاسوب]].
في [[هندسة رياضية حاسوبية|الهندسة الحسابية]] ، تم اقتراح العديد من الخوارزميات لحساب الهيكل المحدب لمجموعة نقاط محددة، وكل خوارزمية من هذه الخوارزميات لها درجة مختلفة من [[تحليل الخوارزميات|تعقيد العمليات الحسابية]].
-إن خوارزمية الهيكل المحدب [[بنية بيانات|تمثل]] الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة و واضحة و من الممكن تقدير تعقيد هذه الخوارزميات ب ''n'' والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. او من الممكن تقديرها ب ''h'' والتي تمثل عدد النقاط على حدود الهيكل المحدب.
+إن خوارزمية الهيكل المحدب تمثل الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة و واضحة و من الممكن تقدير تعقيد هذه الخوارزميات ب ''n'' والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. او من الممكن تقديرها ب ''h'' والتي تمثل عدد النقاط على حدود الهيكل المحدب.
.
== الحالة المستوية لبناء الهيكل المحدب ==
-في البداية لنعتبر ان الحالة العامة لبناء الهيكل المحدب تكون مدخلاتها عبارة عن مجموعة محددة غير مرتبة من النقاط على مستوى ديكارت. وهناك حالة خاصة للمدخلات سيأتي فيما بعد توضيحها بحيث تكون فيها النقاط المدخلة مرتبة على حدود مضلع بسيط.
+في البداية لنعتبر أن الحالة العامة لبناء الهيكل المحدب تكون مدخلاتها عبارة عن مجموعة محددة غير مرتبة من النقاط على مستوى ديكارت. وهناك حالة خاصة للمدخلات سيأتي فيما بعد توضيحها بحيث تكون فيها النقاط المدخلة مرتبة على حدود مضلع بسيط.
إذا لم تكن جميع النقاط على نفس الخط، فإن الهيكل المحدب يكون [[مضلع محدب|مضلعًا محدبًا]] رؤسه تكون أحد هذه النقاط. واكثر هذه الحلات شيوعا هي عندما تكون نقاط الهيكل المضلع مرتبة على طول حدوده في اتجاه عقارب الساعة أو عكس عقارب الساعة. و في بعض التطبيقات يكون من الملائم تمثيل مضلع محدب كتقاطع لمجموعة من أنصاف المستويات .
=== الحد الأدنى من التعقيد الحسابي ===
-إن معرفة التعقيد الحسابي لبناء الهيكل المحدب المضلع لمجموعة من النقاط في فضاء ثنائي الابعاد، يتم تمثيله بسهولة وذلك لامتلاكه نفس التعقيد الحسابي الموجود في خوارزمية [[تصنيف (عام)|ترتيب]] النقاط، باستخدام الإسقاط التالي: لكل مجموعة من الارقام المراد ترتيبها <math>x_1,\dots,x_n</math> نقوم بإنشاء النقاط التالية في فضاء ثنائي الابعاد <math>(x_1, x^2_1),\dots,(x_n, x^2_n)</math>
+إن معرفة التعقيد الحسابي لبناء الهيكل المحدب المضلع لمجموعة من النقاط في فضاء ثنائي الابعاد، يتم تمثيله بسهولة وذلك لامتلاكه نفس التعقيد الحسابي الموجود في خوارزمية [[تصنيف (عام)|ترتيب]] النقاط، باستخدام الإسقاط التالي: لكل مجموعة من الارقام المراد ترتيبها <math>x_1,\dots,x_n</math> نقوم بإنشاء النقاط التالية في فضاء ثنائي الابعاد <math>(x_1, x^2_1),\dots,(x_n, x^2_n)</math>
+
+ولأن كل نقطة من هذه النقاط تقع على [[قطع مكافئ|القطع المكافئ]] و الذي يعد بطبيعته [[دالة محدبة|منحنى محدب]] فانه من السهل ايجاد النقاط التي شكلت الهيكل المحدب حيث تكون على طول حدود القطع المكافئ، و التي يمكن الحصول عليها من خلال ترتيب الأرقام <math>x_1,\dots,x_n</math> . و من الواضح ان عملية تحويل الارقام لنقاط تستهلك و<nowiki/>[[تعقيد الوقت|قتا يمكن تمثيله بمنحنى خطي]]، وهذا يؤكد على عدم امكانية حساب الهيكل المحدب لمجموعة من النقاط في الحالة العامة بوقت اسرع من وقت ترتيب مجموعة من الأرقام.
+
-ولأن كل نقطة من هذه النقاط تقع على [[قطع مكافئ|القطع المكافئ]] و الذي يعد بطبيعته [[دالة محدبة|منحنى محدب]] فانه من السهل ايجاد النقاط التي شكلت الهيكل المحدب حيث تكون على طول حدود القطع المكافئ، و التي يمكن الحصول عليها من خلال ترتيب الأرقام <math>x_1,\dots,x_n</math> . و من الواضح ان عملية تحويل الارقام لنقاط تستهلك و[[تعقيد الوقت|قتا يمكن تمثيله بمنحنى خطي]]، وهذا يؤكد على عدم امكانية حساب الهيكل المحدب لمجموعة من النقاط في الحالة العامة بوقت اسرع من وقت ترتيب مجموعة من الأرقام.
-إن نموذج شجرة القرار (Decision tree model) مستخدم في اثبات أن الحد الادنى من التعقيد الحسابي المطلوب لترتيب مجموعة من الأرقام هو Ω ( ''n'' log ''n'' ). و يجب التنويه هنا إلى أن هذا التعقيد الحسابي مرتبط فقط بعمليات المقارنة وليس بالعمليات الحسابية المستخدمة في ترتيب هذه الأرقام. ولكن لا يمكن أبدا استخدام هذه الطريقة لحساب الهياكل المحدبة. ولذلك فان الطريقة الأكثر ملائمة لحساب الهيكل المحدب بنفس التعقيد الحسابي هي شجرة القرار الجبري (algebraic decision tree model) <ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>
+إن نموذج شجرة القرار (Decision tree model) مستخدم في اثبات أن الحد الادنى من التعقيد الحسابي المطلوب لترتيب مجموعة من الأرقام هو Ω ( ''n'' log ''n'' ). و يجب التنويه هنا إلى أن هذا التعقيد الحسابي مرتبط فقط بعمليات المقارنة وليس بالعمليات الحسابية المستخدمة في ترتيب هذه الأرقام. ولكن لا يمكن أبدا استخدام هذه الطريقة لحساب الهياكل المحدبة. ولذلك فان الطريقة الأكثر ملائمة لحساب الهيكل المحدب بنفس التعقيد الحسابي هي شجرة القرار الجبري (algebraic decision tree model) <ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>
-و نتيجة لأن نماذج حسابات الكمبيوتر التي تسمح بترتيب مجموعة من الارقام في وقت حسابي اسرع من ''O''( ''n'' log ''n'' ) ،مثل استخدام خوارزمية ترتيب الاعداد الصحيحة، فإن حساب الهياكل المحدبة المستوية يمكن ايجادها بطريقة أسرع: كخوارزمية جرهام للبحث Graham scan algorithm المكونة من عملية ترتيب واحدة متبوعة بعمل إضافي يمكن تمثيله بوقت حسابي خطي.
+و نتيجة لأن [[نموذج حوسبة|نماذج حسابات الكمبيوتر]] التي تسمح بترتيب مجموعة من الارقام في وقت حسابي اسرع من ''O''( ''n'' log ''n'' ) ،مثل استخدام خوارزمية ترتيب الاعداد الصحيحة، فإن حساب الهياكل المحدبة المستوية يمكن ايجادها بطريقة أسرع: كخوارزمية جرهام للبحث Graham scan algorithm المكونة من عملية ترتيب واحدة متبوعة بعمل إضافي يمكن تمثيله بوقت حسابي خطي.
=== الخوارزميات المعتمدة على المخرجات ===
-يمكن تصنيف التعقيد الحسابي لبناء الهيكل المحدب بناءً على: عدد النقاط المدخلة - والتي ذكرنا سابقاً أن الحد الأدنى لتعقيدها الحسابي يمكن حصره ب (Ω ( ''n'' log ''n'' - أو على عدد النقاط التي ستشكل الهيكل المحدب (h) و يمكن تسميتها ب بالخوارزميات المعتمدة على المخرجات و التي تستهلك تعقيد حسابي أكثر فاعلية من Θ ( ''n'' log ''n'' ) في حال كان h=o(n).
+يمكن تصنيف التعقيد الحسابي لبناء الهيكل المحدب بناءً على: عدد النقاط المدخلة - والتي ذكرنا سابقاً أن الحد الأدنى لتعقيدها الحسابي يمكن حصره ب (Ω ( ''n'' log ''n'' - أو على عدد النقاط التي ستشكل الهيكل المحدب (h) و يمكن تسميتها ب بالخوارزميات المعتمدة على المخرجات و التي تستهلك تعقيد حسابي أكثر فاعلية من Θ ( ''n'' log ''n'' ) في حال كان h=o(n).
-ان الحد الأدنى [[تحليل الخوارزميات|للتعقيد الزمني]] في أسوأ حالة لخوارزميات الهيكل المحدب المعتمدة على المخرجات هي Ω (n log h) في فضاء ثنائي الأبعاد.<ref name="ps" /> و هناك العديد من الخوارزميات تصل لهذا الحد الأدنى من التعقيد الزمني. وقد تم تقديم أقدمها بواسطة (كركباترك وسايدل) [[ديفيد جي. كيركباتريك|Kirkpatrick]] و[[رايموند زايدل|Seidel]] في عام 1986 (الذين أطلقوا عليها اسم خوارزمية الهيكل المحدب القصوى. (the ultimate convex hull algorithm) ). ومن ثم تم تطوير خوارزمية أبسط بكثير بواسطة (شان) Chan في عام 1996، و سميت على اسمه ( خوارزمية Chan).
+ان الحد الأدنى [[تحليل الخوارزميات|للتعقيد الزمني]] في أسوأ حالة لخوارزميات الهيكل المحدب المعتمدة على المخرجات هي Ω (n log h) في فضاء ثنائي الأبعاد<ref name="ps" />. و هناك العديد من الخوارزميات تصل لهذا الحد الأدنى من التعقيد الزمني. وقد تم تقديم أقدمها بواسطة (كركباترك وسايدل) [[ديفيد جي. كيركباتريك|Kirkpatrick]] و [[رايموند زايدل|Seidel]] في عام 1986 (الذين أطلقوا عليها اسم خوارزمية الهيكل المحدب القصوى. (The ultimate convex hull algorithm) ). ومن ثم تم تطوير خوارزمية أبسط بكثير بواسطة (شان) Chan في عام 1996، و سميت على اسمه ( خوارزمية Chan).
=== خوارزميات الهيكل المحدب ===
-خوارزميات الهيكل المحدب المدرجة أدناه مرتبة حسب تاريخ نشرها الأول. و نجد أن التعقيد الحسابي لكل خوارزمية قد مُثِل بعدد النقاط المدخلة n وعدد نقاط الهيكل المحدب h.
+خوارزميات الهيكل المحدب المدرجة أدناه مرتبة حسب تاريخ نشرها الأول. و نجد أن التعقيد الحسابي لكل خوارزمية قد مُثِل بعدد النقاط المدخلة n وعدد نقاط الهيكل المحدب h.
-ملاحظة: قد تكون ''h'' مساوية ل ''n في أسوأ الحالات.''
+ملاحظة: قد تكون ''h'' مساوية ل ''n في أسوأ الحالات.''
-* خوارزمية '''جارفيس مارس''' او (خوارزمية '''تغليف الهدايا''') – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الاكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 و تبعهم آر جارفيس في عام 1973 [[تحليل الخوارزميات|بتعقيد زمني]] يقدر ب<nowiki/>[[تمثيل O الكبرى|O]](nh). و في أسوأ الحالات يكون [[تمثيل O الكبرى|Θ]] (n ''<sup>2</sup>'').
-* خوارزمية '''جراهام''' – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما ، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل [[رونالد غراهام|رونالد جراهام]] في عام 1972. و تستغرق وقتاً يقدر بO ( ''n'' ) في حال كانت النقاط المدخلة مرتبة بناء على احد الاحداثيات او بناء على متجه ثابت.
-* خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 و أ. بيكات 1978. و كخوارزمية الترتيب السريع (Quick sort) فان تعقيدها الزمني هو O(n log n) و من الممكن ان تتراجع لتصل الى ''O'' ( ''n'' <sup>2</sup> ) في أسوء الحالات.
-* خوارزمية '''فرق تسد''' – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ و فرانكو بريراتا (Franco Preparata and Hong) بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.
+* خوارزمية '''جارفيس مارس''' او ([[:en:Gift_wrapping_algorithm|خوارزمية '''تغليف الهدايا''']]) – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الاكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 و تبعهم آر جارفيس في عام 1973 [[تحليل الخوارزميات|بتعقيد زمني]] يقدر ب<nowiki/>[[تمثيل O الكبرى|O]](nh). و في أسوأ الحالات يكون [[تمثيل O الكبرى|Θ]] (n ''<sup>2</sup>'').
+* خوارزمية '''جراهام''' – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما ، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل [[رونالد غراهام|رونالد جراهام]] في عام 1972. و تستغرق وقتاً يقدر بO ( ''n'' ) في حال كانت النقاط المدخلة مرتبة بناء على احد الاحداثيات او بناء على متجه ثابت.
+* خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 و أ. بيكات 1978. و كخوارزمية الترتيب السريع (Quick sort) فان تعقيدها الزمني هو O(n log n) و من الممكن ان تتراجع لتصل الى ''O'' ( ''n'' <sup>2</sup> ) في أسوء الحالات.
+* خوارزمية '''[[خوارزمية فرق تسد|فرق تسد]]''' – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ و فرانكو بريراتا (Franco Preparata and Hong) بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.
* خوارزمية اندرو ('''[[wikibooks:Algorithm Implementation/Geometry/Convex hull/Monotone chain|السلسلة الرتيبة]]''') – O(n log n) تم نشر هذه الخوارزمية عام 1979 بواسطة اندرو AM Andrew. و يمكن اعتبار هذه الخوارزمية كنوع من خوارزمية جراهام ، التي ترتب النقاط من خلال إحداثياتها. و إذا تم ترتيب النقاط المدخلة فإن الخوارزمية تستغرق وقتاً يقدر ب O (n).
* '''خوارزمية''' '''الهيكل''' '''المحدب''' '''المتزايد''' - O (n log n) تم صايغتها عام 1984 بواسطة مايكل كاليMichael Kallay.
* '''خوارزمية كيركباتريك - سيدل''' - ''O'' ( ''n'' log ''h'' ) هي أول خوارزمية من الخوارزميات المعتمدة على المخرجات و تستخدم تقنية "marriage-before-conquest" في البرمجة الخطية محدودة الأبعاد. وقد تم نشرها بواسطة [[ديفيد جي. كيركباتريك|Kirkpatrick]] and [[رايموند زايدل|Seidel]] عام 1986.
-* '''خوارزمية تشان''' - O (n log h) نشرها تيموثي تشين في عام 1996. وهي خوارزمية مثلى من الخوارزميات المعتمدة على المخرجات وتعد أبسط من سابقاتها. و تدمج بين خوارزمية جارفيس واي خوارزمية تستغرق وقتا يقدر ب O(n log n) -مثل خوارزمية جرهام - .
+* '''خوارزمية تشان''' - O (n log h) نشرها تيموثي تشين في عام 1996. وهي خوارزمية مثلى من الخوارزميات المعتمدة على المخرجات وتعد أبسط من سابقاتها. و تدمج بين خوارزمية جارفيس واي خوارزمية تستغرق وقتا يقدر ب O(n log n) -مثل خوارزمية جرهام - .
=== '''استدلال توسان و عقل''' ===
-غالبًا ما يتم استخدام الاستدلال البسيط التالي كخطوة أولى في تنفيذ خوارزميات الهيكل المحدب لتحسين الأداء. وقد قام<nowiki/>[[سليم عقل]] و توسان باستحداث طريقة فعالة لايجاد الهيكل المحدب و تعتمد هذه الطريقة على استبعاد اكبر عدد ممكن من النقاط التي لا يمكن ان تشكل الهيكل المحدب من خلال إيجاد النقطتين اللتين تحتويان على أدنى وأعلى إحداثيات في محور x ، و أدنى وأعلى نقطتي إحداث في محور y. (كل من هذه العمليات تستغرق [[تمثيل O الكبرى|O]] (n)) و هذه النقاط الأربع تشكل [[رباعي أضلاع|محدباً رباعياً]] ، و جميع النقاط التي تقع في هذا الرباعي (باستثناء الرؤوس الأربعة المختارة في البداية) ليست جزءًا من الهيكل المحدب أو يمكن أن نضيف الى الشكل الرباعي النقاط التي تحتوي على أصغر وأكبر مجاميع من إحداثيات x و y وكذلك تلك التي تحتوي على أصغر وأكبر اختلافات في إحداثيات x و y ، و هطذا يصبح لدينا محدب ثماني غير منتظم ، ثم نقوم بالتخلص من جميع النقاط التي بداخل الشكل الثماني بأمان.
+غالبًا ما يتم استخدام الاستدلال البسيط التالي كخطوة أولى في تنفيذ خوارزميات الهيكل المحدب لتحسين الأداء. وقد قام [[سليم عقل]] و توسان باستحداث طريقة فعالة لايجاد الهيكل المحدب و تعتمد هذه الطريقة على استبعاد اكبر عدد ممكن من النقاط التي لا يمكن ان تشكل الهيكل المحدب من خلال إيجاد النقطتين اللتين تحتويان على أدنى وأعلى إحداثيات في محور x ، و أدنى وأعلى نقطتي إحداث في محور y. (كل من هذه العمليات تستغرق [[تمثيل O الكبرى|O]](n)) و هذه النقاط الأربع تشكل [[رباعي أضلاع|محدباً رباعياً]] ، و جميع النقاط التي تقع في هذا الرباعي (باستثناء الرؤوس الأربعة المختارة في البداية) ليست جزءًا من الهيكل المحدب أو يمكن أن نضيف الى الشكل الرباعي النقاط التي تحتوي على أصغر وأكبر مجاميع من إحداثيات x و y وكذلك تلك التي تحتوي على أصغر وأكبر اختلافات في إحداثيات x و y ، و هطذا يصبح لدينا محدب ثماني غير منتظم ، ثم نقوم بالتخلص من جميع النقاط التي بداخل الشكل الثماني بأمان.
-و إذا كانت النقاط عبارة عن متغيرات عشوائية -وهذا يكون فقط لفئة معينة و شائعة من دوال الكثافة الاحتمالية- فإن عملية التخلص من النقاط التي ذكرناها في الخطوة السابقة ستجعل الخوارزمية تستغرق زمناً خطياً، و حتى في اسوء الحالات فان الوقت المستغرق قد يصل الى ''n'' <sup>2</sup> .<ref>[[Luc Devroye]] and [[Godfried Toussaint]], "A note on linear expected time algorithms for finding convex hulls," ''Computing'', Vol. 26, 1981, pp. 361-366.</ref>
+و إذا كانت النقاط عبارة عن متغيرات عشوائية -وهذا يكون فقط لفئة معينة و شائعة من دوال الكثافة الاحتمالية- فإن عملية التخلص من النقاط التي ذكرناها في الخطوة السابقة ستجعل الخوارزمية تستغرق زمناً خطياً، و حتى في اسوء الحالات فان الوقت المستغرق قد يصل الى ''n'' <sup>2</sup> .<ref>[[Luc Devroye]] and [[Godfried Toussaint]], "A note on linear expected time algorithms for finding convex hulls," ''Computing'', Vol. 26, 1981, pp. 361-366.</ref>
-=== '''مشاكل خوارزمية الهيكل المحدب المتغير''' ===
+=== '''مشاكل خوارزمية الهيكل المحدب المتغير والفوري''' ===
ان في كل ما تم ذكره سابقا كانت النقاط المدخلة معروفة مسبقا، و لذلك فإننا يجب أن نأخذ بعين الاعتبار الخطوتين التاليتين عند بناء الهيكل المحدب:<ref name="ps" />
-* '''مشاكل بناء الهيكل المحدب عبر الإنترنت''': حين يتم وصول نقاط الإدخال بالتتابع واحدة تلو الأخرى. سيتم اعادة حساب الهيكل المحدب لمجموعة النقاط الحالية بكفاءة، بعد إدخال كل نقطة.
-* '''الصيانة الدورية للهيكل المحدب المتغير''': يجب تحديث الهيكل المحدب بعد كل عملية إدخال أو حذف. وذلك لإمكانية ادخال النقاط و حذفها بالتسلسل.
+* '''مشاكل بناء الهيكل المحدب [[خوارزمية فورية|الفوري]]''': حين يتم وصول نقاط الإدخال بالتتابع واحدة تلو الأخرى. سيتم اعادة حساب الهيكل المحدب لمجموعة النقاط الحالية بكفاءة، بعد إدخال كل نقطة.
+* '''الصيانة الدورية للهيكل المحدب المتغير''': يجب تحديث الهيكل المحدب بعد كل عملية إدخال أو حذف. وذلك لإمكانية ادخال النقاط و حذفها بالتسلسل.
-قد يؤدي إدخال نقطة إلى زيادة عدد رؤوس الهيكل محدب بمقدار 1 على الأكثر ، والعكس صحيح بالنسبة للحذف.
+قد يؤدي إدخال نقطة إلى زيادة عدد رؤوس الهيكل محدب بمقدار 1 على الأكثر ، والعكس صحيح بالنسبة للحذف.
-يمكن التعامل مع النقاط المدخلة للهيكل المحدب عبر الإنترنت خلال وقت يقدر ب O (log n) لكل نقطة ، و هذا على أفضل تقدير. و يمكن التعامل مع النقاط المدخلة للهيكل المحدب المتغير خلال وقت يقدر ب O (log <sup>2</sup> ''n'' ) لكل عملية.<ref name="ps" />
+يمكن التعامل مع النقاط المدخلة للهيكل المحدب عبر الإنترنت خلال وقت يقدر ب O (log n) لكل نقطة ، و هذا على أفضل تقدير. و يمكن التعامل مع النقاط المدخلة للهيكل المحدب المتغير خلال وقت يقدر ب O (log <sup>2</sup> ''n'' ) لكل عملية. <ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>
-=== المضلع البسيط ([[مضلع بسيط]]) ===
-يتم تقسيم الهيكل المحدب [[مضلع بسيط|لمضلع بسيط]] إلى أجزاء من خلال جعل أحدها هو المضلع نفسه و أما باقي الهيكل فعبارة عن ''جيوب'' تحدها قطعة من حدود المضلع وحافة واحدة من الهيكل. على الرغم من نشر العديد من الخوارزميات لبناء الهيكل المحدب لمضلع بسيط ، فإن نصفها تقريبًا غير صحيح.<ref>{{استشهاد ويب
-| مسار = http://cgm.cs.mcgill.ca/~athens/cs601/
-| عنوان = A History of Linear-time Convex Hull Algorithms for Simple Polygons
-| تاريخ الوصول = October 11, 2020
-| الأخير = Aloupis
-| الأول = Greg
-}}</ref> ويعد مكالوم وآفيس أول من قدم خوارزمية صحيحة.<ref>{{استشهاد|الأخير=McCallum|الأول=Duncan|مؤلف-الأخير2=Avis|مؤلف-الأول2=David|وصلة-مؤلف2=David Avis|DOI=10.1016/0020-0190(79)90069-3|العدد=5|صحيفة=[[Information Processing Letters]]|mr=552534|صفحات=201–206|عنوان=A linear algorithm for finding the convex hull of a simple polygon|المجلد=9|سنة=1979}}</ref> وقد استخدم جرهام و ياو ( {{Harvard citation text|Graham|Yao|1983}} ) و لي ({{Harvard citation text|Lee|1983}}) [[مكدس (بنية بيانات)|بنية بيانات المكدس]] (stack data structure ) واحدة من أجل تبسيط الخوارزمية وتسير هذه الخوارزمية على المضلع في اتجاه عقارب الساعة ، بدءً من النقطة الواقعة أقصى اليسار وخلال ذلك تقوم بتخزين النقاط الموجودة على المحدب ( تلك التي لم يتم تحديدها بعد على أنها داخل الجيوب) في المكدس. في كل خطوة ، تتبع الخوارزمية مسارًا على طول المضلع من قمة المكدس إلى النقطة التالية على ألا تكون ضمن أحد الجيوب المجاورة لأعلى المكدس. و طالما أن اخر نقطتين في أعلى المكدس لا يشكلان محدبا مع النقطة الجديدة نقوم بعملية اخراج النقطة العلوية من المكدس ، ثم ادخال النقطة الجديدة. عندما تنتهي دورة قراءة الخوارزمية للنقاط في اتجاه عقارب الساعة نكون قد عدنا إلى نقطة البداية، وهنا ستكون نتيجة الخوارزمية عبارة عن تسلسل النقاط الموجودة في المكدس وهي ذاتها نقاط المكونة الهيكل.<ref>{{استشهاد|الأخير=Graham|الأول=Ronald L.|وصلة مؤلف=Ronald Graham|مؤلف-الأخير2=Yao|مؤلف-الأول2=F. Frances|وصلة-مؤلف2=Frances Yao|DOI=10.1016/0196-6774(83)90013-5|العدد=4|صحيفة=[[إلزيفير]]|mr=729228|صفحات=324–331|عنوان=Finding the convex hull of a simple polygon|المجلد=4|سنة=1983}}</ref><ref>{{استشهاد|الأخير=Lee|الأول=D. T.|DOI=10.1007/BF00993195|العدد=2|صحيفة=International Journal of Computer and Information Sciences|mr=724699|صفحات=87–98|عنوان=On finding the convex hull of a simple polygon|المجلد=12|سنة=1983}}</ref>
+=== المضلع البسيط ([[Simple polygon|Simple Polygon]]) ===
+يتم تقسيم الهيكل المحدب [[مضلع بسيط|لمضلع بسيط]] إلى أجزاء من خلال جعل أحدها هو المضلع نفسه و أما باقي الهيكل فعبارة عن ''جيوب'' تحدها قطعة من حدود المضلع وحافة واحدة من الهيكل. على الرغم من نشر العديد من الخوارزميات لبناء الهيكل المحدب لمضلع بسيط ، فإن نصفها تقريبًا غير صحيح. <ref>{{استشهاد ويب
+| url = http://cgm.cs.mcgill.ca/~athens/cs601/
+| title = A History of Linear-time Convex Hull Algorithms for Simple Polygons
+| accessdate = October 11, 2020
+| last = Aloupis
+| first = Greg
+}}</ref> ويعد مكالوم وآفيس أول من قدم خوارزمية صحيحة. <ref>{{استشهاد|last=McCallum|first=Duncan|last2=Avis|first2=David|author2-link=David Avis|DOI=10.1016/0020-0190(79)90069-3|number=5|journal=[[Information Processing Letters]]|mr=552534|pages=201–206|title=A linear algorithm for finding the convex hull of a simple polygon|volume=9|year=1979}}</ref> وقد استخدم جرهام و ياو ( {{Harvard citation text|Graham|Yao|1983}} ) و لي ({{Harvard citation text|Lee|1983}}) [[مكدس (بنية بيانات)|بنية بيانات المكدس]] (stack data structure ) واحدة من أجل تبسيط الخوارزمية وتسير هذه الخوارزمية على المضلع في اتجاه عقارب الساعة ، بدءً من النقطة الواقعة أقصى اليسار وخلال ذلك تقوم بتخزين النقاط الموجودة على المحدب ( تلك التي لم يتم تحديدها بعد على أنها داخل الجيوب) في المكدس. في كل خطوة ، تتبع الخوارزمية مسارًا على طول المضلع من قمة المكدس إلى النقطة التالية على ألا تكون ضمن أحد الجيوب المجاورة لأعلى المكدس. و طالما أن اخر نقطتين في أعلى المكدس لا يشكلان محدبا مع النقطة الجديدة نقوم بعملية اخراج النقطة العلوية من المكدس ، ثم ادخال النقطة الجديدة. عندما تنتهي دورة قراءة الخوارزمية للنقاط في اتجاه عقارب الساعة نكون قد عدنا إلى نقطة البداية، وهنا ستكون نتيجة الخوارزمية عبارة عن تسلسل النقاط الموجودة في المكدس وهي ذاتها نقاط المكونة الهيكل. <ref>{{استشهاد|last=Graham|first=Ronald L.|author-link=Ronald Graham|last2=Yao|first2=F. Frances|author2-link=Frances Yao|DOI=10.1016/0196-6774(83)90013-5|number=4|journal=[[Journal of Algorithms]]|mr=729228|pages=324–331|title=Finding the convex hull of a simple polygon|volume=4|year=1983}}</ref> <ref>{{استشهاد|last=Lee|first=D. T.|DOI=10.1007/BF00993195|number=2|journal=International Journal of Computer and Information Sciences|mr=724699|pages=87–98|title=On finding the convex hull of a simple polygon|volume=12|year=1983}}</ref>
-== أنظر أيضا ==
-
-* بدن محدب متعامد
-
-== مراجع ==
+== المراجع ==
{{مراجع}}
== قراءة متعمقة ==
-* توماس إتش كورمن ، تشارلز إي ليسرسون ، [[رونالد ريفست|رونالد إل ريفيست]] ، [[كليفورد شتاين|وكليفورد شتاين]] . ''[[مقدمة في الخوارزميات (كتاب)|مقدمة في الخوارزميات]]'' ، الإصدار الثاني. مطبعة معهد ماساتشوستس للتكنولوجيا ومكجرو هيل ، 2001.{{ردمك|0-262-03293-7}}[[النظام القياسي الدولي لترقيم الكتب|رقم ISBN]] [[خاص:BookSources/0-262-03293-7|0-262-03293-7]] . القسم 33.3: العثور على بدن محدب ، ص. 947-957 –
-* فرانكو ب .بيراتا ، إس جيه هونغ . ''هياكل محدبة من مجموعات محدودة من النقاط في بعدين وثلاثة أبعاد'' ، Commun. ACM ، المجلد. 20 ، لا. 2 ، ص. 87-93 – 1977.
-* <bdi><cite class="citation book cs1" data-ve-ignore="true" id="CITEREFMark_de_BergMarc_van_KreveldMark_OvermarsOtfried_Schwarzkopf2000">[[خاص: BookSources / 978-3-540-65620-3|978-3-540-65620-3]]</cite></bdi> القسم 1.1: مثال: أجسام محدبة (يصف الخوارزميات الكلاسيكية للأجسام المحدبة ثنائية الأبعاد). الفصل 11: هياكل محدبة: ص. 235-250 – يصف خوارزمية عشوائية لهياكل محدبة ثلاثية الأبعاد بسبب كلاركسون وشور).
+* توماس إتش كورمن ، تشارلز إي ليسرسون ، [[رونالد ريفست|رونالد إل ريفيست]] ، [[كليفورد شتاين|وكليفورد شتاين]] . ''[[مقدمة في الخوارزميات (كتاب)|مقدمة في الخوارزميات]]'' ، الإصدار الثاني. مطبعة معهد ماساتشوستس للتكنولوجيا ومكجرو هيل ، 2001.{{ردمك|0-262-03293-7}}[[ISBN (identifier)|رقم ISBN]] [[Special:BookSources/0-262-03293-7|0-262-03293-7]] . القسم 33.3: العثور على بدن محدب ، ص. 947-957 –
+* فرانكو ب .بيراتا ، إس جيه هونغ . ''هياكل محدبة من مجموعات محدودة من النقاط في بعدين وثلاثة أبعاد'' ، Commun. ACM ، المجلد. 20 ، لا. 2 ، ص. 87-93 – 1977.
+* <bdi><cite class="citation book cs1" data-ve-ignore="true" id="CITEREFMark_de_BergMarc_van_KreveldMark_OvermarsOtfried_Schwarzkopf2000">[[خاص: BookSources / 978-3-540-65620-3|978-3-540-65620-3]]</cite></bdi> القسم 1.1: مثال: أجسام محدبة (يصف الخوارزميات الكلاسيكية للأجسام المحدبة ثنائية الأبعاد). الفصل 11: هياكل محدبة: ص. 235-250 – يصف خوارزمية عشوائية لهياكل محدبة ثلاثية الأبعاد بسبب كلاركسون وشور).
== روابط خارجية ==
+{{ويكي الكتب|Algorithm Implementation|Geometry/Convex hull|Convex hull}}
* <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>Weisstein, Eric W. "Convex Hull". MathWorld.
* [http://www.cgal.org/Part/ConvexHullAlgorithms 2D, 3D, and dD Convex Hull] in CGAL, the Computational Geometry Algorithms Library
* [http://www.qhull.org/ Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection]
-* [https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html Demo as Flash swf], Jarvis, Graham, Quick (divide and conquer) and Chan algorithms
+* [https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html Demo as Flash swf], Jarvis, Graham, Quick (divide and conquer) and Chan algorithms
* [http://wayback.vefsafn.is/wayback/20130721095350/http://michal.is/projects/convex%2Dhull%2Dgift%2Dwrapping%2Dmethod/ Gift wrapping algorithm in C#]
-
-{{شريط بوابات|رياضيات}}
-
-{{غير مصنفة|تاريخ=نوفمبر 2022}}
' |
حجم الصفحة الجديد (new_size) | 20554 |
حجم الصفحة القديم (old_size) | 20617 |
الحجم المتغير في التعديل (edit_delta) | -63 |
السطور المضافة في التعديل (added_lines) | [
0 => '[[ملف:Envoltura convexa de puntos.png|تصغير|الهيكل المحدب لمجموعة من النقاط]]',
1 => 'إن الخوارزميات التي تبني هياكلاً [[انغلاق محدب|محدبة]] (convex hull) لها العديد من الاستخدامات [[انغلاق محدب|الواسعة]] في [[رياضيات|الرياضيات]] [[علم الحاسوب|وعلوم الحاسوب]].',
2 => 'إن خوارزمية الهيكل المحدب تمثل الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة و واضحة و من الممكن تقدير تعقيد هذه الخوارزميات ب ''n'' والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. او من الممكن تقديرها ب ''h'' والتي تمثل عدد النقاط على حدود الهيكل المحدب.',
3 => 'في البداية لنعتبر أن الحالة العامة لبناء الهيكل المحدب تكون مدخلاتها عبارة عن مجموعة محددة غير مرتبة من النقاط على مستوى ديكارت. وهناك حالة خاصة للمدخلات سيأتي فيما بعد توضيحها بحيث تكون فيها النقاط المدخلة مرتبة على حدود مضلع بسيط.',
4 => 'إن معرفة التعقيد الحسابي لبناء الهيكل المحدب المضلع لمجموعة من النقاط في فضاء ثنائي الابعاد، يتم تمثيله بسهولة وذلك لامتلاكه نفس التعقيد الحسابي الموجود في خوارزمية [[تصنيف (عام)|ترتيب]] النقاط، باستخدام الإسقاط التالي: لكل مجموعة من الارقام المراد ترتيبها <math>x_1,\dots,x_n</math> نقوم بإنشاء النقاط التالية في فضاء ثنائي الابعاد <math>(x_1, x^2_1),\dots,(x_n, x^2_n)</math>',
5 => '',
6 => 'ولأن كل نقطة من هذه النقاط تقع على [[قطع مكافئ|القطع المكافئ]] و الذي يعد بطبيعته [[دالة محدبة|منحنى محدب]] فانه من السهل ايجاد النقاط التي شكلت الهيكل المحدب حيث تكون على طول حدود القطع المكافئ، و التي يمكن الحصول عليها من خلال ترتيب الأرقام <math>x_1,\dots,x_n</math> . و من الواضح ان عملية تحويل الارقام لنقاط تستهلك و<nowiki/>[[تعقيد الوقت|قتا يمكن تمثيله بمنحنى خطي]]، وهذا يؤكد على عدم امكانية حساب الهيكل المحدب لمجموعة من النقاط في الحالة العامة بوقت اسرع من وقت ترتيب مجموعة من الأرقام.',
7 => '',
8 => 'إن نموذج شجرة القرار (Decision tree model) مستخدم في اثبات أن الحد الادنى من التعقيد الحسابي المطلوب لترتيب مجموعة من الأرقام هو Ω ( ''n'' log ''n'' ). و يجب التنويه هنا إلى أن هذا التعقيد الحسابي مرتبط فقط بعمليات المقارنة وليس بالعمليات الحسابية المستخدمة في ترتيب هذه الأرقام. ولكن لا يمكن أبدا استخدام هذه الطريقة لحساب الهياكل المحدبة. ولذلك فان الطريقة الأكثر ملائمة لحساب الهيكل المحدب بنفس التعقيد الحسابي هي شجرة القرار الجبري (algebraic decision tree model) <ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>',
9 => 'و نتيجة لأن [[نموذج حوسبة|نماذج حسابات الكمبيوتر]] التي تسمح بترتيب مجموعة من الارقام في وقت حسابي اسرع من ''O''( ''n'' log ''n'' ) ،مثل استخدام خوارزمية ترتيب الاعداد الصحيحة، فإن حساب الهياكل المحدبة المستوية يمكن ايجادها بطريقة أسرع: كخوارزمية جرهام للبحث Graham scan algorithm المكونة من عملية ترتيب واحدة متبوعة بعمل إضافي يمكن تمثيله بوقت حسابي خطي.',
10 => 'يمكن تصنيف التعقيد الحسابي لبناء الهيكل المحدب بناءً على: عدد النقاط المدخلة - والتي ذكرنا سابقاً أن الحد الأدنى لتعقيدها الحسابي يمكن حصره ب (Ω ( ''n'' log ''n'' - أو على عدد النقاط التي ستشكل الهيكل المحدب (h) و يمكن تسميتها ب بالخوارزميات المعتمدة على المخرجات و التي تستهلك تعقيد حسابي أكثر فاعلية من Θ ( ''n'' log ''n'' ) في حال كان h=o(n).',
11 => 'ان الحد الأدنى [[تحليل الخوارزميات|للتعقيد الزمني]] في أسوأ حالة لخوارزميات الهيكل المحدب المعتمدة على المخرجات هي Ω (n log h) في فضاء ثنائي الأبعاد<ref name="ps" />. و هناك العديد من الخوارزميات تصل لهذا الحد الأدنى من التعقيد الزمني. وقد تم تقديم أقدمها بواسطة (كركباترك وسايدل) [[ديفيد جي. كيركباتريك|Kirkpatrick]] و [[رايموند زايدل|Seidel]] في عام 1986 (الذين أطلقوا عليها اسم خوارزمية الهيكل المحدب القصوى. (The ultimate convex hull algorithm) ). ومن ثم تم تطوير خوارزمية أبسط بكثير بواسطة (شان) Chan في عام 1996، و سميت على اسمه ( خوارزمية Chan).',
12 => 'خوارزميات الهيكل المحدب المدرجة أدناه مرتبة حسب تاريخ نشرها الأول. و نجد أن التعقيد الحسابي لكل خوارزمية قد مُثِل بعدد النقاط المدخلة n وعدد نقاط الهيكل المحدب h. ',
13 => 'ملاحظة: قد تكون ''h'' مساوية ل ''n في أسوأ الحالات.''',
14 => '* خوارزمية '''جارفيس مارس''' او ([[:en:Gift_wrapping_algorithm|خوارزمية '''تغليف الهدايا''']]) – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الاكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 و تبعهم آر جارفيس في عام 1973 [[تحليل الخوارزميات|بتعقيد زمني]] يقدر ب<nowiki/>[[تمثيل O الكبرى|O]](nh). و في أسوأ الحالات يكون [[تمثيل O الكبرى|Θ]] (n ''<sup>2</sup>'').',
15 => '* خوارزمية '''جراهام''' – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما ، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل [[رونالد غراهام|رونالد جراهام]] في عام 1972. و تستغرق وقتاً يقدر بO ( ''n'' ) في حال كانت النقاط المدخلة مرتبة بناء على احد الاحداثيات او بناء على متجه ثابت.',
16 => '* خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 و أ. بيكات 1978. و كخوارزمية الترتيب السريع (Quick sort) فان تعقيدها الزمني هو O(n log n) و من الممكن ان تتراجع لتصل الى ''O'' ( ''n'' <sup>2</sup> ) في أسوء الحالات.',
17 => '* خوارزمية '''[[خوارزمية فرق تسد|فرق تسد]]''' – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ و فرانكو بريراتا (Franco Preparata and Hong) بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.',
18 => '* '''خوارزمية تشان''' - O (n log h) نشرها تيموثي تشين في عام 1996. وهي خوارزمية مثلى من الخوارزميات المعتمدة على المخرجات وتعد أبسط من سابقاتها. و تدمج بين خوارزمية جارفيس واي خوارزمية تستغرق وقتا يقدر ب O(n log n) -مثل خوارزمية جرهام - .',
19 => 'غالبًا ما يتم استخدام الاستدلال البسيط التالي كخطوة أولى في تنفيذ خوارزميات الهيكل المحدب لتحسين الأداء. وقد قام [[سليم عقل]] و توسان باستحداث طريقة فعالة لايجاد الهيكل المحدب و تعتمد هذه الطريقة على استبعاد اكبر عدد ممكن من النقاط التي لا يمكن ان تشكل الهيكل المحدب من خلال إيجاد النقطتين اللتين تحتويان على أدنى وأعلى إحداثيات في محور x ، و أدنى وأعلى نقطتي إحداث في محور y. (كل من هذه العمليات تستغرق [[تمثيل O الكبرى|O]](n)) و هذه النقاط الأربع تشكل [[رباعي أضلاع|محدباً رباعياً]] ، و جميع النقاط التي تقع في هذا الرباعي (باستثناء الرؤوس الأربعة المختارة في البداية) ليست جزءًا من الهيكل المحدب أو يمكن أن نضيف الى الشكل الرباعي النقاط التي تحتوي على أصغر وأكبر مجاميع من إحداثيات x و y وكذلك تلك التي تحتوي على أصغر وأكبر اختلافات في إحداثيات x و y ، و هطذا يصبح لدينا محدب ثماني غير منتظم ، ثم نقوم بالتخلص من جميع النقاط التي بداخل الشكل الثماني بأمان. ',
20 => 'و إذا كانت النقاط عبارة عن متغيرات عشوائية -وهذا يكون فقط لفئة معينة و شائعة من دوال الكثافة الاحتمالية- فإن عملية التخلص من النقاط التي ذكرناها في الخطوة السابقة ستجعل الخوارزمية تستغرق زمناً خطياً، و حتى في اسوء الحالات فان الوقت المستغرق قد يصل الى ''n'' <sup>2</sup> .<ref>[[Luc Devroye]] and [[Godfried Toussaint]], "A note on linear expected time algorithms for finding convex hulls," ''Computing'', Vol. 26, 1981, pp. 361-366.</ref>',
21 => '=== '''مشاكل خوارزمية الهيكل المحدب المتغير والفوري''' ===',
22 => '* '''مشاكل بناء الهيكل المحدب [[خوارزمية فورية|الفوري]]''': حين يتم وصول نقاط الإدخال بالتتابع واحدة تلو الأخرى. سيتم اعادة حساب الهيكل المحدب لمجموعة النقاط الحالية بكفاءة، بعد إدخال كل نقطة. ',
23 => '* '''الصيانة الدورية للهيكل المحدب المتغير''': يجب تحديث الهيكل المحدب بعد كل عملية إدخال أو حذف. وذلك لإمكانية ادخال النقاط و حذفها بالتسلسل.',
24 => 'قد يؤدي إدخال نقطة إلى زيادة عدد رؤوس الهيكل محدب بمقدار 1 على الأكثر ، والعكس صحيح بالنسبة للحذف.',
25 => 'يمكن التعامل مع النقاط المدخلة للهيكل المحدب عبر الإنترنت خلال وقت يقدر ب O (log n) لكل نقطة ، و هذا على أفضل تقدير. و يمكن التعامل مع النقاط المدخلة للهيكل المحدب المتغير خلال وقت يقدر ب O (log <sup>2</sup> ''n'' ) لكل عملية. <ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>',
26 => '=== المضلع البسيط ([[Simple polygon|Simple Polygon]]) ===',
27 => 'يتم تقسيم الهيكل المحدب [[مضلع بسيط|لمضلع بسيط]] إلى أجزاء من خلال جعل أحدها هو المضلع نفسه و أما باقي الهيكل فعبارة عن ''جيوب'' تحدها قطعة من حدود المضلع وحافة واحدة من الهيكل. على الرغم من نشر العديد من الخوارزميات لبناء الهيكل المحدب لمضلع بسيط ، فإن نصفها تقريبًا غير صحيح. <ref>{{استشهاد ويب',
28 => '| url = http://cgm.cs.mcgill.ca/~athens/cs601/',
29 => '| title = A History of Linear-time Convex Hull Algorithms for Simple Polygons',
30 => '| accessdate = October 11, 2020',
31 => '| last = Aloupis',
32 => '| first = Greg',
33 => '}}</ref> ويعد مكالوم وآفيس أول من قدم خوارزمية صحيحة. <ref>{{استشهاد|last=McCallum|first=Duncan|last2=Avis|first2=David|author2-link=David Avis|DOI=10.1016/0020-0190(79)90069-3|number=5|journal=[[Information Processing Letters]]|mr=552534|pages=201–206|title=A linear algorithm for finding the convex hull of a simple polygon|volume=9|year=1979}}</ref> وقد استخدم جرهام و ياو ( {{Harvard citation text|Graham|Yao|1983}} ) و لي ({{Harvard citation text|Lee|1983}}) [[مكدس (بنية بيانات)|بنية بيانات المكدس]] (stack data structure ) واحدة من أجل تبسيط الخوارزمية وتسير هذه الخوارزمية على المضلع في اتجاه عقارب الساعة ، بدءً من النقطة الواقعة أقصى اليسار وخلال ذلك تقوم بتخزين النقاط الموجودة على المحدب ( تلك التي لم يتم تحديدها بعد على أنها داخل الجيوب) في المكدس. في كل خطوة ، تتبع الخوارزمية مسارًا على طول المضلع من قمة المكدس إلى النقطة التالية على ألا تكون ضمن أحد الجيوب المجاورة لأعلى المكدس. و طالما أن اخر نقطتين في أعلى المكدس لا يشكلان محدبا مع النقطة الجديدة نقوم بعملية اخراج النقطة العلوية من المكدس ، ثم ادخال النقطة الجديدة. عندما تنتهي دورة قراءة الخوارزمية للنقاط في اتجاه عقارب الساعة نكون قد عدنا إلى نقطة البداية، وهنا ستكون نتيجة الخوارزمية عبارة عن تسلسل النقاط الموجودة في المكدس وهي ذاتها نقاط المكونة الهيكل. <ref>{{استشهاد|last=Graham|first=Ronald L.|author-link=Ronald Graham|last2=Yao|first2=F. Frances|author2-link=Frances Yao|DOI=10.1016/0196-6774(83)90013-5|number=4|journal=[[Journal of Algorithms]]|mr=729228|pages=324–331|title=Finding the convex hull of a simple polygon|volume=4|year=1983}}</ref> <ref>{{استشهاد|last=Lee|first=D. T.|DOI=10.1007/BF00993195|number=2|journal=International Journal of Computer and Information Sciences|mr=724699|pages=87–98|title=On finding the convex hull of a simple polygon|volume=12|year=1983}}</ref>',
34 => '== المراجع ==',
35 => '* توماس إتش كورمن ، تشارلز إي ليسرسون ، [[رونالد ريفست|رونالد إل ريفيست]] ، [[كليفورد شتاين|وكليفورد شتاين]] . ''[[مقدمة في الخوارزميات (كتاب)|مقدمة في الخوارزميات]]'' ، الإصدار الثاني. مطبعة معهد ماساتشوستس للتكنولوجيا ومكجرو هيل ، 2001.{{ردمك|0-262-03293-7}}[[ISBN (identifier)|رقم ISBN]] [[Special:BookSources/0-262-03293-7|0-262-03293-7]] . القسم 33.3: العثور على بدن محدب ، ص. 947-957 –',
36 => '* فرانكو ب .بيراتا ، إس جيه هونغ . ''هياكل محدبة من مجموعات محدودة من النقاط في بعدين وثلاثة أبعاد'' ، Commun. ACM ، المجلد. 20 ، لا. 2 ، ص. 87-93 – 1977.',
37 => '* <bdi><cite class="citation book cs1" data-ve-ignore="true" id="CITEREFMark_de_BergMarc_van_KreveldMark_OvermarsOtfried_Schwarzkopf2000">[[خاص: BookSources / 978-3-540-65620-3|978-3-540-65620-3]]</cite></bdi> القسم 1.1: مثال: أجسام محدبة (يصف الخوارزميات الكلاسيكية للأجسام المحدبة ثنائية الأبعاد). الفصل 11: هياكل محدبة: ص. 235-250 – يصف خوارزمية عشوائية لهياكل محدبة ثلاثية الأبعاد بسبب كلاركسون وشور).',
38 => '{{ويكي الكتب|Algorithm Implementation|Geometry/Convex hull|Convex hull}}',
39 => '* [https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html Demo as Flash swf], Jarvis, Graham, Quick (divide and conquer) and Chan algorithms'
] |
السطور المزالة في التعديل (removed_lines) | [
0 => '{{مقالة غير مراجعة|تاريخ = نوفمبر 2022}}',
1 => '{{يتيمة|تاريخ=نوفمبر 2022}}',
2 => '',
3 => 'إن الخوارزميات التي تبني هياكلاً [[انغلاق محدب|محدبة]] (convex hull) لها العديد من الاستخدامات [[انغلاق محدب|الواسعة]] في [[رياضيات|الرياضيات]] [[علم الحاسوب|وعلوم الحاسوب]].',
4 => 'إن خوارزمية الهيكل المحدب [[بنية بيانات|تمثل]] الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة و واضحة و من الممكن تقدير تعقيد هذه الخوارزميات ب ''n'' والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. او من الممكن تقديرها ب ''h'' والتي تمثل عدد النقاط على حدود الهيكل المحدب.',
5 => 'في البداية لنعتبر ان الحالة العامة لبناء الهيكل المحدب تكون مدخلاتها عبارة عن مجموعة محددة غير مرتبة من النقاط على مستوى ديكارت. وهناك حالة خاصة للمدخلات سيأتي فيما بعد توضيحها بحيث تكون فيها النقاط المدخلة مرتبة على حدود مضلع بسيط.',
6 => 'إن معرفة التعقيد الحسابي لبناء الهيكل المحدب المضلع لمجموعة من النقاط في فضاء ثنائي الابعاد، يتم تمثيله بسهولة وذلك لامتلاكه نفس التعقيد الحسابي الموجود في خوارزمية [[تصنيف (عام)|ترتيب]] النقاط، باستخدام الإسقاط التالي: لكل مجموعة من الارقام المراد ترتيبها <math>x_1,\dots,x_n</math> نقوم بإنشاء النقاط التالية في فضاء ثنائي الابعاد <math>(x_1, x^2_1),\dots,(x_n, x^2_n)</math>',
7 => 'ولأن كل نقطة من هذه النقاط تقع على [[قطع مكافئ|القطع المكافئ]] و الذي يعد بطبيعته [[دالة محدبة|منحنى محدب]] فانه من السهل ايجاد النقاط التي شكلت الهيكل المحدب حيث تكون على طول حدود القطع المكافئ، و التي يمكن الحصول عليها من خلال ترتيب الأرقام <math>x_1,\dots,x_n</math> . و من الواضح ان عملية تحويل الارقام لنقاط تستهلك و[[تعقيد الوقت|قتا يمكن تمثيله بمنحنى خطي]]، وهذا يؤكد على عدم امكانية حساب الهيكل المحدب لمجموعة من النقاط في الحالة العامة بوقت اسرع من وقت ترتيب مجموعة من الأرقام.',
8 => 'إن نموذج شجرة القرار (Decision tree model) مستخدم في اثبات أن الحد الادنى من التعقيد الحسابي المطلوب لترتيب مجموعة من الأرقام هو Ω ( ''n'' log ''n'' ). و يجب التنويه هنا إلى أن هذا التعقيد الحسابي مرتبط فقط بعمليات المقارنة وليس بالعمليات الحسابية المستخدمة في ترتيب هذه الأرقام. ولكن لا يمكن أبدا استخدام هذه الطريقة لحساب الهياكل المحدبة. ولذلك فان الطريقة الأكثر ملائمة لحساب الهيكل المحدب بنفس التعقيد الحسابي هي شجرة القرار الجبري (algebraic decision tree model) <ref name="ps">Preparata, Shamos, ''Computational Geometry'', Chapter "Convex Hulls: Basic Algorithms"</ref>',
9 => 'و نتيجة لأن نماذج حسابات الكمبيوتر التي تسمح بترتيب مجموعة من الارقام في وقت حسابي اسرع من ''O''( ''n'' log ''n'' ) ،مثل استخدام خوارزمية ترتيب الاعداد الصحيحة، فإن حساب الهياكل المحدبة المستوية يمكن ايجادها بطريقة أسرع: كخوارزمية جرهام للبحث Graham scan algorithm المكونة من عملية ترتيب واحدة متبوعة بعمل إضافي يمكن تمثيله بوقت حسابي خطي.',
10 => 'يمكن تصنيف التعقيد الحسابي لبناء الهيكل المحدب بناءً على: عدد النقاط المدخلة - والتي ذكرنا سابقاً أن الحد الأدنى لتعقيدها الحسابي يمكن حصره ب (Ω ( ''n'' log ''n'' - أو على عدد النقاط التي ستشكل الهيكل المحدب (h) و يمكن تسميتها ب بالخوارزميات المعتمدة على المخرجات و التي تستهلك تعقيد حسابي أكثر فاعلية من Θ ( ''n'' log ''n'' ) في حال كان h=o(n).',
11 => 'ان الحد الأدنى [[تحليل الخوارزميات|للتعقيد الزمني]] في أسوأ حالة لخوارزميات الهيكل المحدب المعتمدة على المخرجات هي Ω (n log h) في فضاء ثنائي الأبعاد.<ref name="ps" /> و هناك العديد من الخوارزميات تصل لهذا الحد الأدنى من التعقيد الزمني. وقد تم تقديم أقدمها بواسطة (كركباترك وسايدل) [[ديفيد جي. كيركباتريك|Kirkpatrick]] و[[رايموند زايدل|Seidel]] في عام 1986 (الذين أطلقوا عليها اسم خوارزمية الهيكل المحدب القصوى. (the ultimate convex hull algorithm) ). ومن ثم تم تطوير خوارزمية أبسط بكثير بواسطة (شان) Chan في عام 1996، و سميت على اسمه ( خوارزمية Chan).',
12 => 'خوارزميات الهيكل المحدب المدرجة أدناه مرتبة حسب تاريخ نشرها الأول. و نجد أن التعقيد الحسابي لكل خوارزمية قد مُثِل بعدد النقاط المدخلة n وعدد نقاط الهيكل المحدب h.',
13 => 'ملاحظة: قد تكون ''h'' مساوية ل ''n في أسوأ الحالات.''',
14 => '* خوارزمية '''جارفيس مارس''' او (خوارزمية '''تغليف الهدايا''') – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الاكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 و تبعهم آر جارفيس في عام 1973 [[تحليل الخوارزميات|بتعقيد زمني]] يقدر ب<nowiki/>[[تمثيل O الكبرى|O]](nh). و في أسوأ الحالات يكون [[تمثيل O الكبرى|Θ]] (n ''<sup>2</sup>'').',
15 => '* خوارزمية '''جراهام''' – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما ، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل [[رونالد غراهام|رونالد جراهام]] في عام 1972. و تستغرق وقتاً يقدر بO ( ''n'' ) في حال كانت النقاط المدخلة مرتبة بناء على احد الاحداثيات او بناء على متجه ثابت.',
16 => '* خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 و أ. بيكات 1978. و كخوارزمية الترتيب السريع (Quick sort) فان تعقيدها الزمني هو O(n log n) و من الممكن ان تتراجع لتصل الى ''O'' ( ''n'' <sup>2</sup> ) في أسوء الحالات.',
17 => '* خوارزمية '''فرق تسد''' – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ و فرانكو بريراتا (Franco Preparata and Hong) بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.',
18 => '* '''خوارزمية تشان''' - O (n log h) نشرها تيموثي تشين في عام 1996. وهي خوارزمية مثلى من الخوارزميات المعتمدة على المخرجات وتعد أبسط من سابقاتها. و تدمج بين خوارزمية جارفيس واي خوارزمية تستغرق وقتا يقدر ب O(n log n) -مثل خوارزمية جرهام - .',
19 => 'غالبًا ما يتم استخدام الاستدلال البسيط التالي كخطوة أولى في تنفيذ خوارزميات الهيكل المحدب لتحسين الأداء. وقد قام<nowiki/>[[سليم عقل]] و توسان باستحداث طريقة فعالة لايجاد الهيكل المحدب و تعتمد هذه الطريقة على استبعاد اكبر عدد ممكن من النقاط التي لا يمكن ان تشكل الهيكل المحدب من خلال إيجاد النقطتين اللتين تحتويان على أدنى وأعلى إحداثيات في محور x ، و أدنى وأعلى نقطتي إحداث في محور y. (كل من هذه العمليات تستغرق [[تمثيل O الكبرى|O]] (n)) و هذه النقاط الأربع تشكل [[رباعي أضلاع|محدباً رباعياً]] ، و جميع النقاط التي تقع في هذا الرباعي (باستثناء الرؤوس الأربعة المختارة في البداية) ليست جزءًا من الهيكل المحدب أو يمكن أن نضيف الى الشكل الرباعي النقاط التي تحتوي على أصغر وأكبر مجاميع من إحداثيات x و y وكذلك تلك التي تحتوي على أصغر وأكبر اختلافات في إحداثيات x و y ، و هطذا يصبح لدينا محدب ثماني غير منتظم ، ثم نقوم بالتخلص من جميع النقاط التي بداخل الشكل الثماني بأمان.',
20 => 'و إذا كانت النقاط عبارة عن متغيرات عشوائية -وهذا يكون فقط لفئة معينة و شائعة من دوال الكثافة الاحتمالية- فإن عملية التخلص من النقاط التي ذكرناها في الخطوة السابقة ستجعل الخوارزمية تستغرق زمناً خطياً، و حتى في اسوء الحالات فان الوقت المستغرق قد يصل الى ''n'' <sup>2</sup> .<ref>[[Luc Devroye]] and [[Godfried Toussaint]], "A note on linear expected time algorithms for finding convex hulls," ''Computing'', Vol. 26, 1981, pp. 361-366.</ref>',
21 => '=== '''مشاكل خوارزمية الهيكل المحدب المتغير''' ===',
22 => '* '''مشاكل بناء الهيكل المحدب عبر الإنترنت''': حين يتم وصول نقاط الإدخال بالتتابع واحدة تلو الأخرى. سيتم اعادة حساب الهيكل المحدب لمجموعة النقاط الحالية بكفاءة، بعد إدخال كل نقطة. ',
23 => '* '''الصيانة الدورية للهيكل المحدب المتغير''': يجب تحديث الهيكل المحدب بعد كل عملية إدخال أو حذف. وذلك لإمكانية ادخال النقاط و حذفها بالتسلسل.',
24 => 'قد يؤدي إدخال نقطة إلى زيادة عدد رؤوس الهيكل محدب بمقدار 1 على الأكثر ، والعكس صحيح بالنسبة للحذف.',
25 => 'يمكن التعامل مع النقاط المدخلة للهيكل المحدب عبر الإنترنت خلال وقت يقدر ب O (log n) لكل نقطة ، و هذا على أفضل تقدير. و يمكن التعامل مع النقاط المدخلة للهيكل المحدب المتغير خلال وقت يقدر ب O (log <sup>2</sup> ''n'' ) لكل عملية.<ref name="ps" />',
26 => '=== المضلع البسيط ([[مضلع بسيط]]) ===',
27 => 'يتم تقسيم الهيكل المحدب [[مضلع بسيط|لمضلع بسيط]] إلى أجزاء من خلال جعل أحدها هو المضلع نفسه و أما باقي الهيكل فعبارة عن ''جيوب'' تحدها قطعة من حدود المضلع وحافة واحدة من الهيكل. على الرغم من نشر العديد من الخوارزميات لبناء الهيكل المحدب لمضلع بسيط ، فإن نصفها تقريبًا غير صحيح.<ref>{{استشهاد ويب',
28 => '| مسار = http://cgm.cs.mcgill.ca/~athens/cs601/',
29 => '| عنوان = A History of Linear-time Convex Hull Algorithms for Simple Polygons',
30 => '| تاريخ الوصول = October 11, 2020',
31 => '| الأخير = Aloupis',
32 => '| الأول = Greg',
33 => '}}</ref> ويعد مكالوم وآفيس أول من قدم خوارزمية صحيحة.<ref>{{استشهاد|الأخير=McCallum|الأول=Duncan|مؤلف-الأخير2=Avis|مؤلف-الأول2=David|وصلة-مؤلف2=David Avis|DOI=10.1016/0020-0190(79)90069-3|العدد=5|صحيفة=[[Information Processing Letters]]|mr=552534|صفحات=201–206|عنوان=A linear algorithm for finding the convex hull of a simple polygon|المجلد=9|سنة=1979}}</ref> وقد استخدم جرهام و ياو ( {{Harvard citation text|Graham|Yao|1983}} ) و لي ({{Harvard citation text|Lee|1983}}) [[مكدس (بنية بيانات)|بنية بيانات المكدس]] (stack data structure ) واحدة من أجل تبسيط الخوارزمية وتسير هذه الخوارزمية على المضلع في اتجاه عقارب الساعة ، بدءً من النقطة الواقعة أقصى اليسار وخلال ذلك تقوم بتخزين النقاط الموجودة على المحدب ( تلك التي لم يتم تحديدها بعد على أنها داخل الجيوب) في المكدس. في كل خطوة ، تتبع الخوارزمية مسارًا على طول المضلع من قمة المكدس إلى النقطة التالية على ألا تكون ضمن أحد الجيوب المجاورة لأعلى المكدس. و طالما أن اخر نقطتين في أعلى المكدس لا يشكلان محدبا مع النقطة الجديدة نقوم بعملية اخراج النقطة العلوية من المكدس ، ثم ادخال النقطة الجديدة. عندما تنتهي دورة قراءة الخوارزمية للنقاط في اتجاه عقارب الساعة نكون قد عدنا إلى نقطة البداية، وهنا ستكون نتيجة الخوارزمية عبارة عن تسلسل النقاط الموجودة في المكدس وهي ذاتها نقاط المكونة الهيكل.<ref>{{استشهاد|الأخير=Graham|الأول=Ronald L.|وصلة مؤلف=Ronald Graham|مؤلف-الأخير2=Yao|مؤلف-الأول2=F. Frances|وصلة-مؤلف2=Frances Yao|DOI=10.1016/0196-6774(83)90013-5|العدد=4|صحيفة=[[إلزيفير]]|mr=729228|صفحات=324–331|عنوان=Finding the convex hull of a simple polygon|المجلد=4|سنة=1983}}</ref><ref>{{استشهاد|الأخير=Lee|الأول=D. T.|DOI=10.1007/BF00993195|العدد=2|صحيفة=International Journal of Computer and Information Sciences|mr=724699|صفحات=87–98|عنوان=On finding the convex hull of a simple polygon|المجلد=12|سنة=1983}}</ref>',
34 => '== أنظر أيضا ==',
35 => '',
36 => '* بدن محدب متعامد',
37 => '',
38 => '== مراجع ==',
39 => '* توماس إتش كورمن ، تشارلز إي ليسرسون ، [[رونالد ريفست|رونالد إل ريفيست]] ، [[كليفورد شتاين|وكليفورد شتاين]] . ''[[مقدمة في الخوارزميات (كتاب)|مقدمة في الخوارزميات]]'' ، الإصدار الثاني. مطبعة معهد ماساتشوستس للتكنولوجيا ومكجرو هيل ، 2001.{{ردمك|0-262-03293-7}}[[النظام القياسي الدولي لترقيم الكتب|رقم ISBN]] [[خاص:BookSources/0-262-03293-7|0-262-03293-7]] . القسم 33.3: العثور على بدن محدب ، ص. 947-957 –',
40 => '* فرانكو ب .بيراتا ، إس جيه هونغ . ''هياكل محدبة من مجموعات محدودة من النقاط في بعدين وثلاثة أبعاد'' ، Commun. ACM ، المجلد. 20 ، لا. 2 ، ص. 87-93 – 1977.',
41 => '* <bdi><cite class="citation book cs1" data-ve-ignore="true" id="CITEREFMark_de_BergMarc_van_KreveldMark_OvermarsOtfried_Schwarzkopf2000">[[خاص: BookSources / 978-3-540-65620-3|978-3-540-65620-3]]</cite></bdi> القسم 1.1: مثال: أجسام محدبة (يصف الخوارزميات الكلاسيكية للأجسام المحدبة ثنائية الأبعاد). الفصل 11: هياكل محدبة: ص. 235-250 – يصف خوارزمية عشوائية لهياكل محدبة ثلاثية الأبعاد بسبب كلاركسون وشور).',
42 => '* [https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html Demo as Flash swf], Jarvis, Graham, Quick (divide and conquer) and Chan algorithms',
43 => '',
44 => '{{شريط بوابات|رياضيات}}',
45 => '',
46 => '{{غير مصنفة|تاريخ=نوفمبر 2022}}'
] |
كل الوصلات الخارجية المضافة في التعديل (added_links) | [] |
كل الوصلات الخارجية المزالة في التعديل (removed_links) | [
0 => '//en.wikipedia.org/w/index.php?title=Special:Search&redirs=1&search=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84+%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&fulltext=Search&ns0=1&title=Special:Search&advanced=1&fulltext=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84+%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8'
] |
نص الصفحة الجديد، مجردا من أية تهيئة (new_text) | ' الهيكل المحدب لمجموعة من النقاط
إن الخوارزميات التي تبني هياكلاً محدبة (convex hull) لها العديد من الاستخدامات الواسعة في الرياضيات وعلوم الحاسوب.
في الهندسة الحسابية ، تم اقتراح العديد من الخوارزميات لحساب الهيكل المحدب لمجموعة نقاط محددة، وكل خوارزمية من هذه الخوارزميات لها درجة مختلفة من تعقيد العمليات الحسابية.
إن خوارزمية الهيكل المحدب تمثل الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة و واضحة و من الممكن تقدير تعقيد هذه الخوارزميات ب n والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. او من الممكن تقديرها ب h والتي تمثل عدد النقاط على حدود الهيكل المحدب.
.
محتويات
1 الحالة المستوية لبناء الهيكل المحدب
1.1 الحد الأدنى من التعقيد الحسابي
1.2 الخوارزميات المعتمدة على المخرجات
1.3 خوارزميات الهيكل المحدب
1.4 استدلال توسان و عقل
1.5 مشاكل خوارزمية الهيكل المحدب المتغير والفوري
1.6 المضلع البسيط (Simple Polygon)
2 المراجع
3 قراءة متعمقة
4 روابط خارجية
الحالة المستوية لبناء الهيكل المحدب[edit]
في البداية لنعتبر أن  الحالة العامة لبناء الهيكل المحدب تكون مدخلاتها عبارة عن مجموعة محددة غير مرتبة من النقاط على مستوى ديكارت. وهناك حالة خاصة للمدخلات سيأتي فيما بعد توضيحها بحيث تكون فيها النقاط المدخلة مرتبة على حدود مضلع بسيط.
إذا لم تكن جميع النقاط على نفس الخط، فإن الهيكل المحدب يكون مضلعًا محدبًا رؤسه تكون أحد هذه النقاط. واكثر هذه الحلات شيوعا هي عندما تكون نقاط الهيكل المضلع مرتبة على طول حدوده في اتجاه عقارب الساعة أو عكس عقارب الساعة. و في بعض التطبيقات يكون من الملائم تمثيل مضلع محدب كتقاطع لمجموعة من أنصاف المستويات .
الحد الأدنى من التعقيد الحسابي[edit]
إن معرفة التعقيد الحسابي لبناء الهيكل المحدب المضلع لمجموعة من النقاط في فضاء ثنائي الابعاد، يتم تمثيله بسهولة وذلك لامتلاكه نفس التعقيد الحسابي الموجود في خوارزمية ترتيب النقاط، باستخدام الإسقاط التالي: لكل مجموعة من الارقام  المراد ترتيبها
x
1
,
…
,
x
n
{\displaystyle x_{1},\dots ,x_{n}}
نقوم بإنشاء النقاط التالية في فضاء ثنائي الابعاد
(
x
1
,
x
1
2
)
,
…
,
(
x
n
,
x
n
2
)
{\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
ولأن كل نقطة من هذه النقاط تقع على القطع المكافئ و الذي يعد بطبيعته منحنى محدب فانه من السهل ايجاد النقاط التي شكلت الهيكل المحدب حيث تكون على طول حدود القطع المكافئ، و التي يمكن الحصول عليها من خلال ترتيب الأرقام
x
1
,
…
,
x
n
{\displaystyle x_{1},\dots ,x_{n}}
. و من الواضح ان عملية تحويل الارقام لنقاط تستهلك وقتا يمكن تمثيله بمنحنى خطي، وهذا يؤكد على عدم امكانية حساب الهيكل المحدب لمجموعة من النقاط في الحالة العامة بوقت اسرع من وقت ترتيب مجموعة من الأرقام.
إن نموذج شجرة القرار (Decision tree model) مستخدم في اثبات أن الحد الادنى من التعقيد الحسابي المطلوب لترتيب مجموعة من الأرقام هو Ω ( n log n ). و يجب التنويه هنا إلى أن هذا التعقيد الحسابي مرتبط فقط بعمليات المقارنة وليس بالعمليات الحسابية المستخدمة في ترتيب هذه الأرقام. ولكن لا يمكن أبدا استخدام هذه الطريقة لحساب الهياكل المحدبة. ولذلك فان الطريقة الأكثر ملائمة لحساب الهيكل المحدب بنفس التعقيد الحسابي هي شجرة القرار الجبري (algebraic decision tree model) [1]
و نتيجة لأن نماذج حسابات الكمبيوتر التي تسمح بترتيب مجموعة من الارقام في وقت حسابي اسرع من O( n log n ) ،مثل استخدام خوارزمية ترتيب الاعداد الصحيحة،  فإن حساب الهياكل المحدبة المستوية يمكن ايجادها بطريقة أسرع: كخوارزمية جرهام للبحث Graham scan algorithm المكونة من عملية ترتيب واحدة متبوعة بعمل إضافي يمكن تمثيله بوقت حسابي خطي.
الخوارزميات المعتمدة على المخرجات[edit]
يمكن تصنيف التعقيد الحسابي لبناء الهيكل المحدب بناءً على: عدد النقاط المدخلة - والتي ذكرنا سابقاً أن الحد الأدنى لتعقيدها الحسابي يمكن حصره ب (Ω ( n log n - أو على عدد النقاط التي ستشكل الهيكل المحدب (h) و يمكن تسميتها ب بالخوارزميات المعتمدة على المخرجات و التي تستهلك تعقيد حسابي أكثر فاعلية من Θ ( n log n ) في حال كان h=o(n).
ان الحد الأدنى للتعقيد الزمني في أسوأ حالة لخوارزميات الهيكل المحدب المعتمدة على المخرجات هي Ω (n log h) في فضاء ثنائي الأبعاد[1]. و هناك العديد من الخوارزميات تصل لهذا الحد الأدنى من التعقيد الزمني. وقد تم تقديم أقدمها بواسطة (كركباترك وسايدل) Kirkpatrick و Seidel في عام 1986 (الذين أطلقوا عليها اسم خوارزمية الهيكل المحدب القصوى.  (The ultimate convex hull algorithm) ). ومن ثم تم تطوير خوارزمية أبسط بكثير بواسطة  (شان) Chan في عام 1996، و سميت على اسمه ( خوارزمية Chan).
خوارزميات الهيكل المحدب[edit]
خوارزميات الهيكل المحدب المدرجة أدناه مرتبة حسب تاريخ نشرها الأول. و نجد أن التعقيد الحسابي لكل خوارزمية قد مُثِل بعدد النقاط المدخلة n وعدد نقاط الهيكل المحدب h.
ملاحظة: قد تكون h مساوية ل n في أسوأ الحالات.
خوارزمية جارفيس مارس او (خوارزمية تغليف الهدايا) – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الاكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 و تبعهم آر جارفيس في عام 1973 بتعقيد زمني يقدر بO(nh). و في أسوأ الحالات يكون Θ (n 2).
 خوارزمية جراهام – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما ، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل رونالد جراهام في عام 1972. و تستغرق وقتاً يقدر بO ( n ) في حال كانت النقاط المدخلة مرتبة بناء على احد الاحداثيات او بناء على متجه ثابت.
خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 و أ. بيكات 1978. و كخوارزمية الترتيب السريع (Quick sort)  فان تعقيدها الزمني هو O(n log n) و من الممكن ان تتراجع لتصل الى O ( n 2 ) في أسوء الحالات.
خوارزمية فرق تسد – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ و فرانكو بريراتا (Franco Preparata and Hong) بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.
 خوارزمية اندرو (السلسلة الرتيبة) – O(n log n) تم نشر هذه الخوارزمية عام 1979 بواسطة اندرو AM Andrew. و يمكن اعتبار هذه الخوارزمية كنوع من خوارزمية جراهام ، التي ترتب النقاط من خلال إحداثياتها. و إذا تم ترتيب النقاط المدخلة فإن الخوارزمية تستغرق وقتاً يقدر ب O (n).
 خوارزمية الهيكل المحدب المتزايد - O (n log n) تم صايغتها عام 1984 بواسطة مايكل كاليMichael Kallay.
خوارزمية كيركباتريك - سيدل - O ( n log h ) هي أول خوارزمية من الخوارزميات المعتمدة على المخرجات و تستخدم تقنية "marriage-before-conquest" في البرمجة الخطية محدودة الأبعاد. وقد تم نشرها بواسطة Kirkpatrick and Seidel عام 1986.
خوارزمية تشان - O (n log h) نشرها تيموثي تشين في عام 1996. وهي خوارزمية مثلى من الخوارزميات المعتمدة على المخرجات وتعد أبسط من سابقاتها. و تدمج بين خوارزمية جارفيس واي خوارزمية تستغرق وقتا يقدر ب O(n log n)  -مثل خوارزمية جرهام - .
استدلال توسان و عقل[edit]
غالبًا ما يتم استخدام الاستدلال البسيط التالي كخطوة أولى في تنفيذ خوارزميات الهيكل المحدب لتحسين الأداء. وقد قام سليم عقل و توسان باستحداث طريقة فعالة لايجاد الهيكل المحدب و تعتمد هذه الطريقة على استبعاد اكبر عدد ممكن من النقاط التي لا يمكن ان تشكل الهيكل المحدب من خلال إيجاد النقطتين اللتين تحتويان على أدنى وأعلى إحداثيات في محور x ، و أدنى وأعلى نقطتي إحداث في محور y. (كل من هذه العمليات تستغرق O(n)) و هذه النقاط الأربع تشكل محدباً رباعياً ، و جميع النقاط التي تقع في هذا الرباعي (باستثناء الرؤوس الأربعة المختارة في البداية) ليست جزءًا من الهيكل المحدب أو يمكن أن نضيف الى الشكل الرباعي النقاط التي تحتوي على أصغر وأكبر مجاميع من إحداثيات x و y وكذلك تلك التي تحتوي على أصغر وأكبر اختلافات في إحداثيات x و y ، و هطذا يصبح لدينا محدب ثماني غير منتظم ، ثم نقوم بالتخلص من جميع النقاط التي بداخل الشكل الثماني بأمان.
و إذا كانت النقاط عبارة عن متغيرات عشوائية -وهذا يكون فقط لفئة معينة و شائعة من دوال الكثافة الاحتمالية- فإن عملية التخلص من النقاط التي ذكرناها في الخطوة السابقة ستجعل الخوارزمية تستغرق زمناً خطياً، و حتى في اسوء الحالات فان الوقت المستغرق قد يصل الى n 2 .[2]
مشاكل خوارزمية الهيكل المحدب المتغير والفوري[edit]
ان في كل ما تم ذكره سابقا كانت النقاط المدخلة معروفة مسبقا، و لذلك فإننا يجب أن نأخذ بعين الاعتبار الخطوتين التاليتين عند بناء الهيكل المحدب:[1]
مشاكل بناء الهيكل المحدب الفوري: حين يتم وصول نقاط الإدخال بالتتابع واحدة تلو الأخرى. سيتم اعادة حساب الهيكل المحدب لمجموعة النقاط الحالية بكفاءة، بعد إدخال كل نقطة.  
الصيانة الدورية للهيكل المحدب المتغير: يجب تحديث الهيكل المحدب بعد كل عملية إدخال أو حذف. وذلك لإمكانية ادخال النقاط و حذفها بالتسلسل.
قد يؤدي إدخال نقطة إلى زيادة عدد رؤوس الهيكل محدب بمقدار 1 على الأكثر ، والعكس صحيح بالنسبة للحذف.
يمكن التعامل مع النقاط المدخلة للهيكل المحدب عبر الإنترنت خلال وقت يقدر ب O (log n) لكل نقطة ، و هذا على أفضل تقدير. و يمكن التعامل مع النقاط المدخلة للهيكل المحدب المتغير خلال وقت يقدر ب O (log 2 n ) لكل عملية. [1]
المضلع البسيط (Simple Polygon)[edit]
يتم تقسيم الهيكل المحدب لمضلع بسيط إلى أجزاء من خلال جعل أحدها هو المضلع نفسه و أما باقي الهيكل فعبارة عن جيوب تحدها قطعة من حدود المضلع وحافة واحدة من الهيكل. على الرغم من نشر العديد من الخوارزميات لبناء الهيكل المحدب لمضلع بسيط ، فإن نصفها تقريبًا غير صحيح. [3] ويعد مكالوم وآفيس أول من قدم خوارزمية صحيحة. [4] وقد استخدم جرهام و ياو ( Graham & Yao (1983) ) و لي (Lee (1983)) بنية بيانات المكدس (stack data structure ) واحدة من أجل تبسيط الخوارزمية وتسير هذه الخوارزمية على المضلع في اتجاه عقارب الساعة ، بدءً من النقطة الواقعة أقصى اليسار وخلال ذلك تقوم بتخزين النقاط الموجودة على المحدب ( تلك التي لم يتم تحديدها بعد على أنها داخل الجيوب) في المكدس. في كل خطوة ، تتبع الخوارزمية مسارًا على طول المضلع من قمة المكدس إلى النقطة التالية على ألا تكون ضمن أحد الجيوب المجاورة لأعلى المكدس. و طالما أن اخر نقطتين في أعلى المكدس لا يشكلان محدبا مع النقطة الجديدة نقوم بعملية اخراج النقطة العلوية من المكدس ، ثم ادخال النقطة الجديدة. عندما تنتهي دورة قراءة الخوارزمية للنقاط في اتجاه عقارب الساعة نكون قد عدنا إلى نقطة البداية، وهنا ستكون نتيجة الخوارزمية عبارة عن تسلسل النقاط الموجودة في المكدس وهي ذاتها نقاط المكونة الهيكل. [5] [6]
المراجع[edit]
.mw-parser-output .reflist{font-size:90%;margin-bottom:0.5em;list-style-type:decimal;overflow-y:auto;max-height:300px}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}@media print{.mw-parser-output .reflist{overflow-y:visible!important;max-height:none!important}}
↑ أ ب ت ث Preparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms"
^ Luc Devroye and Godfried Toussaint, "A note on linear expected time algorithms for finding convex hulls," Computing, Vol. 26, 1981, pp. 361-366.
^ .mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}Aloupis, Greg، "A History of Linear-time Convex Hull Algorithms for Simple Polygons"، اطلع عليه بتاريخ 11 أكتوبر 2020.
^ McCallum, Duncan؛ Avis, David (1979)، "A linear algorithm for finding the convex hull of a simple polygon"، Information Processing Letters، 9 (5): 201–206، doi:10.1016/0020-0190(79)90069-3، MR 0552534
^ Graham, Ronald L.؛ Yao, F. Frances (1983)، "Finding the convex hull of a simple polygon"، Journal of Algorithms، 4 (4): 324–331، doi:10.1016/0196-6774(83)90013-5، MR 0729228
^ Lee, D. T. (1983)، "On finding the convex hull of a simple polygon"، International Journal of Computer and Information Sciences، 12 (2): 87–98، doi:10.1007/BF00993195، MR 0724699
قراءة متعمقة[edit]
توماس إتش كورمن ، تشارلز إي ليسرسون ، رونالد إل ريفيست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الإصدار الثاني. مطبعة معهد ماساتشوستس للتكنولوجيا ومكجرو هيل ، 2001.(ردمك 0-262-03293-7)رقم ISBN 0-262-03293-7 . القسم 33.3: العثور على بدن محدب ، ص. 947-957 –
فرانكو ب .بيراتا ، إس جيه هونغ . هياكل محدبة من مجموعات محدودة من النقاط في بعدين وثلاثة أبعاد ، Commun. ACM ، المجلد. 20 ، لا. 2 ، ص. 87-93 – 1977.
978-3-540-65620-3 القسم 1.1: مثال: أجسام محدبة (يصف الخوارزميات الكلاسيكية للأجسام المحدبة ثنائية الأبعاد). الفصل 11: هياكل محدبة: ص. 235-250 – يصف خوارزمية عشوائية لهياكل محدبة ثلاثية الأبعاد بسبب كلاركسون وشور).
روابط خارجية[edit]
اقرأ كتاب يتعلق بخوارزمية الهيكل المحدب في ويكي الكتب.
Weisstein, Eric W. "Convex Hull". MathWorld.
2D, 3D, and dD Convex Hull in CGAL, the Computational Geometry Algorithms Library
Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection
Demo as Flash swf, Jarvis, Graham, Quick (divide and conquer) and Chan algorithms
Gift wrapping algorithm in C#' |
كل الوصلات الخارجية في النص الجديد (all_links) | [
0 => 'http://cgm.cs.mcgill.ca/~athens/cs601/',
1 => '//doi.org/10.1016%2F0020-0190(79)90069-3',
2 => '//www.ams.org/mathscinet-getitem?mr=0552534',
3 => '//doi.org/10.1016%2F0196-6774(83)90013-5',
4 => '//www.ams.org/mathscinet-getitem?mr=0729228',
5 => '//doi.org/10.1007%2FBF00993195',
6 => '//www.ams.org/mathscinet-getitem?mr=0724699',
7 => 'http://www.cgal.org/Part/ConvexHullAlgorithms',
8 => 'http://www.qhull.org/',
9 => 'https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html',
10 => 'http://wayback.vefsafn.is/wayback/20130721095350/http://michal.is/projects/convex-hull-gift-wrapping-method/'
] |
الوصلات في الصفحة، قبل التعديل (old_links) | [
0 => 'http://cgm.cs.mcgill.ca/~athens/cs601/',
1 => 'http://wayback.vefsafn.is/wayback/20130721095350/http://michal.is/projects/convex-hull-gift-wrapping-method/',
2 => '//www.ams.org/mathscinet-getitem?mr=0552534',
3 => '//www.ams.org/mathscinet-getitem?mr=0724699',
4 => '//www.ams.org/mathscinet-getitem?mr=0729228',
5 => 'http://www.cgal.org/Part/ConvexHullAlgorithms',
6 => '//doi.org/10.1007%2FBF00993195',
7 => '//doi.org/10.1016%2F0020-0190(79)90069-3',
8 => '//doi.org/10.1016%2F0196-6774(83)90013-5',
9 => 'http://www.qhull.org/',
10 => '//en.wikipedia.org/w/index.php?title=Special:Search&redirs=1&search=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84+%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&fulltext=Search&ns0=1&title=Special:Search&advanced=1&fulltext=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84+%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8',
11 => 'https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html'
] |
مصدر HTML المعروض للمراجعة الجديدة (new_html) | '<div class="mw-parser-output"><div class="thumb tleft"><div class="thumbinner" style="width:222px;"><a href="/wiki/%D9%85%D9%84%D9%81:Envoltura_convexa_de_puntos.png" class="image"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/16/Envoltura_convexa_de_puntos.png/220px-Envoltura_convexa_de_puntos.png" decoding="async" width="220" height="165" class="thumbimage" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/16/Envoltura_convexa_de_puntos.png/330px-Envoltura_convexa_de_puntos.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/16/Envoltura_convexa_de_puntos.png/440px-Envoltura_convexa_de_puntos.png 2x" data-file-width="560" data-file-height="420" /></a> <div class="thumbcaption"><div class="magnify"><a href="/wiki/%D9%85%D9%84%D9%81:Envoltura_convexa_de_puntos.png" class="internal" title="Enlarge"></a></div>الهيكل المحدب لمجموعة من النقاط</div></div></div>
<p>إن الخوارزميات التي تبني هياكلاً <a href="/wiki/%D8%A7%D9%86%D8%BA%D9%84%D8%A7%D9%82_%D9%85%D8%AD%D8%AF%D8%A8" title="انغلاق محدب">محدبة</a> (convex hull) لها العديد من الاستخدامات <a href="/wiki/%D8%A7%D9%86%D8%BA%D9%84%D8%A7%D9%82_%D9%85%D8%AD%D8%AF%D8%A8" title="انغلاق محدب">الواسعة</a> في <a href="/wiki/%D8%B1%D9%8A%D8%A7%D8%B6%D9%8A%D8%A7%D8%AA" title="رياضيات">الرياضيات</a> <a href="/wiki/%D8%B9%D9%84%D9%85_%D8%A7%D9%84%D8%AD%D8%A7%D8%B3%D9%88%D8%A8" title="علم الحاسوب">وعلوم الحاسوب</a>.
</p><p>في <a href="/wiki/%D9%87%D9%86%D8%AF%D8%B3%D8%A9_%D8%B1%D9%8A%D8%A7%D8%B6%D9%8A%D8%A9_%D8%AD%D8%A7%D8%B3%D9%88%D8%A8%D9%8A%D8%A9" title="هندسة رياضية حاسوبية">الهندسة الحسابية</a> ، تم اقتراح العديد من الخوارزميات لحساب الهيكل المحدب لمجموعة نقاط محددة، وكل خوارزمية من هذه الخوارزميات لها درجة مختلفة من <a href="/wiki/%D8%AA%D8%AD%D9%84%D9%8A%D9%84_%D8%A7%D9%84%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A7%D8%AA" title="تحليل الخوارزميات">تعقيد العمليات الحسابية</a>.
</p><p>إن خوارزمية الهيكل المحدب تمثل الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة و واضحة و من الممكن تقدير تعقيد هذه الخوارزميات ب <i>n</i> والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. او من الممكن تقديرها ب <i>h</i> والتي تمثل عدد النقاط على حدود الهيكل المحدب.
</p><p>.
</p>
<div id="toc" class="toc" role="navigation" aria-labelledby="mw-toc-heading"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none" /><div class="toctitle" lang="ar" dir="rtl"><h2 id="mw-toc-heading">محتويات</h2><span class="toctogglespan"><label class="toctogglelabel" for="toctogglecheckbox"></label></span></div>
<ul>
<li class="toclevel-1 tocsection-1"><a href="#الحالة_المستوية_لبناء_الهيكل_المحدب"><span class="tocnumber">1</span> <span class="toctext">الحالة المستوية لبناء الهيكل المحدب</span></a>
<ul>
<li class="toclevel-2 tocsection-2"><a href="#الحد_الأدنى_من_التعقيد_الحسابي"><span class="tocnumber">1.1</span> <span class="toctext">الحد الأدنى من التعقيد الحسابي</span></a></li>
<li class="toclevel-2 tocsection-3"><a href="#الخوارزميات_المعتمدة_على_المخرجات"><span class="tocnumber">1.2</span> <span class="toctext">الخوارزميات المعتمدة على المخرجات</span></a></li>
<li class="toclevel-2 tocsection-4"><a href="#خوارزميات_الهيكل_المحدب"><span class="tocnumber">1.3</span> <span class="toctext">خوارزميات الهيكل المحدب</span></a></li>
<li class="toclevel-2 tocsection-5"><a href="#استدلال_توسان_و_عقل"><span class="tocnumber">1.4</span> <span class="toctext"><b>استدلال توسان و عقل</b></span></a></li>
<li class="toclevel-2 tocsection-6"><a href="#مشاكل_خوارزمية_الهيكل_المحدب_المتغير_والفوري"><span class="tocnumber">1.5</span> <span class="toctext"><b>مشاكل خوارزمية الهيكل المحدب المتغير والفوري</b></span></a></li>
<li class="toclevel-2 tocsection-7"><a href="#المضلع_البسيط_(Simple_Polygon)"><span class="tocnumber">1.6</span> <span class="toctext">المضلع البسيط (Simple Polygon)</span></a></li>
</ul>
</li>
<li class="toclevel-1 tocsection-8"><a href="#المراجع"><span class="tocnumber">2</span> <span class="toctext">المراجع</span></a></li>
<li class="toclevel-1 tocsection-9"><a href="#قراءة_متعمقة"><span class="tocnumber">3</span> <span class="toctext">قراءة متعمقة</span></a></li>
<li class="toclevel-1 tocsection-10"><a href="#روابط_خارجية"><span class="tocnumber">4</span> <span class="toctext">روابط خارجية</span></a></li>
</ul>
</div>
<h2><span id=".D8.A7.D9.84.D8.AD.D8.A7.D9.84.D8.A9_.D8.A7.D9.84.D9.85.D8.B3.D8.AA.D9.88.D9.8A.D8.A9_.D9.84.D8.A8.D9.86.D8.A7.D8.A1_.D8.A7.D9.84.D9.87.D9.8A.D9.83.D9.84_.D8.A7.D9.84.D9.85.D8.AD.D8.AF.D8.A8"></span><span class="mw-headline" id="الحالة_المستوية_لبناء_الهيكل_المحدب">الحالة المستوية لبناء الهيكل المحدب</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=1" title="Edit section: الحالة المستوية لبناء الهيكل المحدب">edit</a><span class="mw-editsection-bracket">]</span></span></h2>
<p>في البداية لنعتبر أن  الحالة العامة لبناء الهيكل المحدب تكون مدخلاتها عبارة عن مجموعة محددة غير مرتبة من النقاط على مستوى ديكارت. وهناك حالة خاصة للمدخلات سيأتي فيما بعد توضيحها بحيث تكون فيها النقاط المدخلة مرتبة على حدود مضلع بسيط.
</p><p>إذا لم تكن جميع النقاط على نفس الخط، فإن الهيكل المحدب يكون <a href="/wiki/%D9%85%D8%B6%D9%84%D8%B9_%D9%85%D8%AD%D8%AF%D8%A8" title="مضلع محدب">مضلعًا محدبًا</a> رؤسه تكون أحد هذه النقاط. واكثر هذه الحلات شيوعا هي عندما تكون نقاط الهيكل المضلع مرتبة على طول حدوده في اتجاه عقارب الساعة أو عكس عقارب الساعة. و في بعض التطبيقات يكون من الملائم تمثيل مضلع محدب كتقاطع لمجموعة من أنصاف المستويات .
</p>
<h3><span id=".D8.A7.D9.84.D8.AD.D8.AF_.D8.A7.D9.84.D8.A3.D8.AF.D9.86.D9.89_.D9.85.D9.86_.D8.A7.D9.84.D8.AA.D8.B9.D9.82.D9.8A.D8.AF_.D8.A7.D9.84.D8.AD.D8.B3.D8.A7.D8.A8.D9.8A"></span><span class="mw-headline" id="الحد_الأدنى_من_التعقيد_الحسابي">الحد الأدنى من التعقيد الحسابي</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=2" title="Edit section: الحد الأدنى من التعقيد الحسابي">edit</a><span class="mw-editsection-bracket">]</span></span></h3>
<p>إن معرفة التعقيد الحسابي لبناء الهيكل المحدب المضلع لمجموعة من النقاط في فضاء ثنائي الابعاد، يتم تمثيله بسهولة وذلك لامتلاكه نفس التعقيد الحسابي الموجود في خوارزمية <a href="/wiki/%D8%AA%D8%B5%D9%86%D9%8A%D9%81_(%D8%B9%D8%A7%D9%85)" title="تصنيف (عام)">ترتيب</a> النقاط، باستخدام الإسقاط التالي: لكل مجموعة من الارقام  المراد ترتيبها <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},\dots ,x_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x_{1},\dots ,x_{n}}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e5afdbc2d248d8fa9ba2c4f5188d946a0537e753" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.671ex; width:10.11ex; height:2.009ex;" alt="{\displaystyle x_{1},\dots ,x_{n}}"/></span> نقوم بإنشاء النقاط التالية في فضاء ثنائي الابعاد <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msubsup>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msubsup>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>,</mo>
<msubsup>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msubsup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4193029a2cb1d9c71c2a461f25b4889241e2f65" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -1.005ex; width:20.729ex; height:3.176ex;" alt="{\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}"/></span>
</p><p>ولأن كل نقطة من هذه النقاط تقع على <a href="/wiki/%D9%82%D8%B7%D8%B9_%D9%85%D9%83%D8%A7%D9%81%D8%A6" title="قطع مكافئ">القطع المكافئ</a> و الذي يعد بطبيعته <a href="/wiki/%D8%AF%D8%A7%D9%84%D8%A9_%D9%85%D8%AD%D8%AF%D8%A8%D8%A9" title="دالة محدبة">منحنى محدب</a> فانه من السهل ايجاد النقاط التي شكلت الهيكل المحدب حيث تكون على طول حدود القطع المكافئ، و التي يمكن الحصول عليها من خلال ترتيب الأرقام <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},\dots ,x_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x_{1},\dots ,x_{n}}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e5afdbc2d248d8fa9ba2c4f5188d946a0537e753" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.671ex; width:10.11ex; height:2.009ex;" alt="{\displaystyle x_{1},\dots ,x_{n}}"/></span> . و من الواضح ان عملية تحويل الارقام لنقاط تستهلك و<a href="/wiki/%D8%AA%D8%B9%D9%82%D9%8A%D8%AF_%D8%A7%D9%84%D9%88%D9%82%D8%AA" title="تعقيد الوقت">قتا يمكن تمثيله بمنحنى خطي</a>، وهذا يؤكد على عدم امكانية حساب الهيكل المحدب لمجموعة من النقاط في الحالة العامة بوقت اسرع من وقت ترتيب مجموعة من الأرقام.
</p><p><br />
</p><p>إن نموذج شجرة القرار (Decision tree model) مستخدم في اثبات أن الحد الادنى من التعقيد الحسابي المطلوب لترتيب مجموعة من الأرقام هو Ω ( <i>n</i> log <i>n</i> ). و يجب التنويه هنا إلى أن هذا التعقيد الحسابي مرتبط فقط بعمليات المقارنة وليس بالعمليات الحسابية المستخدمة في ترتيب هذه الأرقام. ولكن لا يمكن أبدا استخدام هذه الطريقة لحساب الهياكل المحدبة. ولذلك فان الطريقة الأكثر ملائمة لحساب الهيكل المحدب بنفس التعقيد الحسابي هي شجرة القرار الجبري (algebraic decision tree model) <sup id="cite_ref-ps_1-0" class="reference"><a href="#cite_note-ps-1">[1]</a></sup>
</p><p>و نتيجة لأن <a href="/wiki/%D9%86%D9%85%D9%88%D8%B0%D8%AC_%D8%AD%D9%88%D8%B3%D8%A8%D8%A9" title="نموذج حوسبة">نماذج حسابات الكمبيوتر</a> التي تسمح بترتيب مجموعة من الارقام في وقت حسابي اسرع من <i>O</i>( <i>n</i> log <i>n</i> ) ،مثل استخدام خوارزمية ترتيب الاعداد الصحيحة،  فإن حساب الهياكل المحدبة المستوية يمكن ايجادها بطريقة أسرع: كخوارزمية جرهام للبحث Graham scan algorithm المكونة من عملية ترتيب واحدة متبوعة بعمل إضافي يمكن تمثيله بوقت حسابي خطي.
</p>
<h3><span id=".D8.A7.D9.84.D8.AE.D9.88.D8.A7.D8.B1.D8.B2.D9.85.D9.8A.D8.A7.D8.AA_.D8.A7.D9.84.D9.85.D8.B9.D8.AA.D9.85.D8.AF.D8.A9_.D8.B9.D9.84.D9.89_.D8.A7.D9.84.D9.85.D8.AE.D8.B1.D8.AC.D8.A7.D8.AA"></span><span class="mw-headline" id="الخوارزميات_المعتمدة_على_المخرجات">الخوارزميات المعتمدة على المخرجات</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=3" title="Edit section: الخوارزميات المعتمدة على المخرجات">edit</a><span class="mw-editsection-bracket">]</span></span></h3>
<p>يمكن تصنيف التعقيد الحسابي لبناء الهيكل المحدب بناءً على: عدد النقاط المدخلة - والتي ذكرنا سابقاً أن الحد الأدنى لتعقيدها الحسابي يمكن حصره ب (Ω ( <i>n</i> log <i>n</i> - أو على عدد النقاط التي ستشكل الهيكل المحدب (h) و يمكن تسميتها ب بالخوارزميات المعتمدة على المخرجات و التي تستهلك تعقيد حسابي أكثر فاعلية من Θ ( <i>n</i> log <i>n</i> ) في حال كان h=o(n).
</p><p>ان الحد الأدنى <a href="/wiki/%D8%AA%D8%AD%D9%84%D9%8A%D9%84_%D8%A7%D9%84%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A7%D8%AA" title="تحليل الخوارزميات">للتعقيد الزمني</a> في أسوأ حالة لخوارزميات الهيكل المحدب المعتمدة على المخرجات هي Ω (n log h) في فضاء ثنائي الأبعاد<sup id="cite_ref-ps_1-1" class="reference"><a href="#cite_note-ps-1">[1]</a></sup>. و هناك العديد من الخوارزميات تصل لهذا الحد الأدنى من التعقيد الزمني. وقد تم تقديم أقدمها بواسطة (كركباترك وسايدل) <a href="/wiki/%D8%AF%D9%8A%D9%81%D9%8A%D8%AF_%D8%AC%D9%8A._%D9%83%D9%8A%D8%B1%D9%83%D8%A8%D8%A7%D8%AA%D8%B1%D9%8A%D9%83" title="ديفيد جي. كيركباتريك">Kirkpatrick</a> و <a href="/wiki/%D8%B1%D8%A7%D9%8A%D9%85%D9%88%D9%86%D8%AF_%D8%B2%D8%A7%D9%8A%D8%AF%D9%84" title="رايموند زايدل">Seidel</a> في عام 1986 (الذين أطلقوا عليها اسم خوارزمية الهيكل المحدب القصوى.  (The ultimate convex hull algorithm) ). ومن ثم تم تطوير خوارزمية أبسط بكثير بواسطة  (شان) Chan في عام 1996، و سميت على اسمه ( خوارزمية Chan).
</p>
<h3><span id=".D8.AE.D9.88.D8.A7.D8.B1.D8.B2.D9.85.D9.8A.D8.A7.D8.AA_.D8.A7.D9.84.D9.87.D9.8A.D9.83.D9.84_.D8.A7.D9.84.D9.85.D8.AD.D8.AF.D8.A8"></span><span class="mw-headline" id="خوارزميات_الهيكل_المحدب">خوارزميات الهيكل المحدب</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=4" title="Edit section: خوارزميات الهيكل المحدب">edit</a><span class="mw-editsection-bracket">]</span></span></h3>
<p>خوارزميات الهيكل المحدب المدرجة أدناه مرتبة حسب تاريخ نشرها الأول. و نجد أن التعقيد الحسابي لكل خوارزمية قد مُثِل بعدد النقاط المدخلة n وعدد نقاط الهيكل المحدب h.
</p><p>ملاحظة: قد تكون <i>h</i> مساوية ل <i>n في أسوأ الحالات.</i>
</p>
<ul><li>خوارزمية <b>جارفيس مارس</b> او (<a href="https://en.wikipedia.org/wiki/Gift_wrapping_algorithm" class="extiw" title="en:Gift wrapping algorithm">خوارزمية <b>تغليف الهدايا</b></a>) – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الاكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 و تبعهم آر جارفيس في عام 1973 <a href="/wiki/%D8%AA%D8%AD%D9%84%D9%8A%D9%84_%D8%A7%D9%84%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A7%D8%AA" title="تحليل الخوارزميات">بتعقيد زمني</a> يقدر ب<a href="/wiki/%D8%AA%D9%85%D8%AB%D9%8A%D9%84_O_%D8%A7%D9%84%D9%83%D8%A8%D8%B1%D9%89" title="تمثيل O الكبرى">O</a>(nh). و في أسوأ الحالات يكون <a href="/wiki/%D8%AA%D9%85%D8%AB%D9%8A%D9%84_O_%D8%A7%D9%84%D9%83%D8%A8%D8%B1%D9%89" title="تمثيل O الكبرى">Θ</a> (n <i><sup>2</sup></i>).</li>
<li> خوارزمية <b>جراهام</b> – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما ، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل <a href="/wiki/%D8%B1%D9%88%D9%86%D8%A7%D9%84%D8%AF_%D8%BA%D8%B1%D8%A7%D9%87%D8%A7%D9%85" title="رونالد غراهام">رونالد جراهام</a> في عام 1972. و تستغرق وقتاً يقدر بO ( <i>n</i> ) في حال كانت النقاط المدخلة مرتبة بناء على احد الاحداثيات او بناء على متجه ثابت.</li>
<li>خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 و أ. بيكات 1978. و كخوارزمية الترتيب السريع (Quick sort)  فان تعقيدها الزمني هو O(n log n) و من الممكن ان تتراجع لتصل الى <i>O</i> ( <i>n</i> <sup>2</sup> ) في أسوء الحالات.</li>
<li>خوارزمية <b><a href="/wiki/%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D9%81%D8%B1%D9%82_%D8%AA%D8%B3%D8%AF" title="خوارزمية فرق تسد">فرق تسد</a></b> – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ و فرانكو بريراتا (Franco Preparata and Hong) بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.</li>
<li> خوارزمية اندرو (<b><a href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain" class="extiw" title="wikibooks:Algorithm Implementation/Geometry/Convex hull/Monotone chain">السلسلة الرتيبة</a></b>) – O(n log n) تم نشر هذه الخوارزمية عام 1979 بواسطة اندرو AM Andrew. و يمكن اعتبار هذه الخوارزمية كنوع من خوارزمية جراهام ، التي ترتب النقاط من خلال إحداثياتها. و إذا تم ترتيب النقاط المدخلة فإن الخوارزمية تستغرق وقتاً يقدر ب O (n).</li>
<li> <b>خوارزمية</b> <b>الهيكل</b> <b>المحدب</b> <b>المتزايد</b> - O (n log n) تم صايغتها عام 1984 بواسطة مايكل كاليMichael Kallay.</li>
<li><b>خوارزمية كيركباتريك - سيدل</b> - <i>O</i> ( <i>n</i> log <i>h</i> ) هي أول خوارزمية من الخوارزميات المعتمدة على المخرجات و تستخدم تقنية "marriage-before-conquest" في البرمجة الخطية محدودة الأبعاد. وقد تم نشرها بواسطة <a href="/wiki/%D8%AF%D9%8A%D9%81%D9%8A%D8%AF_%D8%AC%D9%8A._%D9%83%D9%8A%D8%B1%D9%83%D8%A8%D8%A7%D8%AA%D8%B1%D9%8A%D9%83" title="ديفيد جي. كيركباتريك">Kirkpatrick</a> and <a href="/wiki/%D8%B1%D8%A7%D9%8A%D9%85%D9%88%D9%86%D8%AF_%D8%B2%D8%A7%D9%8A%D8%AF%D9%84" title="رايموند زايدل">Seidel</a> عام 1986.</li>
<li><b>خوارزمية تشان</b> - O (n log h) نشرها تيموثي تشين في عام 1996. وهي خوارزمية مثلى من الخوارزميات المعتمدة على المخرجات وتعد أبسط من سابقاتها. و تدمج بين خوارزمية جارفيس واي خوارزمية تستغرق وقتا يقدر ب O(n log n)  -مثل خوارزمية جرهام - .</li></ul>
<h3><span id=".D8.A7.D8.B3.D8.AA.D8.AF.D9.84.D8.A7.D9.84_.D8.AA.D9.88.D8.B3.D8.A7.D9.86_.D9.88_.D8.B9.D9.82.D9.84"></span><span class="mw-headline" id="استدلال_توسان_و_عقل"><b>استدلال توسان و عقل</b></span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=5" title="Edit section: استدلال توسان و عقل">edit</a><span class="mw-editsection-bracket">]</span></span></h3>
<p>غالبًا ما يتم استخدام الاستدلال البسيط التالي كخطوة أولى في تنفيذ خوارزميات الهيكل المحدب لتحسين الأداء. وقد قام <a href="/wiki/%D8%B3%D9%84%D9%8A%D9%85_%D8%B9%D9%82%D9%84" title="سليم عقل">سليم عقل</a> و توسان باستحداث طريقة فعالة لايجاد الهيكل المحدب و تعتمد هذه الطريقة على استبعاد اكبر عدد ممكن من النقاط التي لا يمكن ان تشكل الهيكل المحدب من خلال إيجاد النقطتين اللتين تحتويان على أدنى وأعلى إحداثيات في محور x ، و أدنى وأعلى نقطتي إحداث في محور y. (كل من هذه العمليات تستغرق <a href="/wiki/%D8%AA%D9%85%D8%AB%D9%8A%D9%84_O_%D8%A7%D9%84%D9%83%D8%A8%D8%B1%D9%89" title="تمثيل O الكبرى">O</a>(n)) و هذه النقاط الأربع تشكل <a href="/wiki/%D8%B1%D8%A8%D8%A7%D8%B9%D9%8A_%D8%A3%D8%B6%D9%84%D8%A7%D8%B9" title="رباعي أضلاع">محدباً رباعياً</a> ، و جميع النقاط التي تقع في هذا الرباعي (باستثناء الرؤوس الأربعة المختارة في البداية) ليست جزءًا من الهيكل المحدب أو يمكن أن نضيف الى الشكل الرباعي النقاط التي تحتوي على أصغر وأكبر مجاميع من إحداثيات x و y وكذلك تلك التي تحتوي على أصغر وأكبر اختلافات في إحداثيات x و y ، و هطذا يصبح لدينا محدب ثماني غير منتظم ، ثم نقوم بالتخلص من جميع النقاط التي بداخل الشكل الثماني بأمان.
</p><p>و إذا كانت النقاط عبارة عن متغيرات عشوائية -وهذا يكون فقط لفئة معينة و شائعة من دوال الكثافة الاحتمالية- فإن عملية التخلص من النقاط التي ذكرناها في الخطوة السابقة ستجعل الخوارزمية تستغرق زمناً خطياً، و حتى في اسوء الحالات فان الوقت المستغرق قد يصل الى <i>n</i> <sup>2</sup> .<sup id="cite_ref-2" class="reference"><a href="#cite_note-2">[2]</a></sup>
</p>
<h3><span id=".D9.85.D8.B4.D8.A7.D9.83.D9.84_.D8.AE.D9.88.D8.A7.D8.B1.D8.B2.D9.85.D9.8A.D8.A9_.D8.A7.D9.84.D9.87.D9.8A.D9.83.D9.84_.D8.A7.D9.84.D9.85.D8.AD.D8.AF.D8.A8_.D8.A7.D9.84.D9.85.D8.AA.D8.BA.D9.8A.D8.B1_.D9.88.D8.A7.D9.84.D9.81.D9.88.D8.B1.D9.8A"></span><span class="mw-headline" id="مشاكل_خوارزمية_الهيكل_المحدب_المتغير_والفوري"><b>مشاكل خوارزمية الهيكل المحدب المتغير والفوري</b></span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=6" title="Edit section: مشاكل خوارزمية الهيكل المحدب المتغير والفوري">edit</a><span class="mw-editsection-bracket">]</span></span></h3>
<p>ان في كل ما تم ذكره سابقا كانت النقاط المدخلة معروفة مسبقا، و لذلك فإننا يجب أن نأخذ بعين الاعتبار الخطوتين التاليتين عند بناء الهيكل المحدب:<sup id="cite_ref-ps_1-2" class="reference"><a href="#cite_note-ps-1">[1]</a></sup>
</p>
<ul><li><b>مشاكل بناء الهيكل المحدب <a href="/wiki/%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D9%81%D9%88%D8%B1%D9%8A%D8%A9" title="خوارزمية فورية">الفوري</a></b>: حين يتم وصول نقاط الإدخال بالتتابع واحدة تلو الأخرى. سيتم اعادة حساب الهيكل المحدب لمجموعة النقاط الحالية بكفاءة، بعد إدخال كل نقطة.  </li>
<li><b>الصيانة الدورية للهيكل المحدب المتغير</b>: يجب تحديث الهيكل المحدب بعد كل عملية إدخال أو حذف. وذلك لإمكانية ادخال النقاط و حذفها بالتسلسل.</li></ul>
<p>قد يؤدي إدخال نقطة إلى زيادة عدد رؤوس الهيكل محدب بمقدار 1 على الأكثر ، والعكس صحيح بالنسبة للحذف.
</p><p>يمكن التعامل مع النقاط المدخلة للهيكل المحدب عبر الإنترنت خلال وقت يقدر ب O (log n) لكل نقطة ، و هذا على أفضل تقدير. و يمكن التعامل مع النقاط المدخلة للهيكل المحدب المتغير خلال وقت يقدر ب O (log <sup>2</sup> <i>n</i> ) لكل عملية. <sup id="cite_ref-ps_1-3" class="reference"><a href="#cite_note-ps-1">[1]</a></sup>
</p>
<h3><span id=".D8.A7.D9.84.D9.85.D8.B6.D9.84.D8.B9_.D8.A7.D9.84.D8.A8.D8.B3.D9.8A.D8.B7_.28Simple_Polygon.29"></span><span class="mw-headline" id="المضلع_البسيط_(Simple_Polygon)">المضلع البسيط (<a href="/wiki/Simple_polygon" class="mw-redirect" title="Simple polygon">Simple Polygon</a>)</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=7" title="Edit section: المضلع البسيط (Simple Polygon)">edit</a><span class="mw-editsection-bracket">]</span></span></h3>
<p>يتم تقسيم الهيكل المحدب <a href="/wiki/%D9%85%D8%B6%D9%84%D8%B9_%D8%A8%D8%B3%D9%8A%D8%B7" title="مضلع بسيط">لمضلع بسيط</a> إلى أجزاء من خلال جعل أحدها هو المضلع نفسه و أما باقي الهيكل فعبارة عن <i>جيوب</i> تحدها قطعة من حدود المضلع وحافة واحدة من الهيكل. على الرغم من نشر العديد من الخوارزميات لبناء الهيكل المحدب لمضلع بسيط ، فإن نصفها تقريبًا غير صحيح. <sup id="cite_ref-3" class="reference"><a href="#cite_note-3">[3]</a></sup> ويعد مكالوم وآفيس أول من قدم خوارزمية صحيحة. <sup id="cite_ref-4" class="reference"><a href="#cite_note-4">[4]</a></sup> وقد استخدم جرهام و ياو ( <a href="#CITEREFGrahamYao1983">Graham & Yao (1983)</a> ) و لي (<a href="#CITEREFLee1983">Lee (1983)</a>) <a href="/wiki/%D9%85%D9%83%D8%AF%D8%B3_(%D8%A8%D9%86%D9%8A%D8%A9_%D8%A8%D9%8A%D8%A7%D9%86%D8%A7%D8%AA)" title="مكدس (بنية بيانات)">بنية بيانات المكدس</a> (stack data structure ) واحدة من أجل تبسيط الخوارزمية وتسير هذه الخوارزمية على المضلع في اتجاه عقارب الساعة ، بدءً من النقطة الواقعة أقصى اليسار وخلال ذلك تقوم بتخزين النقاط الموجودة على المحدب ( تلك التي لم يتم تحديدها بعد على أنها داخل الجيوب) في المكدس. في كل خطوة ، تتبع الخوارزمية مسارًا على طول المضلع من قمة المكدس إلى النقطة التالية على ألا تكون ضمن أحد الجيوب المجاورة لأعلى المكدس. و طالما أن اخر نقطتين في أعلى المكدس لا يشكلان محدبا مع النقطة الجديدة نقوم بعملية اخراج النقطة العلوية من المكدس ، ثم ادخال النقطة الجديدة. عندما تنتهي دورة قراءة الخوارزمية للنقاط في اتجاه عقارب الساعة نكون قد عدنا إلى نقطة البداية، وهنا ستكون نتيجة الخوارزمية عبارة عن تسلسل النقاط الموجودة في المكدس وهي ذاتها نقاط المكونة الهيكل. <sup id="cite_ref-5" class="reference"><a href="#cite_note-5">[5]</a></sup> <sup id="cite_ref-6" class="reference"><a href="#cite_note-6">[6]</a></sup>
</p>
<h2><span id=".D8.A7.D9.84.D9.85.D8.B1.D8.A7.D8.AC.D8.B9"></span><span class="mw-headline" id="المراجع">المراجع</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=8" title="Edit section: المراجع">edit</a><span class="mw-editsection-bracket">]</span></span></h2>
<style data-mw-deduplicate="TemplateStyles:r56810696">.mw-parser-output .reflist{font-size:90%;margin-bottom:0.5em;list-style-type:decimal;overflow-y:auto;max-height:300px}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}@media print{.mw-parser-output .reflist{overflow-y:visible!important;max-height:none!important}}</style><div class="reflist">
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-ps-1"><span class="mw-cite-backlink">↑ <a href="#cite_ref-ps_1-0"><sup><i><b>أ</b></i></sup></a> <a href="#cite_ref-ps_1-1"><sup><i><b>ب</b></i></sup></a> <a href="#cite_ref-ps_1-2"><sup><i><b>ت</b></i></sup></a> <a href="#cite_ref-ps_1-3"><sup><i><b>ث</b></i></sup></a></span> <span class="reference-text">Preparata, Shamos, <i>Computational Geometry</i>, Chapter "Convex Hulls: Basic Algorithms"</span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><a href="/w/index.php?title=Luc_Devroye&action=edit&redlink=1" class="new" title="Luc Devroye (الصفحة غير موجودة)">Luc Devroye</a> and <a href="/w/index.php?title=Godfried_Toussaint&action=edit&redlink=1" class="new" title="Godfried Toussaint (الصفحة غير موجودة)">Godfried Toussaint</a>, "A note on linear expected time algorithms for finding convex hulls," <i>Computing</i>, Vol. 26, 1981, pp. 361-366.</span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r57313094">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}</style><cite id="CITEREFAloupis" class="citation web cs1">Aloupis, Greg، <a rel="nofollow" class="external text" href="http://cgm.cs.mcgill.ca/~athens/cs601/">"A History of Linear-time Convex Hull Algorithms for Simple Polygons"</a><span class="reference-accessdate">، اطلع عليه بتاريخ 11 أكتوبر 2020</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=A+History+of+Linear-time+Convex+Hull+Algorithms+for+Simple+Polygons&rft.aulast=Aloupis&rft.aufirst=Greg&rft_id=http%3A%2F%2Fcgm.cs.mcgill.ca%2F~athens%2Fcs601%2F&rfr_id=info%3Asid%2Far.wikipedia.org%3A%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84+%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8" class="Z3988"></span></span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r57313094"/><cite id="CITEREFMcCallumAvis1979" class="citation cs2">McCallum, Duncan؛ <a href="/wiki/David_Avis" class="mw-redirect" title="David Avis">Avis, David</a> (1979)، "A linear algorithm for finding the convex hull of a simple polygon"، <i><a href="/w/index.php?title=Information_Processing_Letters&action=edit&redlink=1" class="new" title="Information Processing Letters (الصفحة غير موجودة)">Information Processing Letters</a></i>، <b>9</b> (5): 201–206، <a href="/wiki/%D9%85%D8%B9%D8%B1%D9%81_%D8%A7%D9%84%D8%BA%D8%B1%D8%B6_%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A" title="معرف الغرض الرقمي">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2879%2990069-3">10.1016/0020-0190(79)90069-3</a>، <a href="/wiki/%D9%85%D8%A7%D8%AB%D9%85%D8%A7%D8%AA%D9%8A%D9%83%D9%84_%D8%B1%D9%8A%D9%81%D9%8A%D9%88%D8%B2" title="ماثماتيكل ريفيوز">MR</a> <a rel="nofollow" class="external text" href="//www.ams.org/mathscinet-getitem?mr=0552534">0552534</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+Processing+Letters&rft.atitle=A+linear+algorithm+for+finding+the+convex+hull+of+a+simple+polygon&rft.volume=9&rft.issue=5&rft.pages=201-206&rft.date=1979&rft_id=info%3Adoi%2F10.1016%2F0020-0190%2879%2990069-3&rft_id=%2F%2Fwww.ams.org%2Fmathscinet-getitem%3Fmr%3D552534%23id-name%3DMR&rft.aulast=McCallum&rft.aufirst=Duncan&rft.au=Avis%2C+David&rfr_id=info%3Asid%2Far.wikipedia.org%3A%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84+%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8" class="Z3988"></span></span>
</li>
<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r57313094"/><cite id="CITEREFGrahamYao1983" class="citation cs2"><a href="/wiki/Ronald_Graham" class="mw-redirect" title="Ronald Graham">Graham, Ronald L.</a>؛ <a href="/w/index.php?title=Frances_Yao&action=edit&redlink=1" class="new" title="Frances Yao (الصفحة غير موجودة)">Yao, F. Frances</a> (1983)، "Finding the convex hull of a simple polygon"، <i><a href="/w/index.php?title=Journal_of_Algorithms&action=edit&redlink=1" class="new" title="Journal of Algorithms (الصفحة غير موجودة)">Journal of Algorithms</a></i>، <b>4</b> (4): 324–331، <a href="/wiki/%D9%85%D8%B9%D8%B1%D9%81_%D8%A7%D9%84%D8%BA%D8%B1%D8%B6_%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A" title="معرف الغرض الرقمي">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-6774%2883%2990013-5">10.1016/0196-6774(83)90013-5</a>، <a href="/wiki/%D9%85%D8%A7%D8%AB%D9%85%D8%A7%D8%AA%D9%8A%D9%83%D9%84_%D8%B1%D9%8A%D9%81%D9%8A%D9%88%D8%B2" title="ماثماتيكل ريفيوز">MR</a> <a rel="nofollow" class="external text" href="//www.ams.org/mathscinet-getitem?mr=0729228">0729228</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Algorithms&rft.atitle=Finding+the+convex+hull+of+a+simple+polygon&rft.volume=4&rft.issue=4&rft.pages=324-331&rft.date=1983&rft_id=info%3Adoi%2F10.1016%2F0196-6774%2883%2990013-5&rft_id=%2F%2Fwww.ams.org%2Fmathscinet-getitem%3Fmr%3D729228%23id-name%3DMR&rft.aulast=Graham&rft.aufirst=Ronald+L.&rft.au=Yao%2C+F.+Frances&rfr_id=info%3Asid%2Far.wikipedia.org%3A%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84+%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8" class="Z3988"></span></span>
</li>
<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r57313094"/><cite id="CITEREFLee1983" class="citation cs2">Lee, D. T. (1983)، "On finding the convex hull of a simple polygon"، <i>International Journal of Computer and Information Sciences</i>، <b>12</b> (2): 87–98، <a href="/wiki/%D9%85%D8%B9%D8%B1%D9%81_%D8%A7%D9%84%D8%BA%D8%B1%D8%B6_%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A" title="معرف الغرض الرقمي">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00993195">10.1007/BF00993195</a>، <a href="/wiki/%D9%85%D8%A7%D8%AB%D9%85%D8%A7%D8%AA%D9%8A%D9%83%D9%84_%D8%B1%D9%8A%D9%81%D9%8A%D9%88%D8%B2" title="ماثماتيكل ريفيوز">MR</a> <a rel="nofollow" class="external text" href="//www.ams.org/mathscinet-getitem?mr=0724699">0724699</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=International+Journal+of+Computer+and+Information+Sciences&rft.atitle=On+finding+the+convex+hull+of+a+simple+polygon&rft.volume=12&rft.issue=2&rft.pages=87-98&rft.date=1983&rft_id=info%3Adoi%2F10.1007%2FBF00993195&rft_id=%2F%2Fwww.ams.org%2Fmathscinet-getitem%3Fmr%3D724699%23id-name%3DMR&rft.aulast=Lee&rft.aufirst=D.+T.&rfr_id=info%3Asid%2Far.wikipedia.org%3A%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84+%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8" class="Z3988"></span></span>
</li>
</ol></div></div>
<h2><span id=".D9.82.D8.B1.D8.A7.D8.A1.D8.A9_.D9.85.D8.AA.D8.B9.D9.85.D9.82.D8.A9"></span><span class="mw-headline" id="قراءة_متعمقة">قراءة متعمقة</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=9" title="Edit section: قراءة متعمقة">edit</a><span class="mw-editsection-bracket">]</span></span></h2>
<ul><li>توماس إتش كورمن ، تشارلز إي ليسرسون ، <a href="/wiki/%D8%B1%D9%88%D9%86%D8%A7%D9%84%D8%AF_%D8%B1%D9%8A%D9%81%D8%B3%D8%AA" title="رونالد ريفست">رونالد إل ريفيست</a> ، <a href="/wiki/%D9%83%D9%84%D9%8A%D9%81%D9%88%D8%B1%D8%AF_%D8%B4%D8%AA%D8%A7%D9%8A%D9%86" title="كليفورد شتاين">وكليفورد شتاين</a> . <i><a href="/wiki/%D9%85%D9%82%D8%AF%D9%85%D8%A9_%D9%81%D9%8A_%D8%A7%D9%84%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A7%D8%AA_(%D9%83%D8%AA%D8%A7%D8%A8)" title="مقدمة في الخوارزميات (كتاب)">مقدمة في الخوارزميات</a></i> ، الإصدار الثاني. مطبعة معهد ماساتشوستس للتكنولوجيا ومكجرو هيل ، 2001.(<span dir="rtl">ردمك <span dir="ltr"><a href="/wiki/%D8%AE%D8%A7%D8%B5:%D9%85%D8%B5%D8%A7%D8%AF%D8%B1_%D9%83%D8%AA%D8%A7%D8%A8/0-262-03293-7" title="خاص:مصادر كتاب/0-262-03293-7">0-262-03293-7</a></span></span>)<a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">رقم ISBN</a> <a href="/wiki/%D8%AE%D8%A7%D8%B5:%D9%85%D8%B5%D8%A7%D8%AF%D8%B1_%D9%83%D8%AA%D8%A7%D8%A8/0-262-03293-7" title="خاص:مصادر كتاب/0-262-03293-7">0-262-03293-7</a> . القسم 33.3: العثور على بدن محدب ، ص. 947-957 –</li>
<li>فرانكو ب .بيراتا ، إس جيه هونغ . <i>هياكل محدبة من مجموعات محدودة من النقاط في بعدين وثلاثة أبعاد</i> ، Commun. ACM ، المجلد. 20 ، لا. 2 ، ص. 87-93 – 1977.</li>
<li><bdi><cite class="citation book cs1" data-ve-ignore="true" id="CITEREFMark_de_BergMarc_van_KreveldMark_OvermarsOtfried_Schwarzkopf2000"><a href="/wiki/%D8%AE%D8%A7%D8%B5:BookSources_/_978-3-540-65620-3" class="new" title="خاص:BookSources / 978-3-540-65620-3 (الصفحة غير موجودة)">978-3-540-65620-3</a></cite></bdi> القسم 1.1: مثال: أجسام محدبة (يصف الخوارزميات الكلاسيكية للأجسام المحدبة ثنائية الأبعاد). الفصل 11: هياكل محدبة: ص. 235-250 – يصف خوارزمية عشوائية لهياكل محدبة ثلاثية الأبعاد بسبب كلاركسون وشور).</li></ul>
<h2><span id=".D8.B1.D9.88.D8.A7.D8.A8.D8.B7_.D8.AE.D8.A7.D8.B1.D8.AC.D9.8A.D8.A9"></span><span class="mw-headline" id="روابط_خارجية">روابط خارجية</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8&action=edit&section=10" title="Edit section: روابط خارجية">edit</a><span class="mw-editsection-bracket">]</span></span></h2>
<table role="presentation" class="metadata mbox-small sisterlinks" style="background-color:#f9f9f9;border:1px solid #C0C0C0;color:#000">
<tbody><tr>
<td class="mbox-image"><a href="/wiki/%D8%AE%D8%A7%D8%B5:%D8%A8%D8%AD%D8%AB/%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%87%D9%8A%D9%83%D9%84_%D8%A7%D9%84%D9%85%D8%AD%D8%AF%D8%A8" title="مشاريع شقيقة"><img alt="مشاريع شقيقة" src="//upload.wikimedia.org/wikipedia/commons/thumb/b/b3/Wikibooks-logo-ar-noslogan.svg/25px-Wikibooks-logo-ar-noslogan.svg.png" decoding="async" width="25" height="25" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/b3/Wikibooks-logo-ar-noslogan.svg/38px-Wikibooks-logo-ar-noslogan.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/b3/Wikibooks-logo-ar-noslogan.svg/50px-Wikibooks-logo-ar-noslogan.svg.png 2x" data-file-width="400" data-file-height="400" /></a></td>
<td class="mbox-text plainlist">اقرأ كتاب يتعلق <b><a href="https://ar.wikibooks.org/wiki/Algorithm_Implementation" class="extiw" title="b:Algorithm Implementation">بخوارزمية الهيكل المحدب</a></b> في <a href="/wiki/%D9%88%D9%8A%D9%83%D9%8A_%D8%A7%D9%84%D9%83%D8%AA%D8%A8" title="ويكي الكتب">ويكي الكتب</a>.</td></tr>
</tbody></table>
<p><br />
</p>
<ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r57313094"/>Weisstein, Eric W. "Convex Hull". MathWorld.</li>
<li><a rel="nofollow" class="external text" href="https://www.cgal.org/Part/ConvexHullAlgorithms">2D, 3D, and dD Convex Hull</a> in CGAL, the Computational Geometry Algorithms Library</li>
<li><a rel="nofollow" class="external text" href="http://www.qhull.org/">Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection</a></li>
<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html">Demo as Flash swf</a>, Jarvis, Graham, Quick (divide and conquer) and Chan algorithms</li>
<li><a rel="nofollow" class="external text" href="http://wayback.vefsafn.is/wayback/20130721095350/http://michal.is/projects/convex%2Dhull%2Dgift%2Dwrapping%2Dmethod/">Gift wrapping algorithm in C#</a></li></ul></div>' |
ما إذا كان التعديل قد تم عمله من خلال عقدة خروج تور (tor_exit_node) | false |
طابع زمن التغيير ليونكس (timestamp) | '1668177884' |
