从手册页XFillPolygon：
如果
shape是Complex，路径可能会自相交。请注意，路径中的连续重合点不会被视为自相交。如果
shape是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 文档中] 为 2D 点的有序数组，连续点与边相连，最后一个点与第一个点相连。）此外，礼品包装算法在这种情况下，将具有O(n^2)forn点的时间复杂度 - 这比解决此问题的实际需要大得多，而问题要求一种有效的算法。
@JasonS 的答案以及遵循他的想法的其他答案，接受五角星形或@zenna 评论中的星形多边形，但星形多边形不被认为是凸的。正如@plasmacel 在评论中指出的那样，如果您事先知道多边形不是自相交的，这是一种很好的方法，但如果您没有该知识，它可能会失败。
@Sekhat 的答案是正确的，但它也具有时间复杂性O(n^2)，因此效率低下。
@LorenPechtel在编辑后添加的答案是这里最好的答案，但它含糊不清。
具有最佳复杂度的正确算法
我在这里介绍的算法的时间复杂度为O(n)，正确地测试了一个多边形是否是凸的，并且通过了我对其进行的所有测试。这个想法是遍历多边形的边，注意每边的方向和连续边之间方向的有符号变化。这里的“有符号”表示向左为正，向右为负（或相反），正前方为零。这些角度被归一化为负 pi（不包括）和 pi（包括）之间。将所有这些方向变化角（也称为偏转角）加在一起将导致正负一圈（即360度）对于凸多边形，而星状多边形（或自相交环）将具有不同的总和（n * 360度，对于n整体转，对于所有偏转角具有相同符号的多边形） . 所以我们必须检查方向改变角度的总和是正负一圈。我们还检查方向变化角度是否全部为正或全部为负且不反转（pi 弧度），所有点都是实际的 2D 点，并且没有连续的顶点是相同的。（最后一点值得商榷——您可能希望允许重复顶点，但我更喜欢禁止它们。）这些检查的组合捕获所有凸多边形和非凸多边形。
这是 Python 3 的代码，它实现了该算法并包括一些次要的效率。由于注释行和避免重复点访问所涉及的簿记，代码看起来比实际更长。
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
以下 Java 函数/方法是此答案中描述的算法的实现。
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;
}
只要顶点是有序的（顺时针或逆时针），并且您没有自相交的边（即它仅适用于简单的多边形），该算法就可以保证工作。
这是一个检查多边形是否为凸的测试。
考虑沿多边形的每组三个点——一个顶点、之前的顶点、之后的顶点。如果每个角度都是 180 度或更小，则您有一个凸多边形。当你计算出每个角度时，还要保持（180 - 角度）的运行总数。对于凸多边形，总计 360。
该测试在 O(n) 时间内运行。
另请注意，在大多数情况下，您可以执行一次并保存此计算 - 大多数情况下，您有一组多边形可供使用，这些多边形不会一直变化。
要测试多边形是否凸面，多边形的每个点都应该与每条线齐平或位于每条线后面。
这是一个示例图片：
假设顶点是有序的（顺时针或逆时针），此方法适用于简单的多边形（没有自相交的边）
对于顶点数组：
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)
@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)) )
第二个断言在原始答案中失败。应该是？对于我的用例，我希望它没有。
我实现了这两种算法：@UriGoren 发布的一种算法（有一点改进 - 仅整数数学）和@RoryDaulton 用Java 发布的一种算法。我遇到了一些问题，因为我的多边形是封闭的，所以两种算法都认为第二个是凹的，而它是凸的。所以我改变了它以防止这种情况。我的方法还使用基本索引（可以是或不是 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;
}
将 Uri 的代码改编成 matlab。希望这可能会有所帮助。
请注意，Uri 的算法仅适用于 简单的多边形！所以，一定要先测试多边形是否简单！
% 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