બહિર્મુખ હલ એલ્ગોરિધમ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ભૌમિતિક મોર્ગન સ્ટેન્લી સેમસંગ

સમસ્યામાં "કન્વેક્સ હલ એલ્ગોરિધમ" અમે કેટલાક મુદ્દાઓનો સમૂહ આપ્યો છે. સૌથી નાના બહુકોણ કે જે તે બિંદુઓ સાથે રચાય છે જે તેની અંદરના બધા અન્ય બિંદુઓ ધરાવે છે તેને તેના બહિર્મુખ હલ કહેવાશે.

બહિર્મુખ હલ એલ્ગોરિધમ

આનો ઉપયોગ કરીને પ્રાપ્ત કરી શકાય છે જાર્વિસ એલ્ગોરિધમ.

અલ્ગોરિધમ

  1. ડાબી બાજુના બિંદુને 0 થી પ્રારંભ કરો.
  2. ઘોષણા કરો એ વેક્ટર પોઇન્ટ પ્રકારનું નામ આપેલ પરિણામ
  3. મુખ્ય ડાબી બિંદુ ન મળે ત્યાં સુધી પોઇન્ટ્સ objectબ્જેક્ટ એરેને પસાર કરો
  4. પરિણામ વેક્ટરમાં તે બિંદુ ઉમેરો
  5. આગળનો મુદ્દો શોધો "ક્યૂ" જેમ કે તે અન્ય તમામ બિંદુઓનો સૌથી ઘડિયાળની દિશામાં બિંદુ છે
  6. બિંદુ પર p સેટ કરો "ક્યૂ" આગામી પુનરાવૃત્તિ માટે.
  7. જ્યારે ઉમેરતા રહો "પી" ડાબી બાજુની બરાબર નથી.

વર્ણન

તેથી બહિર્મુખ હલને હલ કરવાનો અમારો મુખ્ય વિચાર લક્ષીકરણનો ઉપયોગ કરવાનો છે. અમે શોધવા અને શરૂ કરવા જઈ રહ્યા છીએ ડાબેથી અથવા કદાચ સૌથી નીચો એક્સ કોઓર્ડિનેટ. અને જ્યાં સુધી અમારા બધા પોઇન્ટ્સ ન મળે ત્યાં સુધી આપણે તે લઈ શકીએ છીએ જેમાં કેટલાક પોઇન્ટનો સમૂહ એકઠા થઈ શકે છે.

આપણે યુઝર ક્લાસ પોઇન્ટના jectબ્જેક્ટ એરે પોઇન્ટ્સ પસાર કરવા જઈ રહ્યા છીએ, જે આપણે કોડની શરૂઆતમાં જ તેને વ્યાખ્યાયિત કરી છે. પૂર્ણાંકોની બિંદુઓ અને લંબાઈની અમારી દલીલો બહિર્મુખ હલમાં પસાર થાય છે કાર્ય, જ્યાં આપણે વેક્ટર નામનું પરિણામ જાહેર કરીશું જેમાં આપણે આપણું આઉટપુટ સંગ્રહિત કરીશું.

હવે ડાબી બાજુના બિંદુને 0. થી પ્રારંભ કરો. આપણે તેને 0 થી શરૂ કરીશું, જો આપણને તે બિંદુ મળે કે જેમાં સૌથી નીચો એક્સ કોઓર્ડિનેટ હોય અથવા ડાબી બાજુનો બિંદુ હોય કે આપણે તેને બદલીશું.

હવે બધા પોઇન્ટ્સ વટાવી દો અને સૌથી નીચો એક શોધી કા .ો. ડાબી બાજુની સ્થિતિ સ્ટોર કરો "પી" અને એક મુદ્દો જાહેર કરો

હવે, ડૂ-વેઈંગ લૂપ શરૂ કરો જેમાં આપણે પ્રથમ વસ્તુ કરીશું તે આઉટપુટ તરીકે પ્રથમ બિંદુ ઉમેરવાનું છે.

હવે આપણે અન્ય તમામ બિંદુઓ પર સૌથી વધુ વિરુદ્ધ ઘડિયાળની દિશા શોધવી પડશે, આ માટે, અમે અભિગમ વાપરીશું. અમે આ માટે એક અલગ કાર્ય કર્યું છે, જે તપાસ કરે છે કે ત્રિવિધિઓનું લક્ષ્યાંક 2 છે કે નહીં તે 2 હોય તો પોઇન્ટની કિંમત અપડેટ કરો. "ક્યૂ".

આ સુધી ચાલુ રાખવું જોઈએ "પી" ડાબી બાજુની બરાબર નથી.

ઉદાહરણ

આપેલ મુદ્દાઓ છે:

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

ડાબું = 0;

બધા પોઇન્ટ્સને ઓળંગી ગયા પછી, અમારું પ્રથમ ન્યૂનતમ એક્સ કો-ઓર્ડિનેટ (0,3) હશે જે પરિણામે સંગ્રહિત કરશે.
હવે તે તપાસવા જઇ રહ્યું છે એક્સ, વાય જોડી સૌથી વધુ ઘડિયાળની દિશામાં હોય છે કારણ કે તે 2 તરીકે અભિગમ આપશે અને બિંદુની કિંમતને અપડેટ કરશે "ક્યૂ".
(0,0) તરીકે મળી જોડી.
હવે, બિંદુની કિંમત ક copyપિ કરો "ક્યૂ" ફરીથી સૌથી બિંદુ ઘડિયાળની દિશા શોધવા માટે આગળના બિંદુ તરીકે પી.
જ્યાં સુધી પી ની વેલ્યુ ડાબી બાજુની બરાબર ના હોય ત્યાં સુધી આપણે આ લૂપ નો ઉપયોગ કરીશું.
અમારું આઉટપુટ આ હશે: (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)

કોન્વેક્સ હલ એલ્ગોરિધમ માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એમ * એન) જ્યાં n એ ઇનપુટ પોઇન્ટની સંખ્યા છે અને એમ આઉટપુટ પોઇન્ટની સંખ્યા છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં n એ ઇનપુટ પોઈન્ટની સંખ્યા છે. અહીં આપણે આગામી મૂલ્ય શોધવા માટે, કદ N ની એરેનો ઉપયોગ કરીએ છીએ.

સંદર્ભ