محدب ہل الگوریتم


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے جیومیٹری مارگن سٹینلی سیمسنگ

مسئلہ "محدور ہل الگوریتم" میں ہم نے کچھ نکات کا ایک سیٹ دیا ہے۔ سب سے چھوٹی کثیرالاضلاع جو ان نکات کے ساتھ تشکیل پاسکتی ہے جس میں اس کے اندر دیگر تمام نکات ہوتے ہیں اس کو محدول ہل کہا جائے گا۔

محدب ہل الگوریتم

یہ استعمال کرکے حاصل کیا جاسکتا ہے جاریوس الگورتھم.

الگورتھم

  1. بائیں بازو کے نقطہ 0 کو شروع کریں۔
  2. اعلان a ویکٹر نقطہ قسم کا نامزد کردہ نتیجہ
  3. جب تک کہ سب سے اہم بائیں نقطہ نہیں مل جاتا پوائنٹس آبجیکٹ صف کو عبور کریں
  4. اس نقطہ کو نتیجہ کے ویکٹر میں شامل کریں
  5. اگلا نقطہ تلاش کریں "ق" اس طرح کہ یہ دوسرے تمام مقامات سے سب سے زیادہ مخالف گھڑی کی طرف ہے
  6. p کی طرف اشارہ کریں "ق" اگلی تکرار کے ل.
  7. شامل کرتے رہیں "P" بائیں بازو کے برابر نہیں ہے۔

تفصیل

لہذا محرک کا حل حل کرنے کا ہمارا بنیادی خیال واقفیت کا استعمال ہے۔ ہم ڈھونڈنے والے اور شاید سب سے کم X کوآرڈینیٹ کے ساتھ تلاش کرنے اور شروع کرنے جارہے ہیں۔ اور ہم اسے اس وقت تک لے جاسکتے ہیں جب تک ہمارے تمام نکات نہیں مل پاتے جس میں کچھ نکات کا مجموعہ جمع ہوسکتا ہے۔

ہم صارف کلاس پوائنٹ کے آبجیکٹ صف نقطہ کو منتقل کرنے جارہے ہیں ، جسے ہم پہلے ہی کوڈ کے شروع میں ہی بیان کرتے ہیں۔ ہمارے پوائنٹس اور لمبائی کے دلائل محدب ہل میں گزر جاتے ہیں تقریب، جہاں ہم ویکٹر کے نام کے نتیجے کا اعلان کریں گے جس میں ہم اپنا آؤٹ پٹ اسٹور کرنے جارہے ہیں۔

اب بائیں بازو کے نقطہ کی شروعات 0. سے کریں۔ ہم اسے 0 سے شروع کرنے جارہے ہیں ، اگر ہمیں کوئی نکتہ مل جائے جس میں سب سے کم ایکس کوآرڈینیٹ یا بائیں بازو کا نقطہ ہے جو ہم اسے تبدیل کرنے جارہے ہیں۔

اب تمام نکات کو عبور کریں اور کم ترین نکات کا پتہ لگائیں۔ بائیں بازو کی پوزیشن کو اسٹور کریں "P" اور ایک نکتہ کا اعلان کریں

اب ، ایک ڈو وپ لوپ شروع کریں جس میں ہم سب سے پہلے کام کرنے والے آئوٹ کو بطور آؤٹ پٹ شامل کریں گے۔

اب ہمیں دوسرے تمام نکات کی طرف سب سے زیادہ گھڑسوار نقطہ تلاش کرنا ہے ، اس کے ل we ، ہم واقفیت استعمال کرنے جارہے ہیں۔ ہم نے اس کے لئے ایک علیحدہ فنکشن بنایا ، جو چیک کرتا ہے کہ آیا ٹرپلٹس کا رخ 2 ہے یا نہیں اگر یہ 2 پایا جاتا ہے تو پھر پوائنٹ کی قدر کو اپ ڈیٹ کریں۔ "ق".

جب تک یہ جاری رکھنا چاہئے "P" بائیں بازو کے برابر نہیں ہے۔

مثال کے طور پر

دیئے گئے نکات یہ ہیں:

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

بائیں ترین = 0؛

تمام نکات کو عبور کرنے کے بعد ، ہمارا پہلا نچلا ترین ہم آہنگی (0,3،XNUMX) ہوگا جس کے نتیجے میں وہ ذخیرہ کرے گا۔
اب یہ چیک کرنے جارہا ہے کہ کون سا x، y جوڑی کے سب سے زیادہ گھڑی مخالف سمت ہوتی ہے کیونکہ یہ 2 کی طرح واقفیت فراہم کرے گی اور نقطہ کی قدر کو اپ ڈیٹ کرے گی "ق".
جوڑی (0,0،XNUMX) کے بطور ملی۔
اب ، نقطہ کی قدر کاپی کریں "ق" اگلے نقطہ کے طور پر 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)

محدور ہل الگورتھم کے لئے پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (m * n) جہاں ن ان پٹ پوائنٹس کی تعداد ہے اور ایم آؤٹ پٹ پوائنٹس کی تعداد ہے۔

خلائی پیچیدگی

اے (ن) جہاں ن ان پٹ پوائنٹس کی تعداد ہے۔ یہاں ہم اگلی قیمت تلاش کرنے کے لئے سائز N کی ایک صف کا استعمال کرتے ہیں۔

حوالہ