Рубрики

Быстрый алгоритм для выпуклого корпуса

При заданном наборе точек выпуклая оболочка является наименьшим выпуклым многоугольником, содержащим все заданные точки.

Ввод — это массив точек, заданных их координатами x и y. На выходе получается выпуклая оболочка этого набора точек в порядке возрастания координат x.

Пример :

Input : points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
                    {0, 0}, {1, 2}, {3, 1}, {3, 3}};
Output :  The points in convex hull are:
          (0, 0) (0, 3) (3, 1) (4, 4)

Input : points[] = {{0, 3}, {1, 1}
Output : Not Possible
There must be at least three points to form a hull.

Input  : points[] = {(0, 0), (0, 4), (-4, 0), (5, 0), 
                     (0, -6), (1, 0)};
Output : (-4, 0), (5, 0), (0, -6), (0, 4)

Мы обсудили следующие алгоритмы для выпуклой задачи Халла.
Выпуклая оболочка | Набор 1 (алгоритм Джарвиса или упаковка)
Выпуклая оболочка | Комплект 2 (Грэм Скан)

Алгоритм QuickHull — это алгоритм «Разделяй и властвуй», аналогичный QuickSort . Пусть a [0… n-1] будет входным массивом точек. Ниже приведены шаги для нахождения выпуклой оболочки этих точек.

  1. Найти точку с минимальной x-координатой, скажем, min_x и аналогично точке с максимальной x-координатой max_x.
  2. Проведите линию, соединяющую эти две точки, скажем, L. Эта строка разделит весь набор на две части. Возьмите обе части одну за другой и продолжайте.
  3. Для детали найдите точку P с максимальным расстоянием от линии L. P образует треугольник с точками min_x, max_x. Ясно, что точки, находящиеся внутри этого треугольника, никогда не могут быть частью выпуклой оболочки.
  4. Вышеуказанный шаг делит проблему на две подзадачи (решаемые рекурсивно). Теперь линия, соединяющая точки P и min_x, и линия, соединяющая точки P и max_x, являются новыми линиями, а точки, находящиеся за пределами треугольника, являются множеством точек. Повторите пункт №. 3, пока не осталось точки с линией. Добавьте конечные точки этой точки к выпуклой оболочке.

Ниже приведена реализация вышеуказанной идеи на C ++. Реализация использует набор для хранения точек, так что точки могут быть напечатаны в отсортированном порядке. Точка представляется в виде пары .

// C ++ программа для реализации алгоритма Quick Hull
// найти выпуклую оболочку.
#include<bits/stdc++.h>

using namespace std;

  
// iPair - целочисленные пары
#define iPair pair<int, int>

  
// Сохраняет результат (точки выпуклой оболочки)
set<iPair> hull;

  
// Возвращает сторону точки p относительно линии
// соединяем точки p1 и p2.

int findSide(iPair p1, iPair p2, iPair p)

{

    int val = (p.second - p1.second) * (p2.first - p1.first) -

              (p2.second - p1.second) * (p.first - p1.first);

  

    if (val > 0)

        return 1;

    if (val < 0)

        return -1;

    return 0;

}

  
// возвращает значение, пропорциональное расстоянию
// между точкой р и линией, соединяющей
// точки p1 и p2

int lineDist(iPair p1, iPair p2, iPair p)

{

    return abs ((p.second - p1.second) * (p2.first - p1.first) -

               (p2.second - p1.second) * (p.first - p1.first));

}

  
// Конечные точки линии L - это p1 и p2. сторона может иметь значение
// 1 или -1, определяя каждую из частей, сделанных линией L

void quickHull(iPair a[], int n, iPair p1, iPair p2, int side)

{

    int ind = -1;

    int max_dist = 0;

  

    // найти точку с максимальным расстоянием

    // из L, а также с указанной стороны L.

    for (int i=0; i<n; i++)

    {

        int temp = lineDist(p1, p2, a[i]);

        if (findSide(p1, p2, a[i]) == side && temp > max_dist)

        {

            ind = i;

            max_dist = temp;

        }

    }

  

    // Если точка не найдена, добавить конечные точки

    // из L в выпуклую оболочку.

    if (ind == -1)

    {

        hull.insert(p1);

        hull.insert(p2);

        return;

    }

  

    // Повторение для двух частей, разделенных на [ind]

    quickHull(a, n, a[ind], p1, -findSide(a[ind], p1, p2));

    quickHull(a, n, a[ind], p2, -findSide(a[ind], p2, p1));

}

  

void printHull(iPair a[], int n)

{

    // a [i] .second -> y-координата i-й точки

    if (n < 3)

    {

        cout << "Convex hull not possible\n";

        return;

    }

  

    // Нахождение точки с минимумом и

    // максимальная координата х

    int min_x = 0, max_x = 0;

    for (int i=1; i<n; i++)

    {

        if (a[i].first < a[min_x].first)

            min_x = i;

        if (a[i].first > a[max_x].first)

            max_x = i;

    }

  

    // Рекурсивно найти точки выпуклой оболочки на

    // одна сторона линии, соединяющая [min_x] и

    // a [max_x]

    quickHull(a, n, a[min_x], a[max_x], 1);

  

    // Рекурсивно найти точки выпуклой оболочки на

    // другая сторона линии, соединяющая [min_x] и

    // a [max_x]

    quickHull(a, n, a[min_x], a[max_x], -1);

  

    cout << "The points in Convex Hull are:\n";

    while (!hull.empty())

    {

        cout << "(" <<( *hull.begin()).first << ", "

             << (*hull.begin()).second << ") ";

        hull.erase(hull.begin());

    }

}

  
// Код драйвера

int main()

{

    iPair a[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},

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

    int n = sizeof(a)/sizeof(a[0]);

    printHull(a, n);

    return 0;

}

Вход:

The points in Convex Hull are:
(0, 0) (0, 3) (3, 1) (4, 4) 

Сложность времени: анализ аналогичен быстрой сортировке. В среднем мы получаем сложность времени как O (n Log n), но в худшем случае она может стать O (n 2 )

Эта статья предоставлена Амритьей Ягни . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Быстрый алгоритм для выпуклого корпуса

0.00 (0%) 0 votes