如何有效地确定多边形是凸面、非凸面还是复杂面? [英] How do I efficiently determine if a polygon is convex, non-convex or complex?

问题描述

来自 XFillPolygon:

• 如果shape是Complex，路径可能会自相交.请注意，路径中的连续重合点不被视为自相交.

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

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

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.

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

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.

I am having performance problems with fill XFillPolygon and, as the man page suggests, the first step I want to take is to specify the correct shape of the polygon. I am currently using Complex to be on the safe side.

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

Is there an efficient algorithm to determine if a polygon (defined by a series of coordinates) is convex, non-convex or complex?

推荐答案

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

You can make things a lot easier than the Gift-Wrapping Algorithm... that's a good answer when you have a set of points w/o any particular boundary and need to find the convex hull.

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

In contrast, consider the case where the polygon is not self-intersecting, and it consists of a set of points in a list where the consecutive points form the boundary. In this case it is much easier to figure out whether a polygon is convex or not (and you don't have to calculate any angles, either):

对于多边形的每对连续边(每个点的三元组)，计算由指向这些点的边按递增顺序定义的向量的叉积的 z 分量.取这些向量的叉积:

For each consecutive pair of edges of the polygon (each triplet of points), compute the z-component of the cross product of the vectors defined by the edges pointing towards the points in increasing order. Take the cross product of these vectors:

 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 分量全部为正或全部为负，则多边形为凸多边形.否则多边形是非凸的.

The polygon is convex if the z-components of the cross products are either all positive or all negative. Otherwise the polygon is nonconvex.

如果有 N 个点，请确保计算 N 个叉积，例如请务必使用三元组 (p[N-2],p[N-1],p[0]) 和 (p[N-1],p[0],p[1]).

If there are N points, make sure you calculate N cross products, e.g. be sure to use the triplets (p[N-2],p[N-1],p[0]) and (p[N-1],p[0],p[1]).

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

If the polygon is self-intersecting, then it fails the technical definition of convexity even if its directed angles are all in the same direction, in which case the above approach would not produce the correct result.

这篇关于如何有效地确定多边形是凸面、非凸面还是复杂面?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！