Convex hull problem

Preface

Convex hull problem （Convex Hull） Is a classical problem in computational geometry , It is also an introduction to many computational geometry problems .

convex hull _ Baidu Encyclopedia As the name suggests, it is a convex polygon , It may be easier to see visually , But how to prove which are convex hull points , How to implement this in code is not easy .

Exercises ：

Power button ：587. Install fence

Power button ：812. Maximum triangle area

Related explanations ：

Install fence - Official explanation - Power button （LeetCode）

Compared with other convex hull codes found on the Internet , The explanation of this question is very friendly , It is recommended to take a look at the dynamic diagram of each algorithm

This article is almost written according to the solution to the problem , Among them, I added my own understanding and comments

Algorithm	Time complexity	Spatial complexity
Jarvis Algorithm	$O(n^2)$ ( Every time violence searches all points )	$O(n)$
Graham Algorithm	$O(nlogn)$ （$O(n)(OutEnter\; intoStack)+O(nlogn)(roworder)$）	$O(n)$ ( No sorting )
Andrew Algorithm	$O(nlogn)$ （$O(n)(OutEnter\; intoStack)+O(nlogn)(roworder)$）	$O(n)$ ( No sorting )

Vector product

Vector product _ Baidu Encyclopedia

Cross product

** Geometric meaning ：** The result is a vector , Perpendicular to the original vector

---

** Algebraic meaning ：** Die length ：（ ad locum θ Represents the angle between two vectors （ Common starting point ）（0°≤θ≤180°）, It lies on the plane defined by these two vectors .）

The absolute value of module length represents the area of a parallelogram composed of two vectors

---

The following figure p spot ,q spot ,r spot vector $pq$, vector $qr$ The vector product of

• Being positive , Then angle ＜ 180 degree $qrphaseYespqLeftpartial$
• by 0, Then angle = 180 degree ( parallel )
• Negative , Then angle > 180 degree $qrphaseYespqRightpartial$

---

This topic is based on this figure

• p Precursor point pre
• q Transfer point cur
• r Search point nex

---

There is no need to memorize relationships

Just need to know One is one minus one. , For two Different biases that will do

// p0p1 x p0p2  Common starting point p0
inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
    
    int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
    int x1 = p2[0] - p0[0], y1 = p2[1] - p0[1];
    return x0 * y1 - y0 * x1;
}
// p0p1 x p1p2 p1 As p0p1 The end ,p0p1 The starting point of the 
inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
    
    int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
    int x1 = p2[0] - p1[0], y1 = p2[1] - p1[1];
    return x0 * y1 - y0 * x1;
}

Convex hull algorithm

Jarvis Algorithm

Ideas ：

• Look for the outermost point as the starting point
  • To facilitate the establishment of coordinates , selection x Lowest point of shaft
• Keep looking for the next adjacent peripheral bump
  • Brute force traversal searches every point
  • The end of a cycle , Find what is currently available as the next point cur
  • Search for parallel points again
  • Qualified points if not visited , The answer is
• Until you find that the point is the same as the starting point , Then form a circle

// Jarvis  Algorithm 
class Solution {
    
public:
    //  In solving the convex hull problem, as long as the cross product effect is correct 
    // p0p1 x p0p2  Common starting point p0
    inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
    
        int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
        int x1 = p2[0] - p0[0], y1 = p2[1] - p0[1];
        return x0 * y1 - y0 * x1;
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
    
        int n = points.size();
        if (n <= 3) {
    
            return points;
        }

        // x  Leftmost left   Again y  At the bottom 
        int leftSide = 0;
        for (int i = 0; i < n; i++) {
    
            // C++ in  vector Compare elements in turn 
            if (points[i] < points[leftSide]) {
    
                leftSide = i;
            }
        }

        vector<vector<int>> ans;
        vector<bool> vis(n);

        int pre = leftSide;
        do {
    
            //  Keep looking for the target point to deposit ans
            int cur = (pre + 1) % n;
            //  Traverse all points to query the next target 
            for (int nex = 0; nex < n; nex++) {
    
                //  As long as unity goes in one direction , Ensure the consistency of the three relationships 
                if (cross(points[pre], points[cur], points[nex]) < 0) {
    
                    cur = nex;
                }
            }

            //  Handle parallel lines 
            for (int nex = 0; nex < n; nex++) {
    
                //  Not accessed   And not the first two points 
                if (vis[nex] || nex == pre || nex == cur) {
    
                    continue;
                }
                //  It's a parallel line 
                if (cross(points[pre], points[cur], points[nex]) == 0) {
    
                    vis[nex] = true;
                    ans.emplace_back(points[nex]);
                }
            }

            if (!vis[cur]) {
    
                vis[cur] = true;
                ans.emplace_back(points[cur]);
            }

            //  Pass on 
            pre = cur;
        } while (pre != leftSide);

        return ans;
    }
};

Graham Algorithm

Ideas ：

• Look for the outermost point as the starting point

  • To facilitate the establishment of coordinates , selection y Lowest point of shaft

• The rest of the points are sorted by polar coordinates The small polar angle is in front

  • The polar angles are the same Sort by distance （ near —> far ）
  • The point in the last convex hull Sort by distance （ far —> near ）

• Record convex hull points with stack

  • Before saving first buttom and sorted The first point of
  • The point at the top of the stack is used as the transit point cur And pop up
  • At this point, the new stack vertex is used as pre
  • Look for the inner deviation point And sort Of cross Consistent judgment
    • Will be searching for nex a.m. cross Inconsistent abandonment
    • until cross Consistent or parallel

• Finally, the points in the stack are all convex hull points

Be careful ：

sort The same treatment for the middle polar angle

It's best to look at the schematic diagram , Go through the simulation , The words are not easy to explain

• Non final convex hull （ near —> far ）
  • Give priority to near points , When it reaches the far point , You can round off the nearest point
• The last convex hull （ far —> near ）
  • Because it is the last convex hull , Therefore, all points on the line are qualified
  • First deal with the remote point and then , All near points must be qualified

// Graham  Algorithm 
class Solution {
    
   public:
    //  In solving the convex hull problem, as long as the cross product effect is correct 
    // p0p1 x p0p2  Common starting point p0
    inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
    
        int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
        int x1 = p2[0] - p0[0], y1 = p2[1] - p0[1];
        return x0 * y1 - y0 * x1;
    }
    //  Distance between two points , Ensure that the precision does not need to open the root 
    inline int distance(vector<int>& p0, vector<int>& p1) {
    
        int x = p0[0] - p1[0], y = p0[1] - p1[1];
        return x * x + y * y;
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
    
        int n = points.size();
        if (n <= 3) {
    
            return points;
        }

        //  Just find y The lowest point of the axis 
        //  Points parallel to this point are automatically processed 
        int buttom = 0;
        for (int i = 0; i < n; i++) {
    
            if (points[i][1] < points[buttom][1]) {
    
                buttom = i;
            }
        }
        //  Put this point in the first part , No sorting and traversal 
        swap(points[0], points[buttom]);

        //  Sort according to the size of the polar angle 
        sort(points.begin() + 1, points.end(),
             [&](vector<int>& a, vector<int>& b) {
    
                 int angle = cross(points[0], a, b);
                 //  If parallel , Then the small distance is in front 
                 return (angle == 0)
                            ? (distance(points[0], a) < distance(points[0], b))
                            : (angle > 0);
             });

        //  Place the point in the last line , distance buttom Far ahead 
        int e = n - 1;
        while (e >= 0 && cross(points[0], points[n - 1], points[e]) == 0) {
    
            e--;
        }
        //  It's in order , Reverse it 
        reverse(points.begin() + e + 1, points.end());

        stack<int> stk;
        stk.push(0);
        stk.push(1);
        //  After two pre stored points , from idx2 To traverse the 
        for (int nex = 2; nex < n; nex++) {
    
            int cur = stk.top();
            stk.pop();

            //  If facing outward , It means that the transfer point is inside , unqualified 
            //  there cross Judging conditions and sort The opposite of 
            while (!stk.empty() &&
                   cross(points[stk.top()], points[cur], points[nex]) < 0) {
    
                cur = stk.top();
                stk.pop();
            }

            //  Here is the transfer point cur Acceptable nex spot 
            //  That is, inward or parallel 
            stk.push(cur);
            stk.push(nex);
        }

        //  All points in the stack are convex hulls 
        vector<vector<int>> ans;
        while (!stk.empty()) {
    
            ans.emplace_back(points[stk.top()]);
            stk.pop();
        }

        return ans;
    }
};

Andrew Algorithm

Ideas ：

• All points according to x Axis sort , Press again y Axis sort
  • point.front() Leftmost left Used for one round of traversal to find one side
  • point.back() The most right Used for two rounds of traversal to find the other side
• Put the endpoint on the stack
  • no need vis Record Because you need to stack twice to close
• Two rounds of traversal Keep the same bias Take the initial stack point as the horizontal line ( Let's say left then right , First down, then up )
  • The first round From left to right Search below
  • The second round From right to left Search the top
• End of traversal , End with leftmost stack , At the same time, it is the first one to put on the stack ( Stack twice )
• pop() The starting point of falling into the stack twice , Get the point stack of convex hull

// Andrew  Algorithm 
class Solution {
    
public:
    //  In solving the convex hull problem, as long as the cross product effect is correct 
    // p0p1 x p0p2  Common starting point p0
    inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
    
        int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
        int x1 = p2[0] - p0[0], y1 = p2[1] - p0[1];
        return x0 * y1 - y0 * x1;
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
    
        int n = points.size();
        if (n <= 3) {
    
            return points;
        }

        //  According to the first x Shaft row , Press again y Shaft row 
        // point.front()  Leftmost left  point.back()  The most right 
        sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b) {
    
            return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
        });

        //  The two cycles are calculated by stk.front() Is the upper and lower half of the horizontal line 
        stack<int> stk;
        //  So it's time to vis Will be like SPFA Same change value 
        vector<bool> vis(n, false);

        //  The leftmost point is stacked 
        stk.push(0);
        
        //  To close , The leftmost point needs to be stacked twice , No record vis
        //  Two rounds guarantee the same cross Direction 
        //  Skip the starting point from left to right 
        for (int nex = 1; nex < n; nex++) {
    
            int cur = stk.top();
            stk.pop();
            //  Keep the first and last element 
            while (stk.size() > (1 - 1) &&
                   cross(points[stk.top()], points[cur], points[nex]) < 0) {
    
                vis[cur] = false;
                cur = stk.top();
                stk.pop();
            }

            //  Here is the transfer point cur Acceptable nex spot 
            //  That is, inward or parallel 
            stk.push(cur);
            stk.push(nex);
            vis[nex] = true;
        }

        int half = stk.size();
        //  Skip the starting point from right to left 
        for (int nex = n - 2; nex >= 0; nex--) {
    
            //  This point has been recorded in the previous round 
            if (vis[nex]) {
    
                continue;
            }
            int cur = stk.top();
            stk.pop();
            //  Keep the points found in the last round 
            while (stk.size() > (half - 1) &&
                   cross(points[stk.top()], points[cur], points[nex]) < 0) {
    
                vis[cur] = false;
                cur = stk.top();
                stk.pop();
            }
            
            //  Here is the transfer point cur Acceptable nex spot 
            //  That is, inward or parallel 
            stk.push(cur);
            stk.push(nex);
            vis[nex] = true;
        }

        vector<vector<int>> ans;
        //  Remove the horizontal mark of repeated addition 
        for (stk.pop(); !stk.empty(); stk.pop()) {
    
            ans.push_back(points[stk.top()]);
        }

        return ans;
    }
};

---

---

---

END