469 Convex Polygon

469. Convex Polygon

1. Question

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:

2. Implementation

(1) Geometry

思路: 凸多边形的定义是每个顶点的角度都小于180度, 判断一个多边形

要注意的地方有两点：(1)如果cross product是0，我们应该忽略，否则会影响之后的结果. (2)由于数字可能溢出，所以curCroosProduct和preCrossProduct要用long

class Solution {
    public boolean isConvex(List<List<Integer>> points) {
        int n = points.size();
        long curCrossProduct = 0;
        long preCrossProduct = 0;

        for (int i = 0; i < n; i++) {
            List<Integer> pointA = points.get(i);
            List<Integer> pointB = points.get((i + 1) % n);
            List<Integer> pointC = points.get((i + 2) % n);

            curCrossProduct = getCrossProduct(pointA, pointB, pointC);

            if (curCrossProduct != 0) {
                if (curCrossProduct * preCrossProduct < 0) {
                    return false;
                }
                preCrossProduct = curCrossProduct;
            }
        }
        return true;
    }

    public int getCrossProduct(List<Integer> pointA, List<Integer> pointB, List<Integer> pointC) {
        int BAx = pointB.get(0) - pointA.get(0);
        int BAy = pointB.get(1) - pointA.get(1);
        int CAx = pointC.get(0) - pointA.get(0);
        int CAy = pointC.get(1) - pointA.get(1);

        return BAx * CAy - CAx * BAy;
    }
}

3. Time & Space Complexity

时间复杂度O(n), n是顶点的个数, 空间复杂度O(1)