خوارزمية QuickHull

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ونقول أن النقطة 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 .
حيث أن أبعد نقطة من الخط ستكون داخل المضلع النهائي.

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

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

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

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

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

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

متى سنتوقف ؟

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

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

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

#ifndef QUICKHULL_H
#define QUICKHULL_H

#include 

class QLine;

class QuickHull
{
    public:
   QuickHull(const QPolygon& polygon);
      
   static QPoint minPoint(const QPolygon& polygon);
   static QPoint maxPoint(const QPolygon& polygon);
   
   const QPolygon& convexHull();

    private:
   void findHull(QPoint p1,QPoint p2,QPolygon set);
      
   static bool isLeft(const QLine& segment,const QPoint& point);
   static int distance(const QPoint& p1,const QPoint& p2,const QPoint& p3);
   static QPoint maxPointDistance(const QPoint& A,const QPoint& B,const QPolygon& set);
   
   QPolygon m_points;
   QPolygon m_convexhull;
};

#endif  // QUICKHULL_H

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

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

/* Find the minimum point in the horizontal axis */
QPoint QuickHull::minPoint(const QPolygon& polygon)
{
    QPoint min = polygon.at(0);
    
    foreach (QPoint p,polygon) {
   if ( min.x() < p.x() )
       min = p;
    }
    
    return min;
}

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

/* Find the maximum point in the horizontal axis */
QPoint QuickHull::maxPoint(const QPolygon& polygon)
{
    QPoint max = polygon.at(0);
    
    foreach (QPoint p,polygon) {
   if ( max.x() > p.x() )
       max = p;
    }
    
    return max; 
}

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

/* Check if point P is left to the line segment AB or not.
** This is done by take the Cross product AB x AP.
** if the result is positive (angle are counter-clockwise) it return true, else return false. */
bool QuickHull::isLeft(const QLine& line,const QPoint& p)
{
    int cp = (line.x2()-line.x1()) * (p.y()-line.y1()) - (line.y2()-line.y1()) * (p.x()-line.x1());
    
    return (cp>0)?true:false;
}

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

/* Compute the (Pseudo)distance between the line segment (p1,p2) and the point p3. */
int QuickHull::distance(const QPoint& p1,const QPoint& p2,const QPoint& p3)
{
    int ux = p2.x() - p1.x();
    int uy = p2.y() - p1.y();
    
    int s = ux*(p1.y()-p3.y()) - uy*(p1.x()-p3.x());
    
    if (s<0)
   s = -s;
    
    return s;
}

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

/* Start of QuickHull Algorithm */
const QPolygon& QuickHull::convexHull()
{
    if ( m_points.size() < 3 )
   return m_points;
    
    // Find the min/max point in the convex polygon
    QPoint A = minPoint(m_points);
    QPoint B = maxPoint(m_points);
    
    QLine segment(A,B);

    // Add min/max point to the m_convexhull
    m_convexhull << A << B;
    
    // Remove min/max from the set of all points m_points
    m_points.remove(m_points.indexOf(A));
    m_points.remove(m_points.indexOf(B));
    
    // Find the left and right points lies with the line segment (A,B).
    // This line divide the hull into upper and lower hull.
    QPolygon upperHull;
    QPolygon lowerHull;
   
   
    foreach (QPoint p,m_points) {
   if (isLeft(segment,p))
       upperHull << p;
   else
       lowerHull << p;
    }
   
    findHull(A,B,upperHull);
    findHull(B,A,lowerHull);
   
    return m_convexhull;
}

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

void QuickHull::findHull(QPoint A,QPoint B,QPolygon set)
{
    // Place to put the new extreme point
    int index = m_convexhull.indexOf(B);
    
    if ( set.size() == 0 )
   return;
    
    if ( set.size() == 1 ) {
   QPoint p = set.at(0);
   set.remove(set.indexOf(p));
   m_convexhull.insert(index,p);
   return;
    }
    
    // Find point that maximize the area of the triangle.
    QPoint C = maxPointDistance(A,B,set);
    
    // Add this point to the convex hull(proved)
    set.remove(set.indexOf(C));
    m_convexhull.insert(index,C);
    
    // Add points left of AC to leftAC set and add points left of CB to leftCB
    // This will automatically discard all points inside this triangle ACB.
    
    QPolygon leftAC;
    QPolygon leftCB;
    
    foreach (QPoint q,set) {
   if (isLeft(QLine(A,C),q))
       leftAC << q;
    }

    foreach (QPoint r,set) {
   if (isLeft(QLine(C,B),r))
       leftCB << r;
    }
    
    findHull(A,C,leftAC);
    findHull(C,B,leftCB);
}

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

تطبيقات على الخوارزمية :
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