אלגוריתם קמור קמור


רמת קושי בינוני
נשאל לעתים קרובות גֵאוֹמֶטרִי מורגן סטנלי סמסונג

בבעיה "אלגוריתם הגולמי הקמור" נתנו סט של כמה נקודות. המצולע הקטן ביותר שיכול להיווצר עם אותם נקודות המכילות את כל הנקודות האחרות בתוכו ייקרא גוף הקמור שלו.

אלגוריתם קמור קמור

ניתן להשיג זאת באמצעות אלגוריתם של ג'רוויס.

אַלגוֹרִיתְם

  1. אתחל את הנקודה השמאלית ביותר ל -0.
  2. הכריז א וקטור תוצאה בשם סוג נקודה
  3. חצו את מערך אובייקט הנקודות עד למציאת הנקודה השמאלית הראשונה
  4. הוסף נקודה זו לווקטור התוצאה
  5. מצא את הנקודה הבאה "Q" כזו שזו הנקודה הכי נגד כיוון השעון מכל הנקודות האחרות
  6. הגדר את p לנקודה "Q" לאיטרציה הבאה.
  7. המשך להוסיף תוך כדי "P" אינו שווה לשמאל.

תיאור

אז הרעיון העיקרי שלנו לפתור את הגג הקמור הוא להשתמש בכיוון. אנו הולכים למצוא את הקואורדינטות X הכי שמאלי או אולי הנמוך ביותר. ואנחנו יכולים לקחת את זה עד שנמצאות כל הנקודות שלנו בהן קבוצה של כמה נקודות יכולה להצטבר.

אנו הולכים להעביר את נקודות מערך האובייקטים של מחלקת המשתמש Point, שכבר אנו מגדירים זאת בתחילת הקוד. הטיעונים שלנו על נקודות ואורכים של המספר השלם מועברים לגוף הקמור פונקציה, שם נכריז על התוצאה בשם וקטור בה אנו הולכים לאחסן את התפוקה שלנו.

כעת אתחל את הנקודה השמאלית ביותר ל- 0. אנו נתחיל אותה מ- 0, אם נקבל את הנקודה בעלת הקואורדינטה x הנמוכה ביותר או את הנקודה השמאלית ביותר אנו נשנה אותה.

עכשיו חצו את כל הנקודות וגלו את הנמוכה ביותר. אחסן את המיקום השמאלי ביותר ל- "P" ולהכריז על נקודה

עכשיו התחל לולאת עשה בזמן שהדבר הראשון שנעשה הוא להוסיף את הנקודה הראשונה כפלט.

כעת עלינו למצוא את הנקודה הכי נגד כיוון השעון לכל שאר הנקודות, לשם כך נשתמש בכיוון. עשינו פונקציה נפרדת לשם כך, שבודקת אם כיוון השלשות הוא 2 או לא אם נמצא 2 ואז מעדכן את ערך הנקודה "Q".

יש להמשיך בכך עד ל "P" אינו שווה לשמאל.

דוגמה

הנקודות הנתונות הן:

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

הכי שמאל = 0;

לאחר חציית כל הנקודות, קואורדינטת ה- x הנמוכה הראשונה שלנו תהיה (0,3) שהיא תאחסן כתוצאה מכך.
עכשיו זה הולך לבדוק איזה x, y לזוג יש הכי נגד כיוון השעון מכיוון שהוא ייתן כיוון כ -2 ויעדכן את ערך הנקודה "Q".
זוג שיימצא כ (0,0).
כעת, העתק את ערך הנקודה "Q" לתוך p כנקודה הבאה לשוב לגלות את הנקודה הכי נגד כיוון השעון.
עד שהערך של 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)

ניתוח מורכבות לאלגוריתם הגולמי הקמור

מורכבות זמן

O (m * n) כאשר n הוא מספר נקודות הכניסה ו- m הוא מספר נקודות הפלט.

מורכבות בחלל

O (n) כאשר n הוא מספר נקודות הקלט. כאן אנו משתמשים במערך בגודל N כדי למצוא את הערך הבא.

התייחסות