ಕಾನ್ವೆಕ್ಸ್ ಹಲ್ ಅಲ್ಗಾರಿದಮ್


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಜ್ಯಾಮಿತೀಯ ಮಾರ್ಗನ್ ಸ್ಟಾನ್ಲಿ ಸ್ಯಾಮ್ಸಂಗ್

“ಕಾನ್ವೆಕ್ಸ್ ಹಲ್ ಅಲ್ಗಾರಿದಮ್” ಸಮಸ್ಯೆಯಲ್ಲಿ ನಾವು ಕೆಲವು ಅಂಶಗಳ ಗುಂಪನ್ನು ನೀಡಿದ್ದೇವೆ. ಅದರೊಳಗಿನ ಎಲ್ಲಾ ಇತರ ಬಿಂದುಗಳನ್ನು ಹೊಂದಿರುವ ಆ ಬಿಂದುಗಳೊಂದಿಗೆ ರಚಿಸಬಹುದಾದ ಚಿಕ್ಕ ಬಹುಭುಜಾಕೃತಿಯನ್ನು ಅದರ ಪೀನ ಹಲ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಕಾನ್ವೆಕ್ಸ್ ಹಲ್ ಅಲ್ಗಾರಿದಮ್

ಇದನ್ನು ಬಳಸಿ ಸಾಧಿಸಬಹುದು ಜಾರ್ವಿಸ್ ಅಲ್ಗಾರಿದಮ್.

ಕ್ರಮಾವಳಿ

  1. ಎಡಭಾಗದ ಬಿಂದುವನ್ನು 0 ಗೆ ಪ್ರಾರಂಭಿಸಿ.
  2. ಎ ಘೋಷಿಸಿ ವೆಕ್ಟರ್ ಪಾಯಿಂಟ್ ಪ್ರಕಾರದ ಹೆಸರಿನ ಫಲಿತಾಂಶ
  3. ಅಗ್ರಗಣ್ಯ ಎಡ ಬಿಂದು ಕಂಡುಬರುವವರೆಗೆ ಪಾಯಿಂಟ್ಸ್ ಆಬ್ಜೆಕ್ಟ್ ಅರೇ ಅನ್ನು ಹಾದುಹೋಗಿರಿ
  4. ಫಲಿತಾಂಶ ವೆಕ್ಟರ್‌ಗೆ ಆ ಬಿಂದುವನ್ನು ಸೇರಿಸಿ
  5. ಮುಂದಿನ ಹಂತವನ್ನು ಹುಡುಕಿ "ಪ್ರಶ್ನೆ" ಅದು ಇತರ ಎಲ್ಲ ಬಿಂದುಗಳಿಂದ ಅಪ್ರದಕ್ಷಿಣಾಕಾರವಾಗಿ ಬಿಂದುವಾಗಿದೆ
  6. P ಅನ್ನು ಪಾಯಿಂಟ್‌ಗೆ ಹೊಂದಿಸಿ "ಪ್ರಶ್ನೆ" ಮುಂದಿನ ಪುನರಾವರ್ತನೆಗಾಗಿ.
  7. ಹಾಗೆಯೇ ಸೇರಿಸುತ್ತಲೇ ಇರಿ "ಪಿ" ಎಡಭಾಗಕ್ಕೆ ಸಮನಾಗಿಲ್ಲ.

ವಿವರಣೆ

ಆದ್ದರಿಂದ ಪೀನ ಹಲ್ ಅನ್ನು ಪರಿಹರಿಸಲು ನಮ್ಮ ಮುಖ್ಯ ಆಲೋಚನೆ ದೃಷ್ಟಿಕೋನವನ್ನು ಬಳಸುವುದು. ನಾವು ಎಡಭಾಗದಿಂದ ಅಥವಾ ಕಡಿಮೆ ಎಕ್ಸ್ ನಿರ್ದೇಶಾಂಕದೊಂದಿಗೆ ಹುಡುಕಲು ಮತ್ತು ಪ್ರಾರಂಭಿಸಲಿದ್ದೇವೆ. ಮತ್ತು ನಮ್ಮ ಎಲ್ಲಾ ಬಿಂದುಗಳು ಕಂಡುಬರುವವರೆಗೆ ನಾವು ಅದನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು, ಇದರಲ್ಲಿ ಕೆಲವು ಬಿಂದುಗಳ ಒಂದು ಗುಂಪು ಸಂಗ್ರಹಗೊಳ್ಳುತ್ತದೆ.

ನಾವು ಬಳಕೆದಾರ ವರ್ಗ ಬಿಂದುವಿನ ಆಬ್ಜೆಕ್ಟ್ ಅರೇ ಪಾಯಿಂಟ್‌ಗಳನ್ನು ರವಾನಿಸಲಿದ್ದೇವೆ, ಅದನ್ನು ನಾವು ಈಗಾಗಲೇ ಕೋಡ್‌ನ ಪ್ರಾರಂಭದಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆ. ಪೂರ್ಣಾಂಕದ ಬಿಂದುಗಳು ಮತ್ತು ಉದ್ದಗಳ ನಮ್ಮ ವಾದಗಳನ್ನು ಪೀನ ಹಲ್‌ಗೆ ರವಾನಿಸಲಾಗುತ್ತದೆ ಕಾರ್ಯ, ಅಲ್ಲಿ ನಾವು ನಮ್ಮ .ಟ್‌ಪುಟ್ ಅನ್ನು ಸಂಗ್ರಹಿಸಲು ಹೋಗುವ ವೆಕ್ಟರ್ ಹೆಸರಿನ ಫಲಿತಾಂಶವನ್ನು ಘೋಷಿಸುತ್ತೇವೆ.

ಈಗ ಎಡಭಾಗದ ಬಿಂದುವನ್ನು 0 ಗೆ ಪ್ರಾರಂಭಿಸಿ. ನಾವು ಅದನ್ನು 0 ರಿಂದ ಪ್ರಾರಂಭಿಸಲಿದ್ದೇವೆ, ಕಡಿಮೆ x ನಿರ್ದೇಶಾಂಕವನ್ನು ಹೊಂದಿರುವ ಬಿಂದುವನ್ನು ನಾವು ಪಡೆದರೆ ಅಥವಾ ನಾವು ಅದನ್ನು ಬದಲಾಯಿಸಲಿದ್ದೇವೆ.

ಈಗ ಎಲ್ಲಾ ಬಿಂದುಗಳನ್ನು ಹಾದುಹೋಗಿರಿ ಮತ್ತು ಕಡಿಮೆ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ. ಎಡಭಾಗದಿಂದ ಸ್ಥಾನವನ್ನು ಸಂಗ್ರಹಿಸಿ "ಪಿ" ಮತ್ತು ಒಂದು ಅಂಶವನ್ನು ಘೋಷಿಸಿ

ಈಗ, ಮಾಡಬೇಕಾದ ಸಮಯದಲ್ಲಿ ಲೂಪ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ, ಇದರಲ್ಲಿ ನಾವು ಮಾಡುವ ಮೊದಲ ಕೆಲಸವೆಂದರೆ ಮೊದಲ ಹಂತವನ್ನು .ಟ್‌ಪುಟ್‌ನಂತೆ ಸೇರಿಸುವುದು.

ಈಗ ನಾವು ಇತರ ಎಲ್ಲ ಬಿಂದುಗಳಿಗೆ ಹೆಚ್ಚು ಅಪ್ರದಕ್ಷಿಣಾಕಾರವಾಗಿ ಕಂಡುಹಿಡಿಯಬೇಕು, ಇದಕ್ಕಾಗಿ ನಾವು ದೃಷ್ಟಿಕೋನವನ್ನು ಬಳಸಲಿದ್ದೇವೆ. ಇದಕ್ಕಾಗಿ ನಾವು ಪ್ರತ್ಯೇಕ ಕಾರ್ಯವನ್ನು ಮಾಡಿದ್ದೇವೆ, ಇದು ತ್ರಿವಳಿಗಳ ದೃಷ್ಟಿಕೋನವು 2 ಆಗಿದೆಯೇ ಅಥವಾ 2 ಎಂದು ಕಂಡುಬಂದಲ್ಲಿ ಪರಿಶೀಲಿಸುತ್ತದೆ ನಂತರ ಬಿಂದುವಿನ ಮೌಲ್ಯವನ್ನು ನವೀಕರಿಸಿ "ಪ್ರಶ್ನೆ".

ಇದನ್ನು ತನಕ ಮುಂದುವರಿಸಬೇಕು "ಪಿ" ಎಡಭಾಗಕ್ಕೆ ಸಮನಾಗಿಲ್ಲ.

ಉದಾಹರಣೆ

ನೀಡಿರುವ ಅಂಶಗಳು ಹೀಗಿವೆ:

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

leftmost = 0;

ಎಲ್ಲಾ ಬಿಂದುಗಳನ್ನು ದಾಟಿದ ನಂತರ, ನಮ್ಮ ಮೊದಲ ಕಡಿಮೆ x ಕೋ-ಆರ್ಡಿನೇಟ್ ಆಗಿರುತ್ತದೆ (0,3) ಇದರ ಪರಿಣಾಮವಾಗಿ ಅದು ಸಂಗ್ರಹವಾಗುತ್ತದೆ.
ಈಗ ಅದು ಯಾವುದನ್ನು ಪರಿಶೀಲಿಸಲಿದೆ x, y ಜೋಡಿಯು ಅಪ್ರದಕ್ಷಿಣಾಕಾರವಾಗಿರುವುದರಿಂದ ಅದು ದೃಷ್ಟಿಕೋನವನ್ನು 2 ಎಂದು ನೀಡುತ್ತದೆ ಮತ್ತು ಬಿಂದುವಿನ ಮೌಲ್ಯವನ್ನು ನವೀಕರಿಸುತ್ತದೆ "ಪ್ರಶ್ನೆ".
ಜೋಡಿಯನ್ನು (0,0) ಎಂದು ಕಂಡುಹಿಡಿಯಬೇಕು.
ಈಗ, ಬಿಂದುವಿನ ಮೌಲ್ಯವನ್ನು ನಕಲಿಸಿ "ಪ್ರಶ್ನೆ" ಹೆಚ್ಚು ಅಪ್ರದಕ್ಷಿಣಾಕಾರವಾಗಿ ಕಂಡುಹಿಡಿಯುವ ಮುಂದಿನ ಹಂತವಾಗಿ p ಗೆ.
P ನ ಮೌಲ್ಯವು ಎಡಭಾಗಕ್ಕೆ ಸಮನಾಗಿರದವರೆಗೆ ನಾವು ಈ ಲೂಪ್ ಅನ್ನು ಬಳಸುತ್ತೇವೆ.
ನಮ್ಮ output ಟ್‌ಪುಟ್ ಹೀಗಿರುತ್ತದೆ: (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 ಎನ್ನುವುದು ಇನ್ಪುಟ್ ಪಾಯಿಂಟ್‌ಗಳ ಸಂಖ್ಯೆ ಮತ್ತು m ಎಂಬುದು output ಟ್‌ಪುಟ್ ಪಾಯಿಂಟ್‌ಗಳ ಸಂಖ್ಯೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಇಲ್ಲಿ n ಎನ್ನುವುದು ಇನ್ಪುಟ್ ಪಾಯಿಂಟ್ಗಳ ಸಂಖ್ಯೆ. ಮುಂದಿನ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಇಲ್ಲಿ ನಾವು N ಗಾತ್ರದ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಬಳಸುತ್ತೇವೆ.

ರೆಫರೆನ್ಸ್