algorithm - 如何有效地确定多边形是凸面、非凸面还是复杂面？

Question

来自 XFillPolygon 的手册页:

• If shape is Complex, the path may self-intersect. Note that contiguous coincident points in the path are not treated as self-intersection.

• If shape is Convex, for every pair of points inside the polygon, the line segment connecting them does not intersect the path. If known by the client, specifying Convex can improve performance. If you specify Convex for a path that is not convex, the graphics results are undefined.

• If shape is Nonconvex, the path does not self-intersect, but the shape is not wholly convex. If known by the client, specifying Nonconvex instead of Complex may improve performance. If you specify Nonconvex for a self-intersecting path, the graphics results are undefined.

我在填充 XFillPolygon 时遇到了性能问题，正如手册页所建议的那样，我要采取的第一步是指定多边形的正确形状。为了安全起见，我目前正在使用Complex。

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

Answer 1

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

相比之下，考虑多边形不是自相交的情况，它由列表中的一组点组成，其中连续的点构成边界。在这种情况下，确定多边形是否为凸面要容易得多(而且您也不必计算任何角度):

对于多边形的每对连续边(每个点的三元组)，计算由指向这些点的边以递增顺序定义的向量叉积的 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])。

---

如果多边形是自相交的，则 it fails the technical definition of convexity即使它的定向角都在同一方向，在这种情况下，上述方法也不会产生正确的结果。