> ## Content Index > Fetch the complete content index at: https://informatic-ar.com/llms.txt > Use this file to discover other available public pages before exploring further. # خوارزمية QuickHull - URL: https://informatic-ar.com/quickhull/ - Published: 2013-09-30T19:31:13.000Z - Updated: 2026-10-03T22:32:07.000Z - Author: أحمد عصام - Tags: خوارزميات, quickhull, convexhull, algorithm, #wordpress-archive, #Import 2026-10-03 20:48 سنتحدث اليوم عن مشكلة معروفة في مجال ال [Computational Geometry](https://informatic-ar.com/http://en.wikipedia.org/wiki/Computational%5Fgeometry) وهي تحديد أصغر مضلع يحوي مجموعة من النقاط! وقبل أن ندخل في حل المشكلة ، دعونا نتعرف على بعض المصطلحات . **Points** وهي نقاط في المستوى Plane ، مثلا النقاط *p(2,2) ,q(3,2),...etc* في المستوى *R x R* ويمكن أن تكون في المستوى الثالث . **Polygon** مضلع ، وقد يكون مثلث،مربع،دائرة،....الخ. **Convex** وهو مضلع يحقق الخاصية التالية : لكل نقطتين فيه *p,q* فان الخط الواصل بينها يقع داخل هذا الشكل . [![convex_polygon](https://informatic-ar.com/wp-content/uploads/2013/09/convex_polygon.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convex%5Fpolygon.png) **Concave** هو المضلع الذي لا يحقق الخاصية أعلاه. [![concave_polygon](https://informatic-ar.com/wp-content/uploads/2013/09/concave_polygon.png)](https://informatic-ar.com/wp-content/uploads/2013/09/concave%5Fpolygon.png) **Convex Hull** هو أصغر مضلع Convex Polygon يحوي مجموعة من النقاط ، وهذا هو ما نريد ان نقوم بانشائه . [![convexhull](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull.png) المضلع -باللون البرتقالي- هو ال convex hull . **خوارزمية QuickHull لايجاد الى convex-Hull:** يوجد العديد من الخوارزميات لايجاد هذا المضلع ، وسنذكر هنا خوارزمية QuickHull وهي خوارزمية تعمل بمبدأ [Divide and Conquer](https://informatic-ar.com/http://en.wikipedia.org/wiki/Divide%5Fand%5Fconquer%5Falgorithm) حيث يتم تقسيم المشكلة الى اجزاء صغيرة -وهكذا يتم التقسيم الى ان نصل الى أصغر جزء ممكن- ثم تحل المشكلة وتجمع الحلول مع بعضها . وتطبيقها سيكون بالاستدعاء الذاتي ، وهو يعطي كود جميل ومقروء، لذلك يفضل الكثير هذه الخوارزمية على الرغم من انه توجد بعض الخورازميات الاخرى ذات أداء أفضل لكن بكود أكثر تعقيدا ! وسأشرح الخوارزمية مع مثال نظري لكي تتضح أكثر. نفرض ان لدينا مجموعة نقاط على المستوى : [![convexhull1](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull1.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull1.png) الخطوة الاولى : ايجاد أصغر نقطة وأكبر نقطة على المحور الافقي - محور X [![convexhull2](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull2.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull2.png) ومن ثم نوصل هاتين النقطتين معا . هاتين النقطتين ستكون داخل المضلع النهائي Proved هذا الخط سيقسم النقاط الى مجموعتين - فوق الخط وتحت الخط - لكن رياضيا نقول - يسار الخط ويمين الخط- [![convexhull3](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull3.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull3.png) ونقول أن النقطة 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](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull4.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull4.png) ولايجاد أبعد نقطة من خط ، توجد العديد من الطرق الرياضية ، ساستخدم المعادلة التالية : \- سأحدث هذه الفقرة لاحقا لكي أضيف رموز LaTeX للمعادلات -. وكما تلاحظ من الشكل السابق ، أبعد نقطة قد شكلت لنا مثلث. الخطوة الثالثة : استبعاد النقاط الموجودة داخل المثلث . لانها بالطبع ليست نقاط عظمى Extreme Points [![convexhull5](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull5.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull5.png) الخطوة الرابعة : كرر الخطوات 2 و 3 ! [![convexhull6](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull6.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull6.png) لان الخوارزمية تعمل بالطريقة التكرارية recursively فكل المطلوب الان هو أن نمسك الضلع (اليمين واليسار) في المثلث كل على حدة ، ثم نقوم بايجاد ابعد نقطة عن الخط وبعدها سيظهر لنا مثلث ، وسنتجاهل النقاط بداخله ، .... وهكذا . **متى سنتوقف ؟** بالتأكيد عندما لا نجد أي نقطة فوق الخط uv مثلا. الخطوة الخامسة : كرر الخطوات على الجزء الاخر (الذي يقع يمين الخط) ، وهكذا تكون قد انتهت الخوارزمية [![convexhull7](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull7.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull7.png) **تنفيذ الخوارزمية** Implementation of QuickHull in C++/Qt ```c #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 هي عبارة عن مصفوفة من النقاط . دالة ايجاد أصغر نقطة : ```c /* 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; } ``` ايجاد أكبر نقطة : ```c /* 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; } ``` معرفة مكان النقطة بالنسبة لخط ما ، يمين الخط ام يساره؟ ```c /* 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; } ``` حساب أبعد نقطة من خط ما ، لاحظ ان القانون ليس دقيقا فهو يتجاهل الكثير من الاشياء التي لن تأثر على المسافة ```c /* 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; } ``` **بداية الخوارزمية** ```c /* 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; } ``` **الدالة التكرارية - تقسيم المشكلة وجمع الحلول هنا-** ```c 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. [![convexhullapp](https://informatic-ar.com/wp-content/uploads/2013/09/convexhullapp-300x195.png)](https://informatic-ar.com/wp-content/uploads/2013/09/convexhullapp.png) تطبيقات على الخوارزمية : 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](https://informatic-ar.com/wp-content/uploads/2013/09/convexhull.tar.gz)