469. Convex Polygon (Medium)

Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).

Note:

1. There are at least 3 and at most 10,000 points.
2. Coordinates are in the range -10,000 to 10,000.
3. You may assume the polygon formed by given points is always a simple polygon (Simple polygon definition). In other words, we ensure that exactly two edges intersect at each vertex, and that edges otherwise don't intersect each other.

Example 1:

[[0,0],[0,1],[1,1],[1,0]]

Answer: True

Explanation:

Example 2:

[[0,0],[0,10],[10,10],[10,0],[5,5]]

Answer: False

Explanation:

Solution: Math

这道题让我们让我们判断一个多边形是否为凸多边形，我想关于凸多边形的性质，我大天朝的初中几何就应该有所涉猎啦吧，忘了的去面壁。就是所有的顶点角都不大于180度。那么我们该如何快速验证这一个特点呢，学过计算机图形学或者是图像处理的课应该对计算法线normal并不陌生吧，计算的curve的法向量是非常重要的手段，一段连续曲线可以离散看成许多离散点组成，而相邻的三个点就是最基本的单位，我们可以算由三个点组成的一小段曲线的法线方向，而凸多边形的每个三个相邻点的法向量方向都应该相同，要么同正，要么同负。那么我们只要遍历每个点，然后取出其周围的两个点计算法线方向，然后跟之前的方向对比，如果不一样，直接返回false。这里我们要特别注意法向量为0的情况，如果某一个点的法向量算出来为0，那么正确的pre就会被覆盖为0，后面再遇到相反的法向就无法检测出来，所以我们对计算出来法向量为0的情况直接跳过即可，参见代码如下：

get the cross product of the sequential input edge a, b as tmp, then:

if tmp == 0, a -> b 180° on the same line; elif tmp > 0, a -> b clockwise; else tmp < 0, a -> anticlockwise;

tmp = (p1[0]-p0[0])(p2[1]-p0[1])-(p2[0]-p0[0])(p1[1]-p0[1])

class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        int n = points.size();
        bool gotNegative = false, gotPositive = false;
        // 3 points: A, B, C
        for (int A = 0; A < n; ++A) {
            int B = (A+1)%n, C = (B+1)%n;
            int dx1 = points[A][0] - points[B][0];
            int dy1 = points[A][1] - points[B][1];
            int dx2 = points[C][0] - points[B][0];
            int dy2 = points[C][1] - points[B][1];
            int crossprod = dx1*dy2-dy1*dx2;
            if (crossprod < 0) gotNegative = true;
            else if (crossprod > 0) gotPositive = true;
            if (gotNegative && gotPositive) return false; 
        }
        return true;
    }
};