Алгоритм выпуклой оболочки


Сложный уровень средний
Часто спрашивают в Геометрическая Morgan Stanley Samsung

В задаче «Алгоритм выпуклой оболочки» мы задали набор некоторых точек. Наименьший многоугольник, который может быть образован из тех точек, которые содержат все остальные точки внутри него, будет называться его выпуклой оболочкой.

Алгоритм выпуклой оболочки

Это может быть достигнуто с помощью Алгоритм Джарвиса.

Алгоритм

  1. Инициализируйте крайнюю левую точку равной 0.
  2. Объявить вектор именованный результат типа Point
  3. Пройдите по массиву объектов точек, пока не найдете крайнюю левую точку
  4. Добавьте эту точку к результирующему вектору
  5. Найдите следующую точку "Q" так, чтобы это крайняя точка против часовой стрелки от всех других точек
  6. Установить p в точку "Q" для следующей итерации.
  7. Продолжайте складывать, пока "P" не равно крайнему левому.

Описание

Итак, наша основная идея решить выпуклую оболочку - использовать ориентацию. Мы собираемся найти и начать с самой левой или, возможно, самой низкой координаты X. И мы можем принимать это до тех пор, пока не будут найдены все наши точки, в которых может накапливаться набор некоторых точек.

Мы собираемся передать точки массива Object пользовательского класса Point, который мы уже определили в начале кода. Наши аргументы точек и длины целого числа передаются в выпуклую оболочку функция, где мы объявим вектор с именем result, в котором мы будем хранить наш вывод.

Теперь инициализируйте крайнюю левую точку равной 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 ++ для алгоритма выпуклой оболочки

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

Анализ сложности алгоритма выпуклой оболочки

Сложность времени

О (м * п) где n - количество входных точек, а m - количество выходных точек.

Космическая сложность

О (п) где n - количество входных точек. Здесь мы используем массив размера N, чтобы найти следующее значение.

Справка