Download

what is the meaning of deleting a certain convex hulls

A model can generate several convex hulls, but what is the meaning of deleting a certain convex hulls? The next generation of the convex hull must use a whole model.

The algorithm for solving the above problem is very easy. We simply check whether the point to be removed is a part of the convex hull. If it is, then we have to remove that point from the initial set and then make the convex hull again (refer Convex hull (divide and conquer) ).
And if not then we already have the solution (the convex hull will not change).
filter_none
edit

play_arrow

brightness_4 [TABLE=“border: 0, cellpadding: 0, cellspacing: 0”]

// C++ program to demonstrate delete operation
// on Convex Hull.
#include<bits/stdc++.h>
using namespace std;

// stores the center of polygon (It is made
// global becuase it is used in comare function)
pair<int, int> mid;

// determines the quadrant of a point
// (used in compare())
int quad(pair<int, int> p)
{
if (p.first >= 0 && p.second >= 0)
return 1;
if (p.first <= 0 && p.second >= 0)
return 2;
if (p.first <= 0 && p.second <= 0)
return 3;
return 4;
}

// Checks whether the line is crossing the polygon
int orientation(pair<int, int> a, pair<int, int> b,
pair<int, int> c)
{
int res = (b.second-a.second)(c.first-b.first) -
(c.second-b.second)
(b.first-a.first);

if (res == 0) 
    return 0; 
if (res &gt; 0) 
    return 1; 
return -1; 

}

// compare function for sorting
bool compare(pair<int, int> p1, pair<int, int> q1)
{
pair<int, int> p = make_pair(p1.first - mid.first,
p1.second - mid.second);
pair<int, int> q = make_pair(q1.first - mid.first,
q1.second - mid.second);

int one = quad(p); 
int two = quad(q); 

if (one != two) 
    return (one &lt; two); 
return (p.second*q.first &lt; q.second*p.first); 

}

// Finds upper tangent of two polygons ‘a’ and ‘b’
// represented as two vectors.
vector<pair<int, int> > merger(vector<pair<int, int> > a,
vector<pair<int, int> > b)
{
// n1 -> number of points in polygon a
// n2 -> number of points in polygon b
int n1 = a.size(), n2 = b.size();

int ia = 0, ib = 0; 
for (int i=1; i&lt;n1; i++) 
    if (a*.first &gt; a[ia].first) 
        ia = i; 

// ib -&gt; leftmost point of b 
for (int i=1; i&lt;n2; i++) 
    if (b*.first &lt; b[ib].first) 
        ib=i; 

// finding the upper tangent 
int inda = ia, indb = ib; 
bool done = 0; 
while (!done) 
{ 
    done = 1; 
    while (orientation(b[indb], a[inda], a(inda+1)%n1]) &gt;=0) 
        inda = (inda + 1) % n1; 

    while (orientation(a[inda], b[indb], b(n2+indb-1)%n2]) &lt;=0) 
    { 
        indb = (n2+indb-1)%n2; 
        done = 0; 
    } 
} 

int uppera = inda, upperb = indb; 
inda = ia, indb=ib; 
done = 0; 
int g = 0; 
while (!done)//finding the lower tangent 
{ 
    done = 1; 
    while (orientation(a[inda], b[indb], b(indb+1)%n2])&gt;=0) 
        indb=(indb+1)%n2; 

    while (orientation(b[indb], a[inda], a(n1+inda-1)%n1])&lt;=0) 
    { 
        inda=(n1+inda-1)%n1; 
        done=0; 
    } 
} 

int lowera = inda, lowerb = indb; 
vector&lt;pair&lt;int, int&gt; &gt; ret; 

//ret contains the convex hull after merging the two convex hulls 
//with the points sorted in anti-clockwise order 
int ind = uppera; 
ret.push_back(a[uppera]); 
while (ind != lowera) 
{ 
    ind = (ind+1)%n1; 
    ret.push_back(a[ind]); 
} 

ind = lowerb; 
ret.push_back(b[lowerb]); 
while (ind != upperb) 
{ 
    ind = (ind+1)%n2; 
    ret.push_back(b[ind]); 
} 
return ret; 

}

// Brute force algorithm to find convex hull for a set
// of less than 6 points
vector<pair<int, int> > bruteHull(vector<pair<int, int> > a)
{
// Take any pair of points from the set and check
// whether it is the edge of the convex hull or not.
// if all the remaining points are on the same side
// of the line then the line is the edge of convex
// hull otherwise not
set<pair<int, int> >s;

for (int i=0; i&lt;a.size(); i++) 
{ 
    for (int j=i+1; j&lt;a.size(); j++) 
    { 
        int x1 = a*.first, x2 = a[j].first; 
        int y1 = a*.second, y2 = a[j].second; 

        int a1 = y1-y2; 
        int b1 = x2-x1; 
        int c1 = x1*y2-y1*x2; 
        int pos = 0, neg = 0; 
        for (int k=0; k&lt;a.size(); k++) 
        { 
            if (a1*a[k].first+b1*a[k].second+c1 &lt;= 0) 
                neg++; 
            if (a1*a[k].first+b1*a[k].second+c1 &gt;= 0) 
                pos++; 
        } 
        if (pos == a.size() || neg == a.size()) 
        { 
            s.insert(a*); 
            s.insert(a[j]); 
        } 
    } 
} 

vector&lt;pair&lt;int, int&gt; &gt;ret; 
for (auto e : s) 
    ret.push_back(e); 

// Sorting the points in the anti-clockwise order 
mid = {0, 0}; 
int n = ret.size(); 
for (int i=0; i&lt;n; i++) 
{ 
    mid.first += ret*.first; 
    mid.second += ret*.second; 
    ret*.first *= n; 
    ret*.second *= n; 
} 
sort(ret.begin(), ret.end(), compare); 
for (int i=0; i&lt;n; i++) 
    ret* = make_pair(ret*.first/n, ret*.second/n); 

return ret; 

}

// Returns the convex hull for the given set of points
vector<pair<int, int>> findHull(vector<pair<int, int>> a)
{
// If the number of points is less than 6 then the
// function uses the brute algorithm to find the
// convex hull
if (a.size() <= 5)
return bruteHull(a);

// left contains the left half points 
// right contains the right half points 
vector&lt;pair&lt;int, int&gt;&gt;left, right; 
for (int i=0; i&lt;a.size()/2; i++) 
    left.push_back(a*); 
for (int i=a.size()/2; i&lt;a.size(); i++) 
    right.push_back(a*); 

// convex hull for the left and right sets 
vector&lt;pair&lt;int, int&gt;&gt;left_hull = findHull(left); 
vector&lt;pair&lt;int, int&gt;&gt;right_hull = findHull(right); 

// merging the convex hulls 
return merger(left_hull, right_hull); 

}

// Returns the convex hull for the given set of points after
// remviubg a point p.
vector<pair<int, int>> removePoint(vector<pair<int, int>> a,
vector<pair<int, int>> hull,
pair<int, int> p)
{
// checking whether the point is a part of the
// convex hull or not.
bool found = 0;
for (int i=0; i < hull.size() && !found; i++)
if (hull*.first == p.first &&
hull*.second == p.second)
found = 1;

// If point is not part of convex hull 
if (found == 0) 
    return hull; 

// if it is the part of the convex hull then 
// we remove the point and again make the convex hull 
// and if not, we print the same convex hull. 
for (int i=0; i&lt;a.size(); i++) 
{ 
    if (a*.first==p.first && a*.second==p.second) 
    { 
        a.erase(a.begin()+i); 
        break; 
    } 
} 

sort(a.begin(), a.end()); 
return findHull(a); 

}

// Driver code
int main()
{
vector<pair<int, int> > a;
a.push_back(make_pair(0, 0));
a.push_back(make_pair(1, -4));
a.push_back(make_pair(-1, -5));
a.push_back(make_pair(-5, -3));
a.push_back(make_pair(-3, -1));
a.push_back(make_pair(-1, -3));
a.push_back(make_pair(-2, -2));
a.push_back(make_pair(-1, -1));
a.push_back(make_pair(-2, -1));
a.push_back(make_pair(-1, 1));

int n = a.size(); 

// sorting the set of points according 
// to the x-coordinate 
sort(a.begin(), a.end()); 
vector&lt;pair&lt;int, int&gt; &gt;hull = findHull(a); 

cout &lt;&lt; "Convex hull:

";
for (auto e : hull)
cout << e.first << " "
<< e.second << endl;

pair&lt;int, int&gt; p = make_pair(-5, -3); 
removePoint(a, hull, p); 

cout &lt;&lt; "

Modified Convex Hull:
";
for (auto e:hull)
cout << e.first << " "
<< e.second << endl;

return 0; 

}

Output:
convex hull: -3 0 -1 -9 2 -6 5 3 2 5