Дөңес корпустың алгоритмі


Күрделілік дәрежесі орта
Жиі кіреді геометриялық Морган Стэнли Samsung

«Дөңес корпустың алгоритмі» есебінде біз бірнеше нүктелер жиынтығын келтірдік. Ішіндегі барлық басқа нүктелерді қамтитын нүктелермен түзуге болатын ең кіші көпбұрыш оның дөңес корпусы деп аталады.

Дөңес корпустың алгоритмі

Бұған қолдану арқылы қол жеткізуге болады Джарвис алгоритмі.

Алгоритм

  1. Ең сол жақтағы нүктені 0-ге дейін бастаңыз.
  2. Декларация а векторы Point типінің нәтижесі
  3. Нүктелер объектісінің массивін ең сол жақ нүкте табылғанша өтіңіз
  4. Осы нүктені нәтиже векторына қосыңыз
  5. Келесі тармақты табыңыз «Q» ол барлық басқа нүктелерден сағат тіліне қарсы бағыттағы ең нүкте
  6. P мәнін орнатыңыз «Q» келесі қайталану үшін.
  7. Біраз уақыт қосыңыз «P» сол жаққа тең емес.

сипаттамасы

Сонымен, дөңес корпусты шешудің негізгі идеясы - бағдарлау. Біз X координатасын сол жақта немесе ең төменгіде табамыз және бастаймыз. Біз кейбір нүктелер жиынтығы жиналатын барлық нүктелер табылғанға дейін оны қабылдай аламыз.

Біз пайдаланушы класының Point массивтік нүктелерін жібереміз, оны біз кодтың басында анықтаймыз. Біздің бүтін санның және ұзындықтың аргументтері дөңес корпусқа беріледі функция, онда біз өз нәтижемізді сақтайтын нәтиже деп аталған векторды жариялаймыз.

Енді сол жақтағы нүктені 0-ге дейін инициализациялаңыз, егер біз координатасы ең аз х нүктесін алсақ немесе оны өзгертсек, оны 0-ден бастаймыз.

Енді барлық нүктелерді айналып өтіп, ең төменгісін табыңыз. Сол жақтағы күйді сақтаңыз «P» және нүкте жариялаңыз

Енді, біз бірінші жасаймыз, бірінші нүктені нәтиже ретінде қосатын do-while циклын бастаңыз.

Енді біз барлық басқа нүктелерге сағат тіліне қарсы ең көп нүктені табуымыз керек, ол үшін бағдар қолданамыз. Біз бұл үшін үш функцияның 2-ге тең болатындығын немесе 2-ге тең болғанын тексеретін жеке функция жасадық, содан кейін нүкте мәнін жаңартыңыз «Q».

Дейін жалғасуы керек «P» сол жаққа тең емес.

мысал

Берілген ұпайлар:

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

сол жақта = 0;

Барлық нүктелерден өтіп, біздің ең төменгі х координатамыз (0,3) болады, нәтижесінде ол сақталады.
Енді қайсысы тексерілетін болады x, y жұп сағат тіліне қарсы бағытталған, өйткені ол бағытты 2-ге теңестіреді және нүктенің мәнін жаңартады «Q».
Жұпты (0,0) деп табу керек.
Енді нүктенің мәнін көшіріңіз «Q» сағат тіліне қарсы бағытты қайтадан анықтайтын келесі нүкте ретінде p-ге.
P мәні сол жаққа тең болмағанша, біз бұл циклды қолданамыз.
Біздің өніміміз: (0,3), (0,0), (3,0), (3,3)

Іске асыру

Дөңес Hull алгоритміне арналған 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)

Convex Hull алгоритміне арналған 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 (m * n) Мұндағы n - кіріс нүктелерінің саны, m - шығу нүктелерінің саны.

Ғарыштың күрделілігі

O (N) мұндағы n - енгізу нүктелерінің саны. Мұнда келесі мәнді табу үшін N өлшемді жиым қолданылады.

анықтамалық