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


कठिनाई तह मध्यम
बारम्बार सोधिन्छ ज्यामितीय मोर्गन स्टेनले Samsung

समस्यामा "उत्तल हल एल्गोरिथ्म" मा हामीले केहि पोइन्टको सेट दिएका छौं। सबैभन्दा सानो बहुभुज जुन ती पोइन्टहरूसँग गठन गर्न सकिन्छ जुन यस भित्र अन्य सबै पोइन्टहरू समावेश गर्दछ यसको उत्तल हल भनिन्छ।

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

यो प्रयोग गरेर प्राप्त गर्न सकिन्छ Jarvis एल्गोरिथ्म.

अल्गोरिदम

  1. ० सम्म बायाँ पोइन्ट सुरू गर्नुहोस्।
  2. घोषणा गर्नुहोस् सदिश पोइन्ट प्रकारको नाम दिइएको
  3. अघिल्लो बायाँ पोइन्ट फेला नहुँदासम्म पोइन्ट्स एब्जे एरे ट्रान्स गर्नुहोस्
  4. परिणाम भेक्टरमा त्यो पोइन्ट थप्नुहोस्
  5. अर्को बिन्दु खोज्नुहोस् "क्यू" जस्तो कि यो सबै अन्य पोइन्टहरू बन्द सबैभन्दा उल्टो दिशा बिन्दु हो
  6. पोइन्टमा पोइन्ट गर्नुहोस् "क्यू" अर्को पुनरावृत्ति को लागी।
  7. थप्दा जारी राख्नुहोस् "P" बाँया भन्दा बराबर छैन।

विवरण

त्यसैले उत्तल हललाई सुल्झाउने हाम्रो मुख्य विचार अभिमुखिकरण प्रयोग गर्नु हो। हामी फेला पार्दै छौं वा बायाँ वा सायद सबै भन्दा कम एक्स समन्वयको साथ सुरू गर्न। र हामी यो लिन सक्दछौं जब सम्म हाम्रो सबै पोइन्टहरू फेला पर्दैन जुन केही पोइन्ट्सको सेट स accum्कलन गर्न सक्छ।

हामी प्रयोगकर्ता वर्ग पोइन्टको वस्तु वस्तु एरे बिन्दु पास गर्न जाँदैछौं जुन हामीले कोडको शुरूमा यसलाई परिभाषित गरिसकेका छौं। पूर्णांकको बिन्दु र लम्बाइका हाम्रो आर्गुमेन्टहरू उत्तल हलमा पास हुन्छन् समारोहजहाँ हामीले भेक्टर नामको नतिजा घोषणा गर्ने छौं जसमा हामी आफ्नो आउटपुट भण्डार गर्छौं।

अब बायाँको बिन्दु ० लाई आरम्भ गर्नुहोस्। हामी यसलाई ० बाट सुरू गर्दैछौं, यदि हामीले पोइन्ट पाउछौं जुन न्यूनतम x समन्वय वा बायाँ पोइन्टमा हामीले त्यसलाई परिवर्तन गर्ने छौं।

अब सबै बिन्दुहरू पार गर्नुहोस् र सबैभन्दा कम एक पत्ता लगाउनुहोस्। बायाँको स्थानको स्टोर गर्नुहोस् "P" र एउटा बिन्दु घोषणा गर्नुहोस्

अब, एक do-while लूप सुरु गर्नुहोस् जुन हामीले गर्न सक्ने पहिलो कुरा आउटपुटको रूपमा पहिलो पोइन्ट थप गर्दैछ।

अब हामीले अरू सबै पोइन्टहरूमा सबैभन्दा काउन्टरवर्क पोइन्ट खोज्नुपर्दछ, यसको लागि हामी अभिमुखिकरण प्रयोग गर्न गइरहेका छौं। यसका लागि हामीले छुट्टै प्रकार्य गरेका छौं, जसले जाँच गर्दछ ट्रिपल्ट्सको अभिमुखिकरण २ छ कि छैन यदि यसलाई २ फेला परेन भने पोइन्टको मान अपडेट गर्नुहोस्। "क्यू".

यो जारी राख्नुपर्दछ "P" बाँया भन्दा बराबर छैन।

उदाहरणका

दिइएको पोइन्टहरू हुन्:

{{०,}}, {२, २}, {१, १}, {२, १}, {,, ०}, {०, ०}, {,,}}};

बायाँको = ०;

सबै पोइन्ट्स ट्र्यावर्सिंग गरेपछि, हाम्रो पहिलो न्यूनतम x को-ओर्डिनेन्ट हुनेछ (०,0,3) यो परिणामको रूपमा भण्डार हुनेछ।
अब यसले कुन जाँच्दैछ x, y जोडीसँग सबैभन्दा घडीको उल्टो दिशा हुन्छ किनकि यसले २ को रूपमा अभिमुखीकरण दिन्छ र बिन्दुको मान अपडेट गर्दछ "क्यू".
जोडी (०,०) को रूपमा फेला पार्न।
अब, पोइन्टको मान प्रतिलिपि गर्नुहोस् "क्यू" पछिल्लो बिन्दुको रूपमा p मा फेरि सबैभन्दा काउन्टरवाट विन्दु पत्ता लगाउँनुहोस्।
जबसम्म p को मान बायाँको बराबर हुँदैन हामी यो लूप प्रयोग गर्ने छौं।
हाम्रो आउटपुट: (०,,), (०,०), (0,3,०), (0,0)

कार्यान्वयन

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 इनपुट पोइन्टहरूको संख्या हो र m आउटपुट पोइन्टहरूको संख्या हो।

ठाउँ जटिलता

ऊ) जहाँ n इनपुट पोइन्टको संख्या हो। यहाँ हामी अर्को मानको आकार N को एरे प्रयोग गर्छौं।

संदर्भ