উত্তল হাল আলগোরিদম


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় জ্যামিতিক মরগ্যান স্ট্যানলি স্যামসাং

"উত্তল হাল আলগোরিদম" সমস্যায় আমরা কিছু পয়েন্টের একটি সেট দিয়েছি। সেই ক্ষুদ্রতম বহুভুজ যা সেই বিন্দুগুলির সাথে গঠিত হতে পারে যা এর অভ্যন্তরে অন্যান্য সমস্ত পয়েন্ট থাকে তাকে তার উত্তল হাল বলা হবে।

উত্তল হাল আলগোরিদম

এটি ব্যবহার করে অর্জন করা যেতে পারে জার্ভিস অ্যালগরিদম.

অ্যালগরিদম

  1. বামদিকের বিন্দুটি 0 তে শুরু করুন।
  2. ঘোষণা করুন ক ভেক্টর পয়েন্ট ধরণের নামকরণ ফলাফল
  3. সর্বাধিক বাম পয়েন্ট না পাওয়া পর্যন্ত পয়েন্ট অবজেক্ট অ্যারেটিকে অতিক্রম করুন
  4. ফলাফল ভেক্টরে সেই বিন্দুটি যুক্ত করুন
  5. পরবর্তী পয়েন্টটি সন্ধান করুন "Q" এর যেমন এটি অন্য সমস্ত পয়েন্ট বন্ধ সবচেয়ে ঘড়ির কাঁটার দিক
  6. পয়েন্ট নির্দেশ করুন "Q" এর পরবর্তী পুনরাবৃত্তির জন্য।
  7. যোগ করার সময় আপ রাখুন "পি" বামতমের সমান নয়।

বিবরণ

সুতরাং উত্তল হলের সমাধানের জন্য আমাদের মূল ধারণাটি হ'ল অরিয়েন্টেশন ব্যবহার করা। আমরা সন্ধান করতে এবং বামে বা সম্ভবত সর্বনিম্ন এক্স স্থানাঙ্ক দিয়ে শুরু করতে যাচ্ছি। এবং আমরা আমাদের পয়েন্টগুলি খুঁজে পাওয়া পর্যন্ত এটি গ্রহণ করতে পারি যাতে কিছু পয়েন্টের একটি সেট জমে যায়।

আমরা ব্যবহারকারী শ্রেণীর পয়েন্টের অবজেক্ট অ্যারে পয়েন্টগুলি পাস করতে যাচ্ছি, যা আমরা ইতিমধ্যে কোডের শুরুতে এটি সংজ্ঞায়িত করেছি। পূর্ণসংখ্যার পয়েন্ট এবং দৈর্ঘ্যের আমাদের যুক্তিগুলি উত্তল হালতে উত্তীর্ণ হয় ক্রিয়া, যেখানে আমরা ভেক্টর নামের ফলাফল ঘোষণা করব যেখানে আমরা আমাদের আউটপুট সংরক্ষণ করব।

এখন বাম দিকের বিন্দুটি 0. তে সূচনা করুন আমরা 0 থেকে এটি শুরু করতে যাচ্ছি, যদি আমরা পয়েন্টটি পাই যা নিম্নতম x স্থানাঙ্ক বা বামতম পয়েন্ট আমরা এটি পরিবর্তন করতে চলেছি।

এখন সমস্ত পয়েন্ট অতিক্রম করুন এবং সর্বনিম্ন একটিটি সন্ধান করুন। বামতম অবস্থানে অবস্থান সংরক্ষণ করুন "পি" এবং একটি বিষয় ঘোষণা

এখন, একটি ডু-ওয়েল লুপটি শুরু করুন যেখানে আমরা প্রথমে যা করব তা আউটপুট হিসাবে প্রথম পয়েন্ট যুক্ত করবে।

এখন আমাদের অন্যান্য সমস্ত পয়েন্টের জন্য সবচেয়ে ঘড়ির কাঁটার দিকে পয়েন্টটি খুঁজে পেতে হবে, এর জন্য, আমরা অরিয়েন্টেশন ব্যবহার করতে যাচ্ছি। আমরা এটির জন্য একটি পৃথক ফাংশন করেছি, যা ট্রিপলগুলির অভিযোজন 2 হয় কিনা এটি পরীক্ষা করে যদি এটি 2 হিসাবে পাওয়া যায় তবে বিন্দুর মান আপডেট করুন "Q" এর.

এটি অবধি চালিয়ে যাওয়া উচিত "পি" বামতমের সমান নয়।

উদাহরণ

প্রদত্ত পয়েন্টগুলি হ'ল:

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

বামতম = 0;

সমস্ত পয়েন্ট ট্র্যাভার করার পরে, আমাদের প্রথম সর্বনিম্ন এক্স কো-অর্ডিনেট (0,3) এটি ফলাফল হিসাবে সংরক্ষণ করবে।
এখন এটি যা যাচাই করতে যাচ্ছে x, y জুটির বেশিরভাগ ঘড়ির কাঁটা রয়েছে কারণ এটি 2 হিসাবে ওরিয়েন্টেশন দেবে এবং পয়েন্টের মান আপডেট করবে "Q" এর.
(0,0) হিসাবে পাওয়া যায় এমন জুটি।
এখন, পয়েন্টের মানটি অনুলিপি করুন "Q" এর সর্বাধিক পাল্টা ঘড়ির কাঁটার পয়েন্টটি খুঁজে পাওয়ার জন্য পরবর্তী পয়েন্ট হিসাবে পি into
যতক্ষণ না প এর মান বামতমের সমান হয় আমরা এই লুপটি ব্যবহার করব।
আমাদের আউটপুটটি হবে: (0,3), (0,0), (3,0), (3,3)

বাস্তবায়ন

উত্তল হাল আলগোরিদমের জন্য সি ++ প্রোগ্রাম

#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)

উত্তল হাল আলগোরিদমের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এম * এন) যেখানে এন ইনপুট পয়েন্টের সংখ্যা এবং এম আউটপুট পয়েন্টগুলির সংখ্যা of

স্পেস জটিলতা ity

উপর) যেখানে এন ইনপুট পয়েন্টের সংখ্যা। এখানে আমরা পরের মানটি খুঁজতে N এর আকারের অ্যারে ব্যবহার করি।

উল্লেখ