उत्तल हल एल्गोरिथम


कठिनाई स्तर मध्यम
में अक्सर पूछा ज्यामितीय मॉर्गन स्टेनली सैमसंग

समस्या में "उत्तल हल एल्गोरिथम" हमने कुछ बिंदुओं का एक सेट दिया है। सबसे छोटे बहुभुज जो उन बिंदुओं के साथ बन सकते हैं, जिनके अंदर अन्य सभी बिंदु होते हैं, इसे इसका उत्तल हल कहा जाएगा।

उत्तल हल एल्गोरिथम

इसका उपयोग करके प्राप्त किया जा सकता है जार्विस एल्गोरिथम.

कलन विधि

  1. एक बायाँ बिंदु को प्रारंभ में 0 करें।
  2. डिक्लेयर ए वेक्टर बिंदु प्रकार का नाम परिणाम
  3. बिंदु ऑब्जेक्ट सरणी को तब तक पीछे छोड़ें जब तक कि सबसे बाईं ओर बिंदु न मिल जाए
  4. परिणाम वेक्टर में उस बिंदु को जोड़ें
  5. अगले बिंदु का पता लगाएं 'क्यू' ऐसा है कि यह अन्य सभी बिंदुओं से सबसे अधिक वामावर्त बिंदु है
  6. इंगित करने के लिए p सेट करें 'क्यू' अगले पुनरावृत्ति के लिए।
  7. जबकि जोड़ते रहो 'पी' सबसे बाईं ओर के बराबर नहीं है।

विवरण

तो उत्तल हल को हल करने के लिए हमारा मुख्य विचार अभिविन्यास का उपयोग करना है। हम सबसे कम या शायद सबसे कम X समन्वय के साथ खोजने और शुरू करने जा रहे हैं। और हम इसे तब तक ले सकते हैं जब तक कि हमारे सभी बिंदु नहीं मिल जाते हैं जिसमें कुछ बिंदुओं का एक सेट जमा हो सकता है।

हम उपयोगकर्ता वर्ग प्वाइंट के ऑब्जेक्ट एरे पॉइंट को पास करने जा रहे हैं, जिसे हम पहले से ही कोड के शुरू में परिभाषित करते हैं। अंक और पूर्णांक की लंबाई के हमारे तर्क उत्तल पतवार में पारित हो जाते हैं समारोह, जहां हम वेक्टर नाम का परिणाम घोषित करेंगे, जिसमें हम अपने आउटपुट को स्टोर करने जा रहे हैं।

अब बायीं ओर के बिंदु को इनिशियलाइज़ करें। 0. हम इसे 0 से शुरू करने जा रहे हैं, अगर हमें वह पॉइंट मिलता है जिसमें सबसे कम x कोऑर्डिनेट किया गया है या सबसे बायीं तरफ हम इसे बदलने जा रहे हैं।

अब सभी बिंदुओं को पार करें और सबसे कम का पता लगाएं। सबसे बाईं ओर की स्थिति संग्रहीत करें 'पी' और एक बिंदु घोषित करें

अब, एक डू-टाइम लूप शुरू करें जिसमें पहली चीज जो हम करते हैं वह आउटपुट के रूप में पहला बिंदु जोड़ रहा है।

अब हमें अन्य सभी बिंदुओं के लिए सबसे वामावर्त बिंदु खोजना होगा, इसके लिए हम अभिविन्यास का उपयोग करने जा रहे हैं। हमने इसके लिए एक अलग कार्य किया, जो यह जांचता है कि क्या त्रिगुणों का अभिविन्यास 2 है या नहीं यदि यह 2 पाया जाता है तो बिंदु के मान को अपडेट करें 'क्यू'.

इसे तब तक जारी रखा जाना चाहिए जब तक कि 'पी' सबसे बाईं ओर के बराबर नहीं है।

उदाहरण

दिए गए बिंदु हैं:

{{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};

वामतम = 0;

सभी बिंदुओं को ट्रेस करने के बाद, हमारा पहला सबसे कम x समन्वय होगा (0,3) यह एक परिणाम के रूप में संग्रहीत करेगा।
अब यह कौन सा चेक करने जा रहा है एक्स, वाई जोड़ी में सबसे अधिक वामावर्त है क्योंकि यह 2 के रूप में अभिविन्यास देगा और बिंदु के मूल्य को अपडेट करेगा 'क्यू'.
जोड़ी के रूप में पाई जाने वाली (0,0)।
अब, बिंदु के मूल्य की प्रतिलिपि बनाएँ 'क्यू' पी में एक अगले बिंदु के रूप में फिर से सबसे वामावर्त बिंदु का पता लगाने के लिए।
जब तक p का मान बायीं ओर के बराबर नहीं होता है तब तक हम इस लूप का उपयोग करने वाले हैं।
हमारा आउटपुट होगा: (0,3), (0,0), (3,0), (3,3)

कार्यान्वयन

उत्तल हल एल्गोरिथम के लिए 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 आउटपुट बिंदुओं की संख्या है।

अंतरिक्ष जटिलता

पर) जहाँ n इनपुट बिंदुओं की संख्या है। यहां हम अगले मान को खोजने के लिए आकार N की एक सरणी का उपयोग करते हैं।

संदर्भ