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

问题描述

从 的手册页，如果<$ c $>
$ b < c> shape 为 Complex ，则路径可能会自相交。如果 shape 是 凸，对于多边形内的每对点，连接它们的线段不会与路径相交。如果客户端知道，指定凸面可以提高性能。如果您为非凸的路径指定凸面，则图形结果未定义。 形状是 Nonconvex ，路径不会自相交，但形状不是完全凸的。如果客户端知道，指定 Nonconvex 而不是复杂可能会提高性能。如果为自相交路径指定 Nonconvex ，则图形结果未定义。
$ b

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

有没有一种有效的算法来确定一个多边形（由一系列坐标）是凸的，非凸的还是复杂的？注意：计算一组点的凸包是完全不必要的如果您只想确定表示多边形的点列表是否表示凸多边形。

---

请参阅礼品包装算法：

假设所有的多边形都是逆时针顺序的，非初始极角向左转，你知道它不是凸的。

你可以看到线段是否相互交叉以确定多边形是否复杂（但我不确定这是否是fa最简单的方式）。

From the man page for 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.

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?

解决方案

NOTE: computing the convex hull of a set of points is completely unnecessary if you just want to determine if a list of points representing a polygon represents a convex polygon.

---

See Gift Wrapping Algorithm:

Assuming all your polygons are in counter-clockwise order, the moment your non-initial polar angle makes a 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 (but I'm not sure if that's the fastest way).

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