Konveks Hull Alqoritmi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Həndəsə Morgan Stanley SamsungBaxılıb 118

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

“Konveks Korpus Alqoritmi” problemində bir sıra nöqtələr verdik. İçindəki bütün digər nöqtələri ehtiva edən nöqtələrlə meydana gələ biləcək ən kiçik çoxbucaq onun qabarıq gövdəsi adlanacaqdır.

Konveks Hull AlqoritmiPin

Bunu istifadə etməklə əldə etmək olar Jarvis Alqoritmi.

Alqoritm

  1. Ən sol nöqtəni 0-a başlayın.
  2. Bəyan edin a vektor Point tipinin nəticəsi
  3. Ən sol nöqtə tapılana qədər nöqtələr obyekti cərgəsini keçin
  4. Bu nöqtəni nəticə vektoruna əlavə edin
  5. Növbəti məqamı tapın "Q" digər nöqtələrin əksinə saat yönünün ən əks nöqtəsidir
  6. P-ni işarələyin "Q" növbəti təkrarlama üçün.
  7. Bir müddət əlavə etməyə davam edin "P" sola bərabər deyil.

təsvir

Beləliklə, qabarıq gövdəni həll etmək üçün əsas fikrimiz oriyentasiya istifadə etməkdir. Ən solda və ya bəlkə də ən aşağı X koordinatını tapıb başlayacağıq. Bəzi nöqtələrin toplana biləcəyi bütün nöqtələrimiz tapılana qədər onu götürə bilərik.

Kodun əvvəlində müəyyənləşdirdiyimiz Point istifadəçi sinfinin Object array nöqtələrini ötürəcəyik. Tam ədədin nöqtə və uzunluq arqumentləri qabarıq gövdəyə ötürülür funksiyası, burada nəticəni saxlayacağımız nəticə adlı vektoru elan edəcəyik.

İndi ən sol nöqtəni 0-a başladın. 0 koordinatına sahib olan nöqtəni və ya ən sol x nöqtəni alsaq, onu XNUMX-dan başlayacağıq.

İndi bütün nöqtələri keçin və ən aşağı olanı tapın. Ən soldakı vəziyyəti saxlayın "P" və bir nöqtə elan et

İndi edəcəyimiz ilk şeyin ilk nöqtəni bir nəticə olaraq əlavə etməsi üçün bir do-while döngəsinə başlayın.

İndi bütün digər nöqtələrə saat yönünün əks istiqamətində ən çox nöqtəni tapmalıyıq, bunun üçün oriyentasiya istifadə edəcəyik. Bunun üçün ayrıca üç funksiyanın 2-yə bərabər olub-olmadığını yoxlayan 2-nin olub olmadığını yoxlayan nöqtə dəyərini yeniləyən ayrı bir funksiya hazırladıq. "Q".

Bu qədər davam etməlidir "P" sola bərabər deyil.

misal

Verilən məqamlar bunlardır:

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

solda = 0;

Bütün nöqtələri keçdikdən sonra ilk ən aşağı x koordinatımız (0,3) nəticə verərək saxlayacaqdır.
İndi hansını yoxlayacağıq x, y cütlük ən çox saat yönünün əksinədir, çünki 2 kimi istiqamət verəcək və nöqtənin dəyərini yeniləyəcəkdir "Q".
Cütlük (0,0) olaraq tapılacaqdır.
İndi nöqtənin dəyərini kopyalayın "Q" yenidən saat yönünün ən əks nöqtəsini tapmaq üçün növbəti nöqtə olaraq p şəklində.
P dəyəri sola bərabər olmayana qədər bu dövrəni istifadə edəcəyik.
Çıxışımız: (0,3), (0,0), (3,0), (3,3)

Həyata keçirilməsi

Konveks Hull Alqoritmi üçün C ++ proqramı

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

Konveks Hull Alqoritmi üçün Java proqramı

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)

Konveks Hull Alqoritmi üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (m * n) burada n - giriş nöqtələrinin sayı, m - çıxış nöqtələrinin sayı.

Kosmik Mürəkkəblik

O (n) burada n giriş nöqtələrinin sayıdır. Burada növbəti dəyəri tapmaq üçün N ölçülü bir sıra istifadə edirik.

arayış

Crack Sistemi Dizayn Müsahibələri
Translate »