خوارزمية خط المسح

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

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

أدى تطبيق هذا النهج إلى طفرة نوعية في التعقيد الحسابي للخوارزميات الهندسية، وذلك عندما قدم شاموس وهوي خوارزميات لتقاطع القطع المستقيمة في المستوى عام 1976. وقد وصفا تحديدًا كيف أن الجمع بين نهج خط المسح وهياكل البيانات الفعالة ( أشجار البحث الثنائية ذاتية التوازن ) يُتيح اكتشاف ما إذا كانت هناك تقاطعات بين N قطعة مستقيمة في المستوى بتعقيد زمني قدره O ( N log N ) . [ ^{1 ] وتستخدم} خوارزمية بنتلي-أوتمان، ذات الصلة الوثيقة، تقنية خط المسح للإبلاغ عن جميع التقاطعات K بين أي N قطعة مستقيمة في المستوى بتعقيد زمني قدره O(( N + K ) log N ) وتعقيد مكاني قدره O( N ) . ^{[ 2 ]}

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

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

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

يمكن تعميم النهج الشامل ليشمل أبعادًا أعلى. ^{[ 4 ]}