Home خوارزميات خوارزمية QuickHull
خوارزمية QuickHull

خوارزمية QuickHull

307
2

سنتحدث اليوم عن مشكلة معروفة في مجال ال Computational Geometry وهي تحديد أصغر مضلع يحوي مجموعة من النقاط!
وقبل أن ندخل في حل المشكلة ، دعونا نتعرف على بعض المصطلحات .

Points وهي نقاط في المستوى Plane ، مثلا النقاط p(2,2) ,q(3,2),…etc في المستوى R x R ويمكن أن تكون في المستوى الثالث .

Polygon مضلع ، وقد يكون مثلث،مربع،دائرة،….الخ.

Convex وهو مضلع يحقق الخاصية التالية :

لكل نقطتين فيه p,q فان الخط الواصل بينها يقع داخل هذا الشكل .

convex_polygon

Concave هو المضلع الذي لا يحقق الخاصية أعلاه.

concave_polygon

Convex Hull هو أصغر مضلع Convex Polygon يحوي مجموعة من النقاط ، وهذا هو ما نريد ان نقوم بانشائه .

convexhull

المضلع -باللون البرتقالي- هو ال convex hull .

خوارزمية QuickHull لايجاد الى convex-Hull:

يوجد العديد من الخوارزميات لايجاد هذا المضلع ، وسنذكر هنا خوارزمية QuickHull وهي خوارزمية تعمل بمبدأ Divide and Conquer حيث يتم تقسيم المشكلة الى اجزاء صغيرة -وهكذا يتم التقسيم الى ان نصل الى أصغر جزء ممكن- ثم تحل المشكلة وتجمع الحلول مع بعضها .

وتطبيقها سيكون بالاستدعاء الذاتي ، وهو يعطي كود جميل ومقروء،  لذلك يفضل الكثير هذه الخوارزمية على الرغم من انه توجد بعض الخورازميات الاخرى ذات أداء أفضل لكن بكود أكثر تعقيدا !

وسأشرح الخوارزمية مع مثال نظري لكي تتضح أكثر.

نفرض ان لدينا مجموعة نقاط على المستوى :

 

convexhull1

الخطوة الاولى : ايجاد أصغر نقطة وأكبر نقطة على المحور الافقي – محور X

 

convexhull2

ومن ثم نوصل هاتين النقطتين معا .

هاتين النقطتين ستكون داخل المضلع النهائي Proved

هذا الخط سيقسم النقاط الى مجموعتين – فوق الخط وتحت الخط – لكن رياضيا نقول – يسار الخط ويمين الخط-
convexhull3

ونقول أن النقطة p تقع يسار الخط الواصل بين النقطتين u,v اذا كان حاصل الضرب الاتجاهي Cross Product للخط (المتجه) up و uv أكبر من الصفر ، اما اذا كان أقل من الصفر فهذا يعني أن النقطة p تقع يمين الخط (المتجه) uv.

ملاحظة : هناك عدة طرق اخرى لمعرفة مكان النقطة ، وسأستخدم هنا قانون الضرب الاتجاهي.

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

– سأحدث هذه الفقرة لاحقا لكي اضيف بعض الصور التوضيحية وكذلك رموز LaTeX للمعادلات -.

انظر في هذا ال Applet للمزيد :
http://physics.syr.edu/courses/java-suite/crosspro.html

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

الخطوة الثانية : ايجاد أبعد نقطة من الخط uv .
حيث أن أبعد نقطة من الخط ستكون داخل المضلع النهائي.
convexhull4

ولايجاد أبعد نقطة من خط ، توجد العديد من الطرق الرياضية ، ساستخدم المعادلة التالية :

– سأحدث هذه الفقرة لاحقا لكي أضيف رموز LaTeX للمعادلات -.

وكما تلاحظ من الشكل السابق ، أبعد نقطة قد شكلت لنا مثلث.

الخطوة الثالثة : استبعاد النقاط الموجودة داخل المثلث .
لانها بالطبع ليست نقاط عظمى Extreme Points
convexhull5

الخطوة الرابعة : كرر الخطوات 2 و 3 !
convexhull6

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

متى سنتوقف ؟

بالتأكيد عندما لا نجد أي نقطة فوق الخط uv مثلا.

الخطوة الخامسة : كرر الخطوات على الجزء الاخر (الذي يقع يمين الخط) ، وهكذا تكون قد انتهت الخوارزمية
convexhull7

 

تنفيذ الخوارزمية
Implementation of QuickHull in C++/Qt

الفئة QPolygon هي عبارة عن مصفوفة من النقاط .

دالة ايجاد أصغر نقطة :

ايجاد أكبر نقطة :

معرفة مكان النقطة بالنسبة لخط ما ، يمين الخط ام يساره؟

حساب أبعد نقطة من خط ما ، لاحظ ان القانون ليس دقيقا فهو يتجاهل الكثير من الاشياء التي لن تأثر على المسافة

بداية الخوارزمية

الدالة التكرارية – تقسيم المشكلة وجمع الحلول هنا-

وفي الملف المرفق ستجد مثال بسيط Quick & Dirty، وكل ما عليك ان تحدد مجموعة من النقاط ثم تضغط على زر start وسيتم تحديد ال convex hull.
convexhullapp

تطبيقات على الخوارزمية :
Computer Visualization, Ray Tracing, Video Games, Replacement of Bounding Boxes
Path Finding – Embedded AI of Mars mission Rovers
Geographical Information Systems (GIS) – Computing Accessibility Maps
Visual Pattern Matching – Detecting Car License Plates
Verification Methods – Bounding of Number Decision Diagrams
Geometry – Diameter Computation

http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_ss_07w/Webprojects/Chen_hull/applications.htm

 

روابط :
http://en.wikipedia.org/wiki/Convex_hull
http://westhoffswelt.de/blog/0040_quickhull_introduction_and_php_implementation.html
http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html
http://www.ahristov.com/tutorial/geometry-games/convex-hull.html

مرفق:
convexhull.tar

(307)

أحمد عصام مهندس برمجيات مهتم بعلوم الحاسب ، وكل ما يتعلق ب Qt و KDE.

Comment(2)

  1. أكثر من رائع فوجود محتوى عربي بهده القيمة شيئ يثلج الصدر زيادةً على طريقة شرح المتميزة شكرا لكم

  2. شي جيمل ان نجد محتوى عربي يقوم بكتابة مقالات مميزة بهذا شكل والله .
    جزاكم الله خيرا

LEAVE YOUR COMMENT

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

مشاركة