如何确定多边形是复杂的/凸的/非凸的？
从XFillPolygon的手册页
·如果形状是复杂的，path可以自相交。 请注意，path中的重合点不被视为自交。
·如果形状为凸，则对于多边形内的每对点，连接它们的线段不会与path相交。 如果客户知道，指定凸面可以提高性能。 如果将凸指定为非凸的path，则graphics结果是不确定的。
·如果形状为非凸，path不自相交，但形状不是完全凸的。 如果客户端知道，指定Nonconvex而不是Complex可能会提高性能。 如果您为自相交path指定Nonconvex，则graphics结果未定义。
我遇到了填充XFillPolygon性能问题，因为手册页build议我要采取的第一步是指定Polygon的正确形状（我目前正在使用Complex来保证安全）。
是否有一个有效的algorithm来确定多边形（由一系列坐标定义）是凸的，非凸的还是复杂的？
请参阅礼品包装algorithm ：
假设所有的多边形都是逆时针顺序的，那么当你的非初始极angular左转时，就知道它不是凸的。
你可以看到线段是否相互交叉，以确定多边形是否复杂（但我不确定这是否是最快的方法）。
你可以使事情比礼物包装algorithm容易得多…当一组点没有任何特定的边界并且需要find凸包时，这是一个很好的答案。
多边形是连续点形成边界的列表中的一组点。 确定一个多边形是否凸起（而且不必计算任何angular度）要容易得多：
对于多边形的每一对连续边（每个点的三个点），计算由指向点的边的递增顺序的vector叉积的z分量。 取这些vector的交叉乘积：
given p[k], p[k+1], p[k+2] each with coordinates x, y: dx1 = x[k+1]-x[k] dy1 = y[k+1]-y[k] dx2 = x[k+2]-x[k+1] dy2 = y[k+2]-y[k+1] zcrossproduct = dx1*dy2 - dy1*dx2
如果交叉积的z分量全部为正或全为负，则多边形是凸的。 否则多边形是非凸的。
如果有N个点，确保计算N个交叉积，例如确保使用三元组（p [N-2]，p [N-1]，p [0]）和（p [N-1] p [0]，p [1]）。
我已经在JAVA中实现了JasonS的解决scheme。
也许这会有所帮助
public boolean isConvex() { if (_vertices.size() < 4) return true; boolean sign = false; int n = _vertices.size(); for(int i=0; i<n; i++) { double dx1 = _vertices.get((i+2)%n).X-_vertices.get((i+1)%n).X; double dy1 = _vertices.get((i+2)%n).Y-_vertices.get((i+1)%n).Y; double dx2 = _vertices.get(i).X-_vertices.get((i+1)%n).X; double dy2 = _vertices.get(i).Y-_vertices.get((i+1)%n).Y; double zcrossproduct = dx1*dy2 - dy1*dx2; if (i == 0) sign = zcrossproduct > 0; else if (sign != (zcrossproduct > 0)) return false; } return true; }
凸是相当容易testing的：考虑沿着多边形的每一组三个点。 如果每个angular度是180度或更less，你有一个凸多边形。 这个testing运行在O（n）时间。
还要注意，在大多数情况下，这个计算是你可以做一次和保存的东西 – 大多数情况下你有一组多边形来处理，而这些多边形不会一直在改变。
有关您的数据的更多信息可能会有帮助。
编辑：彼得Kirkham指出一个多边形，这个testing不会赶上。 抓住他的多边形也很容易：当你计算出每个angular度时，还要保持（180°angular）的总计。 对于凸多边形，这将总共360。
为了testing一个多边形是否是凸的，多边形的每一点应该与每一行的水平相同或相同。
这是一个示例图片：
当您search“确定凸多边形”时，此问题现在是Bing或Google中的第一个项目。 但是，没有一个答案是好的。
@EugeneYokota接受的答案是通过检查一组无序的点是否可以制成一个凸多边形，但这不是OP所要求的。 他要求一种方法来检查给定的多边形是否凸起。 （计算机科学中的“多边形”通常被定义为（如在XFillPolygon文档中 ）作为2D点的有序arrays，连续点与边连接以及最后一点连接）。另外，礼品包装algorithm在这种情况下，对于n个点将具有O(n^2)的时间复杂度 – 这比解决这个问题实际需要的大得多，而问题要求有效的algorithm。
@ JasonS的回答 ，以及其他答案跟随他的想法，接受星形多边形 ，如五angular星形或@ zenna评论中的星形多边形，但星形多边形不被认为是凸的。 正如@plasmacel在评论中所指出的那样，如果您事先知道多边形不是自相交的，那么这是一个很好的使用方法，但是如果您不具备这些知识，则可能会失败。
Sekhat的答案是正确的，但它也具有O(n^2)的时间复杂性，因此是低效的。
@ LorenPechtel在她编辑之后添加的答案在这里是最好的，但是它是含糊的。
具有最佳复杂度的正确algorithm
我在这里提出的algorithm具有O(n)的时间复杂度，正确地testing一个多边形是否凸起，并通过了我所有的testing。 这个想法是遍历多边形的边，注意每边的方向和连续边之间方向符号的变化。 这里的“签名”表示左侧为正，右侧为负（或相反），直线前为零。 这些angular度被标准化为在-π（独占）和pi（含）之间。 添加这些方向改变angular度将导致凸多边形的正或负一圈，而星形多边形将具有不同的总和。 我们还检查方向转换angular度是全部为正还是全为负，而不是反转（pi弧度），所有点都是实际的2D点，并且没有连续的顶点是相同的。 这些检查的组合捕获所有凸多边形和非多边形多边形。
这里是Python 3的代码，它实现了algorithm，并包含一些小的效率。 代码看起来比实际上更长，这是由于注释行和簿记涉及避免重复的点访问。
TWO_PI = 2 * pi def is_convex_polygon(polygon): """Return True if the polynomial defined by the sequence of 2D points is 'strictly convex': points are valid, side lengths non- zero, interior angles are strictly between zero and a straight angle, and the polygon does not intersect itself. NOTES: 1. Algorithm: the signed changes of the direction angles from one side to the next side must be all positive or all negative, and their sum must equal plus-or-minus one full turn (2 pi radians). Also check for too few, invalid, or repeated points. 2. No check is explicitly done for zero internal angles (180 degree direction-change angle) as this is covered in other ways, including the `n < 3` check. """ try: # needed for any bad points or direction changes # Check for too few points if len(polygon) < 3: return False # Get starting information old_x, old_y = polygon[-2] new_x, new_y = polygon[-1] new_direction = atan2(new_y - old_y, new_x - old_x) angle_sum = 0.0 # Check each point (the side ending there, its angle) and accum. angles for ndx, newpoint in enumerate(polygon): # Update point coordinates and side directions, check side length old_x, old_y, old_direction = new_x, new_y, new_direction new_x, new_y = newpoint new_direction = atan2(new_y - old_y, new_x - old_x) if old_x == new_x and old_y == new_y: return False # repeated consecutive points # Calculate & check the normalized direction-change angle angle = new_direction - old_direction if angle <= -pi: angle += TWO_PI # make it in half-open interval (-Pi, Pi] elif angle > pi: angle -= TWO_PI if ndx == 0: # if first time through loop, initialize orientation if angle == 0.0: return False orientation = 1.0 if angle > 0.0 else -1.0 else: # if other time through loop, check orientation is stable if orientation * angle <= 0.0: # not both pos. or both neg. return False # Accumulate the direction-change angle angle_sum += angle # Check that the total number of full turns is plus-or-minus 1 return abs(round(angle_sum / TWO_PI)) == 1 except (ArithmeticError, TypeError, ValueError): return False # any exception means not a proper convex polygon
对于顶点数组：
vertices = [(0,0),(1,0),(1,1),(0,1)]
下面的python实现检查所有交叉产品的z分量是否具有相同的符号
def zCrossProduct(a,b,c): return (a[0]-b[0])*(b[1]-c[1])-(a[1]-b[1])*(b[0]-c[0]) def isConvex(vertices): if len(vertices)<4: return True signs= [zCrossProduct(a,b,c)>0 for a,b,c in zip(vertices[2:],vertices[1:],vertices)] return all(signs) or not any(signs)
将Uri的代码改写成matlab。 希望这可能有帮助。
% M [ x1 x2 x3 ... % y1 y2 y3 ...] % test if a polygon is convex function ret = isConvex(M) N = size(M,2); if (N<4) ret = 1; return; end x0 = M(1, 1:end); x1 = [x0(2:end), x0(1)]; x2 = [x0(3:end), x0(1:2)]; y0 = M(2, 1:end); y1 = [y0(2:end), y0(1)]; y2 = [y0(3:end), y0(1:2)]; dx1 = x2 - x1; dy1 = y2 - y1; dx2 = x0 - x1; dy2 = y0 - y1; zcrossproduct = dx1 .* dy2 - dy1 .* dx2; % equality allows two consecutive edges to be parallel t1 = sum(zcrossproduct >= 0); t2 = sum(zcrossproduct <= 0); ret = t1 == N || t2 == N; end
