Гүдгэр их биеийн алгоритм


Хэцүү байдлын түвшин Дунд
Байнга асуудаг геометр Morgan Stanley Samsung

“Гүдгэр их биеийн алгоритм” бодлогод бид зарим нэг цэгийг өгсөн болно. Бусад бүх цэгүүдийг агуулсан цэгүүдээс үүсэх хамгийн жижиг олон өнцөгтийг гүдгэр их бие гэж нэрлэнэ.

Гүдгэр их биеийн алгоритм

Үүнийг ашиглах замаар үүнийг хийж болно Жарвис алгоритм.

Алгоритм

  1. Хамгийн зүүн цэгийг 0 болгож эхлүүлнэ.
  2. Мэдүүлэх a вектор Point төрлийн нэртэй үр дүн
  3. Хамгийн эхний зүүн цэгийг олох хүртэл объектын массивыг дайран өнгөр
  4. Энэ цэгийг үр дүнгийн вектор дээр нэмнэ
  5. Дараагийн цэгийг олох "Q" Энэ нь бусад бүх цэгээс цагийн зүүний эсрэг хамгийн цэг юм
  6. P-ийг зааж өгөөрэй "Q" дараагийн давталтын хувьд.
  7. Хэсэг хугацаанд үргэлжлүүлэн нэмээрэй "P" хамгийн зүүнтэй тэнцүү биш байна.

Тодорхойлолт

Тиймээс гүдгэр их биеийг шийдэх бидний гол санаа бол чиг баримжаа ашиглах явдал юм. Бид хамгийн зүүн талын, магадгүй хамгийн бага X координатаас хайж эхлэх болно. Зарим цэгүүдийн багцыг хуримтлуулж болох бүх цэгүүдээ олох хүртэл бид үүнийг авч болно.

Бид хэрэглэгчийн Point объектын массив цэгүүдийг дамжуулах гэж байгаа бөгөөд үүнийг кодын эхэнд тодорхойлчихсон байгаа. Бүхэл тооны цэг ба уртын аргументыг гүдгэр их бие рүү дамжуулна үйл ажиллагаа, энд бид үр дүнгээ хадгалах үр дүнг нэрлэсэн векторыг зарлах болно.

Одоо хамгийн зүүн цэгийг 0 гэж эхлүүлээрэй. Хэрэв бид хамгийн бага x координаттай цэгийг авбал эсвэл хамгийн зүүн цэгийг өөрчлөх гэж байгаа бол үүнийг 0-ээс эхлүүлэх болно.

Одоо бүх цэгүүдийг тойрон гарч, хамгийн доод цэгийг олж мэдээрэй. Хамгийн зүүн талын байрлалыг хадгална уу "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.
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)

Гүдгэр их биеийн алгоритмд зориулсан 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 хэмжээтэй массивыг ашиглаж дараагийн утгыг олох болно.

лавлагаа