ამოზნექილი ჰალის ალგორითმი


Რთული ტური საშუალო
ხშირად ეკითხებიან გეომეტრიული Morgan Stanley Samsung

პრობლემში ”ამოზნექილი კორპუსის ალგორითმი” ჩვენ მივცეთ რამდენიმე პუნქტის ნაკრები. ყველაზე პატარა პოლიგონს, რომელიც შეიძლება ჩამოყალიბდეს იმ წერტილებთან, რომლებიც შეიცავს მის შიგნით არსებულ ყველა სხვა წერტილს, მისი ამოზნექილი კორპუსი ეწოდება.

ამოზნექილი ჰალის ალგორითმი

ამის მიღწევა შესაძლებელია გამოყენებით ჯარვის ალგორითმი.

ალგორითმი

  1. ინიციალეთ მარცხენა წერტილი 0-ზე.
  2. გამოაცხადეთ ა ვექტორი Point ტიპის დასახელებული შედეგი
  3. გაიარეთ წერტილების ობიექტის მასივი მანამ, სანამ არ აღმოჩნდება მთავარი მარცხენა წერტილი
  4. შედეგის ვექტორს დაამატე ეს წერტილი
  5. იპოვნეთ შემდეგი წერტილი "Q" ისეთი, რომ ის საათის ისრის საწინააღმდეგო წერტილია ყველა სხვა წერტილისგან
  6. დააყენეთ p წერტილზე "Q" შემდეგი განმეორებისთვის.
  7. გააგრძელეთ დამატება სანამ "P" არ არის ტოლი მარცხნივ.

აღწერა

ამრიგად, ჩვენი მთავარი იდეა ამოზნექილი კორპუსის მოსაგვარებლად არის ორიენტაციის გამოყენება. ჩვენ ვაპირებთ ვიპოვოთ და დავიწყოთ ყველაზე დაბალი ან შესაძლოა ყველაზე დაბალი X კოორდინატით. და ჩვენ შეგვიძლია ავიღოთ მანამ, სანამ არ მოიძებნება ყველა ჩვენი წერტილი, რომელშიც შეიძლება დაგროვდეს რამდენიმე ქულა.

ჩვენ ვაპირებთ გადავიტანოთ მომხმარებლის კლასის Point ობიექტის მასივის წერტილები, რომლებსაც მას უკვე განვსაზღვრავთ კოდის დასაწყისში. მთელი რიცხვის წერტილებისა და სიგრძის ჩვენი არგუმენტები გადადის ამოზნექილ კორპუსში ფუნქცია, სადაც ჩვენ გამოვაცხადებთ ვექტორს დასახელებულ შედეგს, რომელშიც ჩვენ ვაპირებთ ჩვენი შედეგის შენახვას.

ახლა წამოაყენეთ ყველაზე მარცხენა წერტილი 0-ზე. ჩვენ დავიწყებთ მას 0 – დან, თუ მივიღებთ წერტილს, რომელსაც აქვს ყველაზე დაბალი x კოორდინატი ან ყველაზე მარცხენა წერტილი, ჩვენ ვაპირებთ მის შეცვლას.

ახლა გაიარეთ ყველა წერტილი და გაიგეთ ყველაზე დაბალი. შეინახეთ პოზიცია მარცხნივ "P" და გამოაცხადეთ წერტილი

ახლა დაიწყეთ do-while მარყუჟი, რომელშიც პირველი, რასაც ჩვენ გავაკეთებთ, არის პირველი წერტილის დამატება, როგორც გამომავალი.

ახლა ჩვენ უნდა ვიპოვნოთ საათის ისრის საწინააღმდეგო წერტილი ყველა სხვა წერტილისთვის, ამისათვის ჩვენ ვაპირებთ გამოვიყენოთ ორიენტაცია. ამისათვის ჩვენ გავაკეთეთ ცალკე ფუნქცია, რომელიც ამოწმებს არის თუ არა სამკუთხედის ორიენტაცია 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 ++ პროგრამა Convex Hull ალგორითმისთვის

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

Java პროგრამა ამოზნექილი კორპუსის ალგორითმისთვის

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 (მ * ნ) სადაც n არის შეყვანის წერტილების რაოდენობა და m არის გამომავალი წერტილების რაოდენობა.

სივრცის სირთულე

O (n) სადაც n არის შეყვანის წერტილების რაოდენობა. აქ ვიყენებთ N ზომის მასივს შემდეგი მნიშვნელობის მოსაძებნად.

Reference