http://bookshadow.com/weblog/2016/12/04/leetcode-convex-polygon/
http://www.cnblogs.com/grandyang/p/6146986.html
就是所有的顶点角都不大于180度。那么我们该如何快速验证这一个特点呢，学过计算机图形学或者是图像处理的课应该对计算法线normal并不陌生吧，计算的curve的法向量是非常重要的手段，一段连续曲线可以离散看成许多离散点组成，而相邻的三个点就是最基本的单位，我们可以算由三个点组成的一小段曲线的法线方向，而凸多边形的每个三个相邻点的法向量方向都应该相同，要么同正，要么同负。那么我们只要遍历每个点，然后取出其周围的两个点计算法线方向，然后跟之前的方向对比，如果不一样，直接返回false。这里我们要特别注意法向量为0的情况，如果某一个点的法向量算出来为0，那么正确的pre就会被覆盖为0，后面再遇到相反的法向就无法检测出来，所以我们对计算出来法向量为0的情况直接跳过即可
https://discuss.leetcode.com/topic/70706/beyond-my-knowledge-java-solution-with-in-line-explanation
https://en.wikipedia.org/wiki/Complex_polygon
https://en.wikipedia.org/wiki/Right-hand_rule
https://betterexplained.com/articles/cross-product/
Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).
Note:
- There are at least 3 and at most 10,000 points.
- Coordinates are in the range -10,000 to 10,000.
- 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:
Example 2:
题目大意：
给定一组点，顺序相连可以组成一个多边形。判断多边形是否是凸包。
注意：
- 最少3个，最多10000个点
- 坐标在-10,000 到 10,000之间。
- 你可以假设组成的多边形总是简单多边形。换言之，我们确保每个顶点都是两条边的交点，其他边不会相互交叉。
解题思路：
遍历顶点，判断相邻三个顶点A、B、C组成的两个向量(AB, AC)的叉积是否同负同正。
https://discuss.leetcode.com/topic/70643/i-believe-this-time-it-s-far-beyond-my-ability-to-get-a-good-grade-of-the-contest
Line
tmp = (p1[0]-p0[0])*(p2[1]-p0[1])-(p2[0]-p0[0])*(p1[1]-p0[1]) is to calculate the determinant of 2x2 matrix det([p1-p0,p2-p0]).
Note that for any two 2D vectors
v1=(x1,y1), v2=(x2,y2), the cross product is calculated by the determinant of 2x2 matrix [v1,v2]:v1 x v2 = det([v1, v2]),
where the sign represents the positive direction of z-axis determined by right-hand system from
v1 to v2. So det([v1, v2]) >= 0if and only if v1 can be rotated at most 180 degrees counterclockwise to v2.
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;
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])
Update instead of just maintaining the sequential cross product result, any of the two cross product shouldn't multiplies to minus:
def isConvex(self, points):
last, tmp = 0, 0
for i in xrange(2, len(points) + 3):
p0, p1, p2 = points[(i - 2) % len(points)], points[(i - 1) % len(points)], points[i % len(points)]
tmp = (p1[0]-p0[0])*(p2[1]-p0[1])-(p2[0]-p0[0])*(p1[1]-p0[1])
if tmp:
if last * tmp < 0:
return False
last = tmp
return Truehttp://www.cnblogs.com/grandyang/p/6146986.html
就是所有的顶点角都不大于180度。那么我们该如何快速验证这一个特点呢，学过计算机图形学或者是图像处理的课应该对计算法线normal并不陌生吧，计算的curve的法向量是非常重要的手段，一段连续曲线可以离散看成许多离散点组成，而相邻的三个点就是最基本的单位，我们可以算由三个点组成的一小段曲线的法线方向，而凸多边形的每个三个相邻点的法向量方向都应该相同，要么同正，要么同负。那么我们只要遍历每个点，然后取出其周围的两个点计算法线方向，然后跟之前的方向对比，如果不一样，直接返回false。这里我们要特别注意法向量为0的情况，如果某一个点的法向量算出来为0，那么正确的pre就会被覆盖为0，后面再遇到相反的法向就无法检测出来，所以我们对计算出来法向量为0的情况直接跳过即可
bool isConvex(vector<vector<int>>& points) { long long n = points.size(), pre = 0, cur = 0; for (int i = 0; i < n; ++i) { int dx1 = points[(i + 1) % n][0] - points[i][0]; int dx2 = points[(i + 2) % n][0] - points[i][0]; int dy1 = points[(i + 1) % n][1] - points[i][1]; int dy2 = points[(i + 2) % n][1] - points[i][1]; cur = dx1 * dy2 - dx2 * dy1; if (cur != 0) { if (cur * pre < 0) return false; else pre = cur; } } return true; }http://blog.csdn.net/liuchenjane/article/details/53455874
只需按逆时针一次判断一边和一点的关系，若叉积>0，则表示存在大于180的内角，即为凹多边形。
对于任意两点组成的直线，第3点相对于这条直线都有3种关系，在线上，在线的左边，在线的右边。如果一个多边形是凸的，则对于多边形的任意一条边，其他的n-2个点必定都在边的同一侧。
假设有两点A(a[0],a[1])，B(b[0],b[1])，则直线AB的表示：(y-a[1])/(x-a[0])=(b[1]-a[1])/(b[0]-a[0])。对于任意点C(c[0],c[1]),要判断点C相对于直线AB的关系，将x=c[0]带入，y=(b[1]-a[1])/(b[0]-a[0])*(c[0]-a[0])+a[1]；则y-c[1]=(b[1]-a[1])/(b[0]-a[0])*(c[0]-a[0])+a[1]-c[1]；化简，判断符号。如果为正，说明，点C在直线AB的上边，为负在直线的下边，=0表示在直线上。
https://discuss.leetcode.com/topic/70664/c-5-liner-o-n-checking-convexity-with-cross-product-of-adjacent-vectors-detailed-explanation
The key observation for convexity is that vector pi+1-pi always turns to the same direction to pi+2-pi formed by any 3 sequentially adjacent vertices, i.e., cross product (pi+1-pi) x (pi+2-pi) does not change sign when traversing sequentially along polygon vertices.
Note that for any 2D vectors v1, v2,
- v1 x v2 = det([v1, v2])
which is the determinant of 2x2 matrix [v1, v2]. And the sign of det([v1, v2]) represents the positive z-direction of right-hand system from v1 to v2. So det([v1, v2]) ≥ 0 if and only if v1 turns at most 180 degrees counterclockwise to v2.
public boolean isConvex(List<List<Integer>> points) {
// For each set of three adjacent points A, B, C, find the cross product AB · BC. If the sign of
// all the cross products is the same, the angles are all positive or negative (depending on the
// order in which we visit them) so the polygon is convex.
boolean gotNegative = false;
boolean gotPositive = false;
int numPoints = points.size();
int B, C;
for (int A = 0; A < numPoints; A++) {
// Trick to calc the last 3 points: n - 1, 0 and 1.
B = (A + 1) % numPoints;
C = (B + 1) % numPoints;
int crossProduct =
crossProductLength(
points.get(A).get(0), points.get(A).get(1),
points.get(B).get(0), points.get(B).get(1),
points.get(C).get(0), points.get(C).get(1));
if (crossProduct < 0) {
gotNegative = true;
}
else if (crossProduct > 0) {
gotPositive = true;
}
if (gotNegative && gotPositive) return false;
}
// If we got this far, the polygon is convex.
return true;
}
// Return the cross product AB x BC.
// The cross product is a vector perpendicular to AB and BC having length |AB| * |BC| * Sin(theta) and
// with direction given by the right-hand rule. For two vectors in the X-Y plane, the result is a
// vector with X and Y components 0 so the Z component gives the vector's length and direction.
private int crossProductLength(int Ax, int Ay, int Bx, int By, int Cx, int Cy)
{
// Get the vectors' coordinates.
int BAx = Ax - Bx;
int BAy = Ay - By;
int BCx = Cx - Bx;
int BCy = Cy - By;
// Calculate the Z coordinate of the cross product.
return (BAx * BCy - BAy * BCx);
}- public boolean isConvex(List<List<Integer>> points) {
- long prev = 0;
- int n = points.size();
- for(int i = 0; i < n; i++) {
- int[][] m = new int[2][];
- for(int j = 0; j < 2; j++) {
- m[j] = new int[] {points.get((i+j+1)%n).get(0) - points.get(i).get(0),
- points.get((i+j+1)%n).get(1) - points.get(i).get(1)};
- }
- long cur = det(m);
- if (cur * prev < 0) return false;
- prev = cur;
- }
- return true;
- }
- private long det(int[][] m) {
- return m[0][0] * m[1][1] - m[0][1] * m[1][0];
- }
The key observation for convexity is that vector
p[i+1]-p[i] always turns to the same direction to p[i+2]-p[i] formed by any 3 sequentially adjacent vertices, i.e., cross product (p[i+1]-p[i]) x (p[i+2]-p[i]) does not change sign when traversing sequentially along polygon vertices.
Note that for any vectors
v1, v2:v1 x v2 = det([v1, v2]),
which is the determinant of 2*2 matrix
[v1,v2]. And the sign of det([v1, v2]) represents the positive z-direction of right-hand system from v1 to v2. So det([v1, v2]) >= 0 if and only if v1 turns at most 180 degrees counterclockwise to v2.https://en.wikipedia.org/wiki/Complex_polygon
a complex polygon is a polygon which has a boundary comprising discrete circuits, such as a polygon with a hole in it.[2]
Self-intersecting polygons are also sometimes included among the complex polygons.[3] Vertices are only counted at the ends of edges, not where edges intersect in space.
https://en.wikipedia.org/wiki/Right-hand_rule
https://betterexplained.com/articles/cross-product/
