从手册页XFillPolygon

From the man page for XFillPolygon

·如果形状复杂，路径​​可能   自相交。需要注意的是CON-           在路径tiguous重合点不被视为自           交叉点。

· If shape is Complex, the path may self-intersect. Note that con‐ tiguous 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性能问题，并为手册页表明我要采取的第一个步骤是指定多边形的正确的形状（我目前使用复杂，无法在安全方面）。

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).

是否有一个effecient算法来确定一个多边形（由一系列坐标定义）是凸的，非凸形或复杂的

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

推荐答案

请参阅礼品包装算法。

修改： 假设所有的多边形在逆时针顺序，那一刻你的非初始的极角，使左转，你知道这是不是凸的。

Edit: Assuming all your polygons are in counter-clockwise order, the moment your non-initial polar angle makes left turn, you know it's not convex.

您可以看到，如果线段彼此交叉，以找出是否多边形是复杂的（不知道这是最快的方式）。

You could see if the line segments intersect with each other to figure out if the polygon is complex (Not sure if that's the fastest way).