如何有效地确定多边形是凸的,非凸的还是复杂的？

从手册页XFillPolygon:

如果shape是复杂的,则路径可以自相交.请注意,路径中的连续重合点不会被视为自相交.

如果shape是Convex,对于多边形内的每对点,连接它们的线段不与路径相交.如果客户端知道,指定Convex可以提高性能.如果为非凸的路径指定Convex,则图形结果未定义.

如果shape是Nonconvex,则路径不会自相交,但形状不是完全凸的.如果客户端知道,指定Nonconvex而不是Complex可以提高性能.如果为自相交路径指定Nonconvex,则图形结果未定义.

我遇到填充性能问题XFillPolygon,正如手册页所示,我想要采取的第一步是指定多边形的正确形状.我目前正在使用Complex来保证安全.

是否有一种有效的算法来确定多边形(由一系列坐标定义)是凸的,非凸的还是复杂的？

1> Jason S..：

---

你可以比礼品包装算法容易得多......当你有一组没有任何特定边界的点并且需要找到凸包时,这是一个很好的答案.

相反,考虑多边形不是自相交的情况,它由列表中的一组点组成,其中连续点形成边界.在这种情况下,更容易确定多边形是否是凸的(并且您也不必计算任何角度):

对于多边形的每个连续边对(每个点的三元组),计算由按指令递增顺序指向点的边所定义的向量的叉积的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]).

---

如果多边形是自相交的,那么即使其定向角度都在同一方向上,它也不符合凸性的技术定义,在这种情况下,上述方法不会产生正确的结果.

---

如果我错了,请纠正我,但是对于一些复杂的多边形,这不会失败吗？例如[[1 3] [9 7] [7 9] [7 2] [9 6] [1 8]]]

---

所有这些赞成票的答案都非常错误.[自相交循环](https://imgur.com/a/fuRxo)将以优异的颜色传递此算法.

---

我已经更新了这个答案。评论者是正确的，因为它不能解决复杂的情况，但仍然有价值。

2> Rory Daulton..：

---

当您搜索"确定凸多边形"时,此问题现在是Bing或Google中的第一个项目.但是,没有一个答案是足够好的.

在通过@EugeneYokota接受的答案工作通过检查一组无序的点是否可以做成凸多边形,但是这不是什么OP要求.他要求一种方法来检查给定的多边形是否凸起.(计算机科学中的"多边形"通常被定义为[在XFillPolygon文档中 ]作为2D点的有序数组,连续点与边连接,最后一点连接到第一点.)此外,礼品包装算法在这种情况下会有的时间复杂度O(n^2)为n分-这是远远大于实际需要来解决这个问题,而问题问的一个高效的算法.

@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

---

度,总共

---

@plasmacel:像JasonS的回答一样,这种方法接受星形多边形,例如五角星形或zenna评论中的那些.如果星形多边形是可以接受的,那确实比我的方法更好,但是星形多边形通常不被认为是凸的.这就是我花时间编写和测试拒绝星形多边形的函数的原因.另外,感谢您的编辑 - 它确实改善了我的答案.但是,你确实改变了一个句子的含义,所以我再次编辑它 - 我希望这次更清楚.

3> Uri Goren..：

---

以下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;
}

只要顶点是有序的(顺时针或逆时针),算法就可以保证工作,并且你没有自相交的边(即它只适用于简单的多边形).

4> Loren Pechte..：

---

这是检查多边形是否为凸面的测试。

考虑沿多边形的每组三个点。如果每个角度都等于或小于180度，则您有一个凸多边形。弄清楚每个角度时，请同时保持总计（180-角度）。对于凸多边形，总计为360。

该测试运行时间为O（n）。

另请注意，在大多数情况下，此计算只需执行一次即可保存，在大多数情况下，要使用一组多边形，这些多边形不会一直保持不变。