来自XFillPolygon的手册描述：
如果
shape为Complex，路径可能会自相交。请注意，路径中连续重合点不被视为自相交。如果
shape为Convex，对于多边形内的每对点，连接它们的线段不会与路径相交。如果客户端已知，请指定Convex以提高性能。如果您为非凸多边形指定Convex，图形结果未定义。如果
shape为Nonconvex，路径不自相交，但形状不完全是凸的。如果客户端已知，请指定Nonconvex而不是Complex以提高性能。如果您为自相交路径指定Nonconvex，图形结果未定义。
我在使用填充XFillPolygon时遇到了性能问题，正如手册所建议的那样，我想采取的第一步是指定正确的多边形形状。目前我正在安全起见使用Complex。
有没有一种有效的算法来确定由一系列坐标定义的多边形是凸的、非凸的还是复杂的？
与礼品包装算法相比，你可以使用更简单的方法来解决问题... 当你有一组没有特定边界的点集需要找到凸包时，礼品包装算法是一个很好的答案。
相反，考虑多边形不自交且由一系列点组成的情况，其中连续的点构成了边界。在这种情况下，要确定多边形是否是凸多边形要容易得多（而且你也不必计算任何角度）：
对于多边形的每一对相邻边缘（每个三元组点），计算由指向越来越大的点的边界定义的向量的叉积的 z 分量。取这些向量的叉积：
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])。
如果多边形自相交，那么即使其方向角都朝一个方向，也会不符合凸性的技术定义，在这种情况下，上述方法将不会产生正确的结果。
当搜索“确定凸多边形”时，此问题现在是Bing或Google中的第一项。然而，没有一个答案足够好。
(现已删除的) EugeneYokota用户的回答 通过检查无序点集是否可以组成凸多边形来工作，但这不是OP所要求的。他要求一种方法来检查给定的多边形是否是凸多边形。（在计算机科学中，“多边形”通常被定义为XFillPolygon文档中所述的有序二维点数组，其中连续的点与一条边连接，并将最后一个点与第一个点连接）。此外，在这种情况下，包裹礼物算法的时间复杂度对于n个点为O(n^2) - 这比实际需要解决这个问题要大得多，而问题要求一种高效的算法。
@JasonS的答案，以及其他支持他想法的答案，接受星形多边形，例如五角星或@zenna评论中的那个，但是星形多边形不被认为是凸多边形。正如@plasmacel在评论中指出的那样，如果您事先知道多边形不会自相交，则这是一种好的方法，但如果您没有这种知识，则可能失败。
@Sekhat的答案是正确的，但它也具有O(n^2)的时间复杂度，因此效率低下。
@LorenPechtel添加的答案在她的编辑后是这里最好的答案，但它比较模糊。
一个正确的算法，具有最优复杂度
我在这里介绍的算法时间复杂度为O(n)，可以正确地测试多边形是否凸多边形，并通过我提出的所有测试。其思想是遍历多边形的各个边，记下每条边的方向以及相邻两条边的方向变化。这里的“带符号”表示向左为正，向右为负（或反之），直线为零。这些角度经过归一化后，值在开区间-π和闭区间π之间。将所有这些方向变化角（也称为偏转角）累加在一起，对于凸多边形而言结果是正负一次旋转（即360度），而星形多边形（或自交环）将有不同的总和（对于所有偏转角具有相同符号的多边形，总和为n * 360度，其中n表示多边形的总旋转次数）。因此，我们必须检查方向变化角的总和是否为正负一次旋转。我们还检查方向变化角是否全部为正数或全部为负数而且没有取反（π弧度），所有点都是实际的二维点，并且没有连续的顶点是相同的。（最后一个点有争议——您可能允许重复的顶点，但我更喜欢禁止它们。）这些检查的组合可以捕获所有凸多边形和非凸多边形。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
atan2()函数运行较慢。如果需要，我也可以提供Python的实现作为比较。 - Nominal Animalpublic 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;
}
只要顶点有序（顺时针或逆时针），并且没有自相交的边（即仅适用于简单多边形），该算法就能保证运行。
这是一个检查多边形是否凸多边形的测试。
考虑多边形上每组三个点——当前顶点，前一个顶点和后一个顶点。如果每个角度都小于等于180度，则该多边形是凸多边形。在计算每个角度时，还需要保持（180-角度）的总和。对于凸多边形，这个总和应该是360。
此测试的时间复杂度为O(n)。
请注意，在大多数情况下，这个计算只需要进行一次并保存结果即可——大多数时候，您需要处理的是一组不经常变化的多边形。
2）中的多面体：对于凸多边形（2-多面体），当选择每个面（线）时（绿色），所有其他未被选择的面（线）的顶点都在所选面（线）的法向量（蓝色箭头）的同一水平或后面，即从不在其前面。 - linker这种方法适用于简单的多边形（没有自相交的边），假设顶点已经被排序（顺时针或逆时针）。
对于一个顶点数组：
vertices = [(0,0),(1,0),(1,1),(0,1)]
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)
对我来说，RoryDaulton的回答是最好的，但如果其中一个角度恰好为0怎么办？一些人可能希望这种边缘情况返回True，在这种情况下，请将“<=”更改为“<”：
if orientation * angle < 0.0: # not both pos. or both neg.
# A square
assert is_convex_polygon( ((0,0), (1,0), (1,1), (0,1)) )
# This LOOKS like a square, but it has an extra point on one of the edges.
assert is_convex_polygon( ((0,0), (0.5,0), (1,0), (1,1), (0,1)) )
if ndx == 0 .. else 更改为 if not np.isclose(angle, 0.): # only check if direction actually changed if orientation is None: orientation = np.sign(angle) elif orientation != np.sign(angle): return False，这样也可以适用于您的边缘情况。在循环之前添加 orientation = None。 - ElRudi我实现了两种算法：一种是@UriGoren发布的（只使用整数计算，做了一些小改进），另一种是@RoryDaulton的。我用Java编写了这些算法。由于我的多边形是闭合的，所以这两个算法都认为第二个角是凹的，而实际上它是凸的。因此，我进行了修改以避免这种情况。我的方法还使用了一个基础索引（可以是0或非0值）。
以下是我的测试顶点：
// concave
int []x = {0,100,200,200,100,0,0};
int []y = {50,0,50,200,50,200,50};
// convex
int []x = {0,100,200,100,0,0};
int []y = {50,0,50,200,200,50};
现在，让我们来谈谈算法：
private boolean isConvex1(int[] x, int[] y, int base, int n) // Rory Daulton
{
final double TWO_PI = 2 * Math.PI;
// 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.
// needed for any bad points or direction changes
// Check for too few points
if (n <= 3) return true;
if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex
n--;
// Get starting information
int old_x = x[n-2], old_y = y[n-2];
int new_x = x[n-1], new_y = y[n-1];
double new_direction = Math.atan2(new_y - old_y, new_x - old_x), old_direction;
double angle_sum = 0.0, orientation=0;
// Check each point (the side ending there, its angle) and accum. angles for ndx, newpoint in enumerate(polygon):
for (int i = 0; i < n; i++)
{
// Update point coordinates and side directions, check side length
old_x = new_x; old_y = new_y; old_direction = new_direction;
int p = base++;
new_x = x[p]; new_y = y[p];
new_direction = Math.atan2(new_y - old_y, new_x - old_x);
if (old_x == new_x && old_y == new_y)
return false; // repeated consecutive points
// Calculate & check the normalized direction-change angle
double angle = new_direction - old_direction;
if (angle <= -Math.PI)
angle += TWO_PI; // make it in half-open interval (-Pi, Pi]
else if (angle > Math.PI)
angle -= TWO_PI;
if (i == 0) // if first time through loop, initialize orientation
{
if (angle == 0.0) return false;
orientation = angle > 0 ? 1 : -1;
}
else // if other time through loop, check orientation is stable
if (orientation * angle <= 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 Math.abs(Math.round(angle_sum / TWO_PI)) == 1;
}
现在来自Uri Goren的最新消息
private boolean isConvex2(int[] x, int[] y, int base, int n)
{
if (n < 4)
return true;
boolean sign = false;
if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex
n--;
for(int p=0; p < n; p++)
{
int i = base++;
int i1 = i+1; if (i1 >= n) i1 = base + i1-n;
int i2 = i+2; if (i2 >= n) i2 = base + i2-n;
int dx1 = x[i1] - x[i];
int dy1 = y[i1] - y[i];
int dx2 = x[i2] - x[i1];
int dy2 = y[i2] - y[i1];
int crossproduct = dx1*dy2 - dy1*dx2;
if (i == base)
sign = crossproduct > 0;
else
if (sign != (crossproduct > 0))
return false;
}
return true;
}
a、b 得到的向量框架必须是点凸的，否则该多边形就是凹的。
例如，在下面的每种情况下，线段 a、b 对于点 p 来说都是凸的，在上方，即： p 存在于 a、b 内部，在下方，即： p 存在于 a、b 外部时，它们对于点 p 来说都是凹的。
同样地，在下面的每个多边形中，如果构成尖锐边缘的每一对直线对于重心 c 都是 点凸 的，则该多边形是凸的，否则它是凹的。
钝边（绿色）应该被忽略
注意：
这种方法需要您事先计算多边形的重心，因为它不使用角度而是使用向量代数/变换。
atan2()或类似的函数，这些函数通常很慢。为了测试性能，我将Rory的代码移植到C++并与Graphics Gems的代码进行了时间比较。我使用1000个随机生成的具有3到8个边的多边形进行了测试。结果显示，Graphics Gems的代码速度是Rory的代码的4倍。我的测试是在Visual Studio 2013上进行的，目标是x64，运行在Intel i3-6100u上。/*
* C code from the article
* "Testing the Convexity of a Polygon"
* by Peter Schorn and Frederick Fisher,
* (schorn@inf.ethz.ch, fred@kpc.com)
* in "Graphics Gems IV", Academic Press, 1994
*/
/* Reasonably Optimized Routine to Classify a Polygon's Shape */
typedef enum { NotConvex, NotConvexDegenerate,
ConvexDegenerate, ConvexCCW, ConvexCW } PolygonClass;
typedef double Number; /* float or double */
#define ConvexCompare(delta) \
( (delta[0] > 0) ? -1 : /* x coord diff, second pt > first pt */\
(delta[0] < 0) ? 1 : /* x coord diff, second pt < first pt */\
(delta[1] > 0) ? -1 : /* x coord same, second pt > first pt */\
(delta[1] < 0) ? 1 : /* x coord same, second pt > first pt */\
0 ) /* second pt equals first point */
#define ConvexGetPointDelta(delta, pprev, pcur ) \
/* Given a previous point 'pprev', read a new point into 'pcur' */ \
/* and return delta in 'delta'. */ \
pcur = pVert[iread++]; \
delta[0] = pcur[0] - pprev[0]; \
delta[1] = pcur[1] - pprev[1]; \
#define ConvexCross(p, q) p[0] * q[1] - p[1] * q[0];
#define ConvexCheckTriple \
if ( (thisDir = ConvexCompare(dcur)) == -curDir ) { \
++dirChanges; \
/* The following line will optimize for polygons that are */ \
/* not convex because of classification condition 4, */ \
/* otherwise, this will only slow down the classification. */ \
/* if ( dirChanges > 2 ) return NotConvex; */ \
} \
curDir = thisDir; \
cross = ConvexCross(dprev, dcur); \
if ( cross > 0 ) { if ( angleSign == -1 ) return NotConvex; \
angleSign = 1; \
} \
else if (cross < 0) { if (angleSign == 1) return NotConvex; \
angleSign = -1; \
} \
pSecond = pThird; /* Remember ptr to current point. */ \
dprev[0] = dcur[0]; /* Remember current delta. */ \
dprev[1] = dcur[1]; \
int classifyPolygon2(int nvert, Number pVert[][2])
/* Determine polygon type. return one of:
* NotConvex, NotConvexDegenerate,
* ConvexCCW, ConvexCW, ConvexDegenerate
*/
{
int curDir, thisDir, dirChanges = 0,
angleSign = 0, iread ;
Number *pSecond, *pThird, *pSaveSecond, dprev[2], dcur[2], cross;
/* if ( nvert <= 0 ) return error; if you care */
/* Get different point, return if less than 3 diff points. */
if ( nvert < 3 ) return ConvexDegenerate;
iread = 1;
while ( 1 ) {
ConvexGetPointDelta( dprev, pVert[0], pSecond );
if ( dprev[0] || dprev[1] ) break;
/* Check if out of points. Check here to avoid slowing down cases
* without repeated points.
*/
if ( iread >= nvert ) return ConvexDegenerate;
}
pSaveSecond = pSecond;
curDir = ConvexCompare(dprev); /* Find initial direction */
while ( iread < nvert ) {
/* Get different point, break if no more points */
ConvexGetPointDelta(dcur, pSecond, pThird );
if ( dcur[0] == 0.0 && dcur[1] == 0.0 ) continue;
ConvexCheckTriple; /* Check current three points */
}
/* Must check for direction changes from last vertex back to first */
pThird = pVert[0]; /* Prepare for 'ConvexCheckTriple' */
dcur[0] = pThird[0] - pSecond[0];
dcur[1] = pThird[1] - pSecond[1];
if ( ConvexCompare(dcur) ) {
ConvexCheckTriple;
}
/* and check for direction changes back to second vertex */
dcur[0] = pSaveSecond[0] - pSecond[0];
dcur[1] = pSaveSecond[1] - pSecond[1];
ConvexCheckTriple; /* Don't care about 'pThird' now */
/* Decide on polygon type given accumulated status */
if ( dirChanges > 2 )
return angleSign ? NotConvex : NotConvexDegenerate;
if ( angleSign > 0 ) return ConvexCCW;
if ( angleSign < 0 ) return ConvexCW;
return ConvexDegenerate;
}