Algoritmo Quickhull para casco convexo

Dado un conjunto de puntos, un casco convexo es el polígono convexo más pequeño que contiene todos los puntos dados. La entrada es una array de puntos especificados por sus coordenadas x e y. La salida es un casco convexo de este conjunto de puntos en orden ascendente de coordenadas x. Ejemplo :

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)

Hemos discutido los siguientes algoritmos para el problema del casco convexo. Casco convexo | Conjunto 1 (algoritmo de Jarvis o envoltura) Casco convexo | Conjunto 2 (Graham Scan) El algoritmo QuickHull es un algoritmo Divide and Conquer similar a QuickSort . Sea a[0…n-1] la array de puntos de entrada. Los siguientes son los pasos para encontrar el casco convexo de estos puntos.

1. Encuentre el punto con la coordenada x mínima, digamos, min_x y, de manera similar, el punto con la coordenada x máxima, max_x.
2. Haz una línea que una estos dos puntos, digamos L . Esta línea dividirá todo el conjunto en dos partes. Tome ambas partes una por una y continúe.
3. Para una parte, encuentre el punto P con la distancia máxima de la línea L. P forma un triángulo con los puntos min_x, max_x. Está claro que los puntos que residen dentro de este triángulo nunca pueden ser parte del casco convexo.
4. El paso anterior divide el problema en dos subproblemas (resueltos recursivamente). Ahora la línea que une los puntos P y min_x y la línea que une los puntos P y max_x son líneas nuevas y los puntos que residen fuera del triángulo es el conjunto de puntos. Repita el punto No. 3 hasta que no quede ningún punto con la línea. Agregue los puntos finales de este punto al casco convexo.

A continuación se muestra la implementación en C++ de la idea anterior. La implementación usa set para almacenar puntos para que los puntos se puedan imprimir en orden. Un punto se representa como un par . 

// C++ program to implement Quick Hull algorithm
// to find convex hull.
#include<bits/stdc++.h>
using namespace std;
 
// iPair is integer pairs
#define iPair pair<int, int>
 
// Stores the result (points of convex hull)
set<iPair> hull;
 
// Returns the side of point p with respect to line
// joining points p1 and 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;
}
 
// returns a value proportional to the distance
// between the point p and the line joining the
// points p1 and 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));
}
 
// End points of line L are p1 and p2.  side can have value
// 1 or -1 specifying each of the parts made by the line L
void quickHull(iPair a[], int n, iPair p1, iPair p2, int side)
{
    int ind = -1;
    int max_dist = 0;
 
    // finding the point with maximum distance
    // from L and also on the specified side of 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;
        }
    }
 
    // If no point is found, add the end points
    // of L to the convex hull.
    if (ind == -1)
    {
        hull.insert(p1);
        hull.insert(p2);
        return;
    }
 
    // Recur for the two parts divided by a[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-coordinate of the ith point
    if (n < 3)
    {
        cout << "Convex hull not possible\n";
        return;
    }
 
    // Finding the point with minimum and
    // maximum x-coordinate
    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;
    }
 
    // Recursively find convex hull points on
    // one side of line joining a[min_x] and
    // a[max_x]
    quickHull(a, n, a[min_x], a[max_x], 1);
 
    // Recursively find convex hull points on
    // other side of line joining a[min_x] and
    // 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());
    }
}
 
// Driver code
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;
}

using System;
using System.Collections.Generic;
 
public static class GFG {
    static HashSet<List<int> > hull
        = new HashSet<List<int> >();
    // Stores the result (points of convex hull)
 
    // Returns the side of point p with respect to line
    // joining points p1 and p2.
    public static int findSide(List<int> p1, List<int> p2,
                               List<int> p)
    {
        int val = (p[1] - p1[1]) * (p2[0] - p1[0])
                  - (p2[1] - p1[1]) * (p[0] - p1[0]);
 
        if (val > 0) {
            return 1;
        }
        if (val < 0) {
            return -1;
        }
        return 0;
    }
 
    // returns a value proportional to the distance
    // between the point p and the line joining the
    // points p1 and p2
    public static int lineDist(List<int> p1, List<int> p2,
                               List<int> p)
    {
        return Math.Abs((p[1] - p1[1]) * (p2[0] - p1[0])
                        - (p2[1] - p1[1]) * (p[0] - p1[0]));
    }
 
    // End points of line L are p1 and p2. side can have
    // value 1 or -1 specifying each of the parts made by
    // the line L
    public static void quickHull(List<List<int> > a, int n,
                                 List<int> p1, List<int> p2,
                                 int side)
    {
        int ind = -1;
        int max_dist = 0;
 
        // finding the point with maximum distance
        // from L and also on the specified side of 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;
            }
        }
 
        // If no point is found, add the end points
        // of L to the convex hull.
        if (ind == -1) {
            hull.Add(p1);
            hull.Add(p2);
            return;
        }
 
        // Recur for the two parts divided by a[ind]
        quickHull(a, n, a[ind], p1,
                  -findSide(a[ind], p1, p2));
        quickHull(a, n, a[ind], p2,
                  -findSide(a[ind], p2, p1));
    }
 
    public static void printHull(List<List<int> > a, int n)
    {
        // a[i].second -> y-coordinate of the ith point
        if (n < 3) {
            Console.Write("Convex hull not possible\n");
            return;
        }
 
        // Finding the point with minimum and
        // maximum x-coordinate
        int min_x = 0;
        int max_x = 0;
        for (int i = 1; i < n; i++) {
            if (a[i][0] < a[min_x][0]) {
                min_x = i;
            }
            if (a[i][0] > a[max_x][0]) {
                max_x = i;
            }
        }
 
        // Recursively find convex hull points on
        // one side of line joining a[min_x] and
        // a[max_x]
        quickHull(a, n, a[min_x], a[max_x], 1);
        quickHull(a, n, a[min_x], a[max_x], -1);
 
        Console.Write("The points in Convex Hull are:\n");
        foreach(var item in hull)
        {
            Console.WriteLine(item[0] + " " + item[1]);
        }
    }
 
    // Driver code
    public static void Main()
    {
        // the set of points in the convex hull
        List<List<int> > a = new List<List<int> >();
        {
            a.Add(new List<int>() { 0, 3 });
            a.Add(new List<int>() { 1, 1 });
            a.Add(new List<int>() { 2, 2 });
            a.Add(new List<int>() { 4, 4 });
            a.Add(new List<int>() { 0, 0 });
            a.Add(new List<int>() { 1, 2 });
            a.Add(new List<int>() { 3, 1 });
            a.Add(new List<int>() { 3, 3 });
        };
 
        int n = a.Count;
        printHull(a, n);
    }
}
// The code is contributed by Aarti_Rathi

// JavaScript program to implement Quick Hull algorithm
// to find convex hull.
 
// Stores the result (points of convex hull)
let hull = new Set();
 
// Returns the side of point p with respect to line
// joining points p1 and p2.
function findSide(p1, p2, p)
{
    let val = (p[1] - p1[1]) * (p2[0] - p1[0]) -
            (p2[1] - p1[1]) * (p[0] - p1[0]);
 
    if (val > 0)
        return 1;
    if (val < 0)
        return -1;
    return 0;
}
 
// returns a value proportional to the distance
// between the point p and the line joining the
// points p1 and p2
function lineDist(p1, p2, p)
{
    return Math.abs ((p[1] - p1[1]) * (p2[0] - p1[0]) -
            (p2[1] - p1[1]) * (p[0] - p1[0]));
}
 
// End points of line L are p1 and p2. side can have value
// 1 or -1 specifying each of the parts made by the line L
function quickHull(a, n, p1, p2, side)
{
    let ind = -1;
    let max_dist = 0;
 
    // finding the point with maximum distance
    // from L and also on the specified side of L.
    for (let i=0; i<n; i++)
    {
        let temp = lineDist(p1, p2, a[i]);
        if ((findSide(p1, p2, a[i]) == side) && (temp > max_dist))
        {
            ind = i;
            max_dist = temp;
        }
    }
 
    // If no point is found, add the end points
    // of L to the convex hull.
    if (ind == -1)
    {
        hull.add(p1);
        hull.add(p2);
        return;
    }
 
    // Recur for the two parts divided by a[ind]
    quickHull(a, n, a[ind], p1, -findSide(a[ind], p1, p2));
    quickHull(a, n, a[ind], p2, -findSide(a[ind], p2, p1));
}
 
function printHull(a, n)
{
    // a[i].second -> y-coordinate of the ith point
    if (n < 3)
    {
        console.log("Convex hull not possible");
        return;
    }
 
    // Finding the point with minimum and
    // maximum x-coordinate
    let min_x = 0, max_x = 0;
    for (let i=1; i<n; i++)
    {
        if (a[i][0] < a[min_x][0])
            min_x = i;
        if (a[i][0] > a[max_x][0])
            max_x = i;
    }
 
    // Recursively find convex hull points on
    // one side of line joining a[min_x] and
    // a[max_x]
    quickHull(a, n, a[min_x], a[max_x], 1);
 
    // Recursively find convex hull points on
    // other side of line joining a[min_x] and
    // a[max_x]
    quickHull(a, n, a[min_x], a[max_x], -1);
 
    console.log("The points in Convex Hull are:");
     
    hull.forEach(element =>{
        console.log("(", element[0], ", ", element[1], ") ");
    })
}
 
// Driver code
{
    let a = [[0, 3], [1, 1], [2, 2], [4, 4],
            [0, 0], [1, 2], [3, 1], [3, 3]];
    let n = a.length;
    printHull(a, n);
}
 
// The code is contributed by Nidhi goel

Aporte :

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

Complejidad de tiempo: el análisis es similar a Quick Sort. En promedio, obtenemos la complejidad del tiempo como O(n Log n), pero en el peor de los casos, puede convertirse en O(n ² ) Amritya Yagni contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.