مشبك الخط
في مجال رسومات الحاسوب ، يُعرف قص الخطوط بأنه عملية إزالة الخطوط أو أجزاء منها خارج منطقة الاهتمام ( نافذة العرض أو حجم العرض ). وعادةً ما تتم إزالة أي جزء من الخط يقع خارج منطقة العرض.
هناك خوارزميتان شائعتان لقص الخطوط: كوهين-ساذرلاند وليانغ -بارسكي .
تتألف طريقة قص الخطوط من عدة أجزاء. تُجرى اختبارات على قطعة خطية معينة لتحديد ما إذا كانت تقع خارج منطقة العرض أو الحجم. ثم تُجرى حسابات التقاطع مع حد قص واحد أو أكثر. [ 1 ] ويتم تحديد أي جزء من الخط يقع داخل أو خارج حجم القص من خلال معالجة نقاط نهاية الخط بالنسبة للتقاطع.
كوهين-ساذرلاند
في مجال رسومات الحاسوب، تُعدّ خوارزمية كوهين-ساذرلاند (نسبةً إلى داني كوهين وإيفان ساذرلاند ) خوارزمية لقص الخطوط. تقسم هذه الخوارزمية الفضاء ثنائي الأبعاد إلى 9 مناطق، لا يظهر منها سوى الجزء الأوسط (منطقة العرض).
في عام 1967، أدى عمل محاكاة الطيران الذي قام به داني كوهين إلى تطوير خوارزميات قص الخطوط ثنائية وثلاثية الأبعاد لرسومات الكمبيوتر كوهين-ساذرلاند، والتي تم إنشاؤها بالتعاون مع إيفان ساذرلاند.
ليانغ-بارسكي
تستخدم خوارزمية ليانغ-بارسكي المعادلة البارامترية للخط والمتباينات التي تصف نطاق مربع القص لتحديد نقاط التقاطع بين الخط ومربع القص. وبناءً على هذه النقاط، تُحدد الخوارزمية أي جزء من الخط يجب رسمه. تُعد هذه الخوارزمية أكثر كفاءة من خوارزمية كوهين-ساذرلاند، إلا أن خوارزمية كوهين-ساذرلاند تُجري عمليات القبول والرفض البسيطة بسرعة أكبر بكثير، لذا يُنصح باستخدامها إذا كانت معظم الخطوط التي تحتاج إلى قصها تقع داخل أو خارج نافذة القص .
سايروس-بيك
يشبه هذا إلى حد كبير خوارزمية ليانغ-بارسكي لقص الخطوط. والفرق هو أن ليانغ-بارسكي عبارة عن نسخة مبسطة من خوارزمية سايروس-بيك تم تحسينها لنافذة قص مستطيلة.
تهدف خوارزمية سايروس-بيك بشكل أساسي إلى قص خط في شكل بارامتري مقابل مضلع محدب في بعدين أو مقابل متعدد السطوح محدب في ثلاثة أبعاد . [ 2 ]
نيكول-لي-نيكول
خوارزمية نيكول-لي-نيكول هي خوارزمية سريعة لقص الخطوط، تقلل من احتمالية قص قطعة خطية واحدة عدة مرات، كما قد يحدث في خوارزمية كوهين-ساذرلاند. تُقسّم نافذة القص إلى عدة مناطق مختلفة، بناءً على موضع نقطة البداية للخط المراد قصه.
قص سريع
تتشابه هذه الخوارزمية مع خوارزمية كوهين-ساذرلاند. تُصنَّف مواقع البداية والنهاية بحسب الجزء الذي تشغله من شبكة المناطق التسع. وتنتقل عبارة switch كبيرة إلى معالج متخصص لتلك الحالة. في المقابل، قد تضطر خوارزمية كوهين-ساذرلاند إلى التكرار عدة مرات لمعالجة الحالة نفسها. [ 3 ]
خوارزمية O (lg N )
تصنف هذه الخوارزمية الرؤوس على الخط المعطى بالصيغة الضمنية p : ax + by + c = 0. وبما أن المضلع يُفترض أنه محدب وأن الرؤوس مرتبة باتجاه عقارب الساعة أو عكس اتجاه عقارب الساعة، فيمكن تطبيق البحث الثنائي ، مما يؤدي إلى تعقيد زمني قدره O (lg N ). [ 4 ]
سكالا
تعتمد هذه الخوارزمية على الإحداثيات المتجانسة والازدواجية . [ 5 ] يمكن استخدامها لقص الخطوط أو القطع المستقيمة على نافذة مستطيلة، وكذلك على مضلع محدب. تعتمد الخوارزمية على تصنيف رأس نافذة القص مقابل نصف فضاء مُعطى بخط p : ax + by + c = 0. تحدد نتيجة التصنيف الحواف التي يتقاطع معها الخط p . الخوارزمية بسيطة وسهلة التنفيذ وقابلة للتوسيع لتشمل نافذة محدبة أيضًا. يمكن حساب الخط أو القطعة المستقيمة p من النقطتين r1 و r2 المُعطيتين في الإحداثيات المتجانسة مباشرةً باستخدام الضرب الاتجاهي .
- p = r 1 × r 2 = ( x 1 , y 1 , w 1 ) × ( x 2 , y 2 , w 2 )
أو كما
- p = r 1 × r 2 = ( x 1 , y 1 , 1) × ( x 2 , y 2 , 1).
انظر أيضاً
مراجع
- ↑ رينكا، آر جيه (19-10-2014). "قص الأسطر" (ملف PDF) . قسم علوم وهندسة الحاسوب، جامعة شمال تكساس . تاريخ الاسترجاع: 12-01-2016 .
- ↑ سايروس، م.، بيك، ج.: القص ثنائي وثلاثي الأبعاد المعمم ، الحواسيب والرسومات، المجلد 3، العدد 1، الصفحات 23-28، 1978.
- ↑ سوبكو، مارك س.؛ بوسبيسيل، بول؛ يانغ، يي-هونغ (1987). "خوارزمية سريعة لقص الخطوط ثنائية الأبعاد عبر ترميز الخطوط" . الحوسبة والرسومات . 11 (4): 459-467 .
- ↑ سكالا، ف. : خوارزمية قص الخطوط O (lg N ) في E2، الحوسبة والرسومات، بيرغامون برس، المجلد 18، العدد 4، 1994.
- ↑ سكالا، ف.: نهج جديد لقص الخطوط وقطع الخطوط في الإحداثيات المتجانسة ، الحاسوب المرئي، ISSN 0178-2789، المجلد 21، العدد 11، الصفحات 905-914، سبرينغر فيرلاغ، 2005.
- القص (رسومات الحاسوب)