볼록 껍질 알고리즘

난이도 중급
자주 묻는 질문 기하학적 모건 스탠리 (Morgan Stanley) 삼성조회수 72

“볼록 껍질 알고리즘”문제에서 우리는 몇 가지 포인트를 제공했습니다. 내부에 다른 모든 점을 포함하는 점으로 형성 할 수있는 가장 작은 다각형을 볼록 껍질이라고합니다.

볼록 껍질 알고리즘

이것은 다음을 사용하여 얻을 수 있습니다. 자비스 알고리즘.

암호알고리즘

  1. 가장 왼쪽 지점을 0으로 초기화합니다.
  2. 선언 벡터 포인트 유형의 명명 된 결과
  3. 가장 왼쪽에있는 지점을 찾을 때까지 points 객체 배열을 순회합니다.
  4. 그 점을 결과 벡터에 추가하십시오.
  5. 다음 지점 찾기 "Q" 다른 모든 지점에서 가장 반 시계 방향 지점이되도록
  6. p를 포인트로 설정 "Q" 다음 반복을 위해.
  7. 계속 합산하는 동안 "P" 가장 왼쪽과 같지 않습니다.

제품 설명

따라서 볼록 껍질을 해결하는 주요 아이디어는 방향을 사용하는 것입니다. 우리는 가장 왼쪽 또는 가장 낮은 X 좌표를 찾아서 시작할 것입니다. 그리고 우리는 어떤 점들이 축적 될 수있는 모든 점을 찾을 때까지 그것을 취할 수 있습니다.

코드 시작 부분에 이미 정의한 사용자 클래스 Point의 Object 배열 지점을 전달합니다. 점과 정수 길이의 인수는 볼록 껍질로 전달됩니다. 기능여기서 출력을 저장할 결과라는 벡터를 선언합니다.

이제 가장 왼쪽 지점을 0으로 초기화합니다. 가장 낮은 x 좌표를 가진 지점이나 가장 왼쪽 지점을 가져 오면이를 변경하려고합니다. 0부터 시작합니다.

이제 모든 지점을 가로 질러 가장 낮은 지점을 찾으십시오. 가장 왼쪽의 위치를 "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 ++ 프로그램

#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의 배열을 사용합니다.

참고

Translate »