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


مستوى الصعوبة متوسط
كثيرا ما يطلب في هندسي مورجان ستانلي سامسونج

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

خوارزمية محدبة هالدبوس

يمكن تحقيق ذلك باستخدام خوارزمية جارفيس.

خوارزمية  

  1. قم بتهيئة نقطة أقصى اليسار إلى 0.
  2. تعلن أ ناقلات نتيجة مسماة من نوع النقطة
  3. اجتياز مصفوفة كائن النقاط حتى يتم العثور على النقطة اليسرى الأولى
  4. أضف هذه النقطة إلى متجه النتيجة
  5. ابحث عن النقطة التالية "Q" بحيث تكون النقطة الأكثر عكس اتجاه عقارب الساعة من جميع النقاط الأخرى
  6. اضبط p للنقطة "Q" للتكرار التالي.
  7. استمر في الجمع أثناء "P" لا يساوي أقصى اليسار.

الوصف  

لذا فإن فكرتنا الرئيسية لحل الهيكل المحدب هي استخدام التوجيه. سنجد ونبدأ بإحداثي X الموجود في أقصى اليسار أو ربما أدنى إحداثي X. ويمكننا أن نأخذها حتى نحصل على جميع النقاط التي يمكن أن تتراكم فيها مجموعة من النقاط.

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

انظر أيضا
عد الخطوات الدنيا للحصول على الصفيف المطلوب المحدد

الآن قم بتهيئة النقطة الموجودة في أقصى اليسار إلى 0. سنبدأ من 0 ، إذا حصلنا على النقطة التي بها أدنى إحداثيات x أو النقطة الموجودة في أقصى اليسار ، فسنقوم بتغييرها.

الآن اجتز جميع النقاط واكتشف أدنى نقطة. تخزين موقف أقصى اليسار ل "P" وتعلن نقطة

الآن ، ابدأ حلقة do-while حيث أول شيء سنفعله هو جمع النقطة الأولى كناتج.

الآن علينا إيجاد النقطة الأكثر عكس اتجاه عقارب الساعة لجميع النقاط الأخرى ، لهذا ، سنستخدم التوجيه. لقد أنشأنا وظيفة منفصلة لهذا ، والتي تتحقق مما إذا كان اتجاه ثلاثة توائم هو 2 أم لا إذا وجد أنه 2 ، ثم قم بتحديث قيمة النقطة "Q".

يجب أن يستمر هذا حتى "P" لا يساوي أقصى اليسار.

مثال

النقاط المعطاة هي:

{{0 ، 3} ، {2 ، 2} ، {1 ، 1} ، {2 ، 1} ، {3 ، 0} ، {0 ، 0} ، {3 ، 3}} ؛

أقصى اليسار = 0 ؛

بعد اجتياز جميع النقاط ، سيكون أول تنسيق x لدينا هو (0,3،XNUMX) سيتم تخزينه كنتيجة لذلك.
الآن سوف تتحقق من أي x، y الزوج لديه معظم عكس اتجاه عقارب الساعة لأنه سيعطي الاتجاه كـ 2 ويحدث قيمة النقطة "Q".
يمكن العثور على الزوج كـ (0,0،XNUMX).
الآن ، انسخ قيمة النقطة "Q" إلى p كنقطة تالية لمعرفة النقطة الأكثر عكس اتجاه عقارب الساعة مرة أخرى.
حتى لا تكون قيمة p مساوية لأقصى اليسار ، سنستخدم هذه الحلقة.
سيكون ناتجنا: (0,3،0,0) ، (3,0،3,3) ، (XNUMX،XNUMX) ، (XNUMX،XNUMX)

تطبيق  

برنامج C ++ لخوارزمية محدب هال

#include <iostream>
using namespace std;
#define INF 10000

struct Point
{
        int x;
        int y;
};

int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);

    if (val == 0)
        return 0;
    return (val > 0) ? 1 : 2;
}

void convexHull(Point points[], int n)
{
    if (n < 3)
        return;
    int next[n];

    for (int i = 0; i < n; i++)
        next[i] = -1;

    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;

    int p = l, q;
    do
    {
        q = (p + 1) % n;
        for (int i = 0; i < n; i++)
            if (orientation(points[p], points[i], points[q]) == 2)
                q = i;

        next[p] = q;
        p = q;
    }
    while (p != l);

    for (int i = 0; i < n; i++)
    {
        if (next[i] != -1)
            cout << "(" << points[i].x << ", " << points[i].y << ")\n";
    }
}

int main()
{
    Point points[] = { { 0, 3 }, { 2, 2 }, { 1, 1 }, { 2, 1 }, { 3, 0 },
            { 0, 0 }, { 3, 3 } };
    cout << "The points in the convex hull are: ";
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}
The points in the convex hull are: (0, 3)
(3, 0)
(0, 0)
(3, 3)

برنامج جافا لخوارزمية محدب هال

import java.util.*;
class Point {

  int x, y;

  Point(int x, int y) {
    this.x = x;
    this.y = y;
  }
}

class ConvexHull{

  public static int OrientationMatch(Point check1, Point check2, Point check3) {

    int val = (check2.y - check1.y) * (check3.x - check2.x) - (check2.x - check1.x) * (check3.y - check2.y);

    if (val == 0)
      return 0;

    return (val > 0) ? 1 : 2;
  }

  public static void convex_hull(Point points[], int lengths) {

    if (lengths<3) return;

    Vector<Point> result = new Vector<Point> ();

    int leftmost = 0;

    for (int i = 1; i<lengths; i++)
      if (points[i].x<points[leftmost].x)
        leftmost = i;

    int p = leftmost, pointq;

    do {

      result.add(points[p]);

      pointq = (p + 1) % lengths;

      for (int i = 0; i<lengths; i++) {
        if (OrientationMatch(points[p], points[i], points[pointq]) == 2) {
          pointq = i;
        }
      }
      p = pointq;
    }

    while (p != leftmost);

    System.out.print("The points in the convex hull are: ");
    for (Point temp: result)
      System.out.println("(" + temp.x + ", " + temp.y + ")");

  }

  public static void main(String[] args) {

    Point points[] = new Point[7];
    points[0] = new Point(0, 3);
    points[1] = new Point(2, 3);
    points[2] = new Point(1, 1);
    points[3] = new Point(2, 1);
    points[4] = new Point(3, 0);
    points[5] = new Point(0, 0);
    points[6] = new Point(3, 3);

    int lengths = points.length;
    convex_hull(points, lengths);
  }
}
The points in the convex hull are: (0, 3)
(0, 0)
(3, 0)
(3, 3)

تحليل التعقيد لخوارزمية محدب هال  

تعقيد الوقت

يا (م * ن) حيث n هو عدد نقاط الإدخال و m هو عدد نقاط الإخراج.

انظر أيضا
تقييم التعبير

تعقيد الفضاء

O (ن) حيث n هو عدد نقاط الإدخال. هنا نستخدم مصفوفة بالحجم N لإيجاد القيمة التالية.

الرقم المرجعي