如何有效地确定多边形是凸面、非凸面还是复面? [英] 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 可以提高性能.如果您为非凸形路径指定凸形，则图形结果未定义.

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屋！