مسح غراهام

مسح غراهام هو طريقة لإيجاد الغلاف المحدب لمجموعة محدودة من النقاط في المستوى، بتعقيد زمني قدره O ( n log n ). سُمّي هذا المسح نسبةً إلى رونالد غراهام ، الذي نشر الخوارزمية الأصلية عام 1972. ^{[ 1 ]} تجد الخوارزمية جميع رؤوس الغلاف المحدب مرتبةً على طول حدوده. وتستخدم مكدسًا لاكتشاف وإزالة التقعرات في الحدود بكفاءة.

تتمثل الخطوة الأولى في هذه الخوارزمية في إيجاد النقطة ذات أصغر قيمة إحداثية y. إذا وُجدت أصغر قيمة إحداثية y في أكثر من نقطة ضمن المجموعة، تُختار النقطة ذات أصغر قيمة إحداثية x من بين النقاط المرشحة. لنُسمِّ هذه النقطة P. تستغرق هذه الخطوة زمنًا قدره O ( n )، حيث n هو عدد النقاط المعنية.

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

لا يتطلب الترتيب حسب الزاوية حساب الزاوية. من الممكن استخدام أي دالة للزاوية تكون رتيبة في الفترة${\displaystyle [0,\pi ]}$يمكن حساب جيب التمام بسهولة باستخدام الضرب القياسي ، أو يمكن استخدام ميل الخط. إذا كانت الدقة العددية مهمة، فإن دالة المقارنة المستخدمة في خوارزمية الفرز تستخدم إشارة الضرب الاتجاهي لتحديد الزوايا النسبية.

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

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

مرة أخرى، لا يتطلب تحديد ما إذا كانت ثلاث نقاط تشكل "انعطافًا لليسار" أو "انعطافًا لليمين" حساب الزاوية الفعلية بين القطعتين المستقيمتين، ويمكن تحقيقه في الواقع باستخدام العمليات الحسابية البسيطة فقط. بالنسبة لثلاث نقاط${\displaystyle P_{1}=(x_{1},y_{1})}$،${\displaystyle P_{2}=(x_{2},y_{2})}$و${\displaystyle P_{3}=(x_{3},y_{3})}$، احسب الإحداثي z للجداء الاتجاهي للمتجهين${\displaystyle {\overrightarrow {P_{1}P_{2}}}}$و${\displaystyle {\overrightarrow {P_{1}P_{3}}}}$، وهو ما يُعطى بالتعبير${\displaystyle (x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})}$إذا كانت النتيجة 0، فإن النقاط تقع على خط مستقيم واحد؛ وإذا كانت موجبة، فإن النقاط الثلاث تشكل "انعطافًا لليسار" أو اتجاهًا عكس عقارب الساعة، وإلا فإنها تشكل "انعطافًا لليمين" أو اتجاهًا مع عقارب الساعة (بالنسبة للنقاط المرقمة عكس عقارب الساعة).

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

تستغرق عملية فرز النقاط وقتًا مقداره O( n log n ). قد يبدو أن التعقيد الزمني للحلقة هو O( n² )، لأنها تعود لكل نقطة للتحقق مما إذا كانت أي من النقاط السابقة قد انعطفت يمينًا، ولكنه في الواقع O( n )، لأن كل نقطة تُؤخذ في الاعتبار مرتين على الأكثر. لا يمكن أن تظهر كل نقطة إلا مرة واحدة ^.${\displaystyle (x_{2},y_{2})}$في "انعطاف يساري" (لأن الخوارزمية تتقدم إلى النقطة التالية)${\displaystyle (x_{3},y_{3})}$وبعد ذلك)، وكنقطة${\displaystyle (x_{2},y_{2})}$في "انعطاف يمين" (لأن النقطة${\displaystyle (x_{2},y_{2})}$(تمت إزالته). وبالتالي فإن التعقيد الزمني الإجمالي هو O( n log n )، لأن وقت الفرز يهيمن على وقت حساب الغلاف المحدب فعليًا.

تستخدم الشفرة الزائفة أدناه الدالة ccw: ccw > 0 إذا كانت النقاط الثلاث تدور عكس اتجاه عقارب الساعة، وccw < 0 إذا كانت تدور مع اتجاه عقارب الساعة، وccw = 0 إذا كانت النقاط على استقامة واحدة. (في التطبيقات العملية، إذا كانت الإحداثيات أعدادًا حقيقية عشوائية، تتطلب الدالة مقارنة دقيقة للأعداد العشرية، ويجب الحذر من الحالات الشاذة العددية للنقاط "شبه" على استقامة واحدة).

ثم يتم تخزين النتيجة في stack.

لنفترض أن النقاط هي قائمة النقاط، ولنفترض أن المكدس فارغ. أوجد أدنى إحداثي y وأقصى نقطة إلى اليسار، وتُسمى P0. رتب النقاط حسب الزاوية القطبية مع P0، وإذا كانت عدة نقاط لها نفس الزاوية القطبية، فاحتفظ فقط بأبعد نقطة. لكل نقطة في النقاط: # قم بإزالة النقطة الأخيرة من المكدس إذا استدرنا باتجاه عقارب الساعة للوصول إلى هذه النقطة طالما أن عدد عناصر المكدس أكبر من 1 وكان اتجاه دوران (العنصر التالي لأعلى المكدس، أعلى المكدس، النقطة) عكس اتجاه عقارب الساعة أقل من أو يساوي 0: اسحب عنصرًا من المكدس، ثم أضف النقطة إلى المكدس .

الآن تحتوي المجموعة على الغلاف المحدب، حيث تكون النقاط موجهة عكس اتجاه عقارب الساعة و P0 هي النقطة الأولى.

هنا، next_to_top()توجد دالة لإرجاع العنصر الموجود أسفل أعلى المكدس بمقدار عنصر واحد، دون تغيير المكدس، وبالمثل، top()لإرجاع العنصر العلوي.

تم اقتباس هذه الشفرة الزائفة من كتاب مقدمة في الخوارزميات .

تنطبق الفكرة الأساسية نفسها حتى لو تم ترتيب المدخلات حسب الإحداثي السيني بدلاً من الزاوية، وتم حساب الهيكل على مرحلتين، حيث ينتج الجزء العلوي والسفلي منه على التوالي. وقد ابتكر هذا التعديل إيه إم أندرو. ^{[ 2 ]} وله نفس الخصائص الأساسية لمسح غراهام. ^{[ 3 ]}

تضمنت الوصفة الأصلية لغراهام فرز النقاط حول نقطة داخلية من الغلاف المحدب ، بدلاً من إحدى رؤوسه. ^{[ 1 ]} وباستخدام نفس نقطة الارتكاز لخوارزمية الفرز، فإن توصيل جميع النقاط الأخرى بترتيبها المُفرز حول هذه النقطة، بدلاً من تنفيذ الخطوات المتبقية من مسح غراهام، ينتج عنه مضلع نجمي الشكل ، وهو عبارة عن تحويل مضلعي للمدخلات. ^{[ 4 ]}

تُشبه تقنية التجميع المستخدمة في مسح غراهام إلى حد كبير تلك المستخدمة في مسألة أقرب القيم الأصغر ، ويمكن أيضًا استخدام خوارزميات متوازية لأقرب القيم الأصغر (مثل مسح غراهام) لحساب الأغلفة المحدبة لتسلسلات النقاط المرتبة بكفاءة. ^{[ 5 ]}

تُعدّ المتانة العددية مسألةً يجب معالجتها في الخوارزميات التي تستخدم حسابات الفاصلة العائمة ذات الدقة المحدودة . حللت ورقة بحثية نُشرت عام ٢٠٠٤ استراتيجية تزايدية بسيطة، يُمكن استخدامها، على وجه الخصوص، لتنفيذ مسح غراهام. ^{[ ٦ ]} لم يكن الهدف المعلن للورقة البحثية تحليل الخوارزمية تحديدًا، بل تقديم مثال نموذجي لما قد يفشل وكيفية حدوثه نتيجةً لحسابات الفاصلة العائمة في الهندسة الحسابية . ^{[ ٦ ]} لاحقًا، قام كلٌّ من د. جيانغ ون. ف. ستيوارت ^{[ ٧ ]} بتوسيع هذا الموضوع، وباستخدام تحليل الخطأ العكسي، توصلا إلى استنتاجين رئيسيين. الأول هو أن الغلاف المحدب مسألة جيدة التكييف ، وبالتالي يُمكن توقع خوارزميات تُنتج إجابةً ضمن هامش خطأ معقول. ثانيًا، يوضحون أن تعديل مسح غراهام الذي يسمونه غراهام-فورتشن (الذي يتضمن أفكار ستيفن فورتشن للاستقرار العددي ^{[ 8 ]} ) يتغلب على مشاكل الدقة المحدودة والبيانات غير الدقيقة "إلى أي مدى يمكن القيام بذلك".

• خوارزميات الغلاف المحدب

• كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001) [1990]. "33.3: إيجاد الغلاف المحدب". مقدمة في الخوارزميات (  الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 949-955 . ISBN  0-262-03293-7.