hha*_*fez 3 algorithm performance raster xlib
对于复杂的多边形（即：自相交），“缠绕”或“偶数-奇数”填充规则之间的选择会影响多边形的填充方式。
但对于不相交的多边形，“缠绕”或“偶奇”填充规则之间是否存在性能差异。我知道这将是特定于实现的，但哪种算法对于非复杂多边形更有效。
后续问题是每个算法的复杂度是多少（即 O(what?) ）。我想知道是否值得删除多边形中的某些点（主要是重复的点或位于同一行的点）以提高性能。
PS：如果重要的话，我正在使用 xlib
PPS：我可以确认问题与硬件无关，因为使用不同的显卡不会改变性能
如今，大多数 X 实现都使用显卡的 2D 硬件，因此两者之间的差异可能可以忽略不计。
由于这是一个性能问题，所以我的答案正确的可能性约为 10%（对于性能，如果不进行测量，你有 90% 的机会出错）。如果你想确定的话，没有办法，只能写一个小的性能测试来亲自看看。
x11perf可能会有所帮助。
您可以在此处找到与硬件无关的多边形填充的算法：http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c ?rev=HEAD
如果您确定多边形是凸的，还有第二个版本，它的速度要快得多：http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c ?rev=HEAD
第二个版本忽略填充规则（不适用于凸多边形）。关于该算法的评论：http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipoly.h ?rev=HEAD
该算法的工作方式如下：它计算轮廓，然后在边缘之间创建跨度对象（只是 ax、y 坐标和宽度）。如果使用 EvenOdd 规则，如果存在交叉点，将会创建更多跨度对象。如果没有（例如，当多边形是凸的时），那么您将不会注意到运行时差异，因为填充规则相当于 miFillPolygon 的主循环中的布尔变量（即，两者的大部分代码是相同的）填写规则）。
在常见情况下，尝试通过优化多边形轮廓来提高性能不会给您带来太多好处，除非您知道多边形包含大量不必要的点（例如，您可以删除多边形中一半的点）常见情况）。优化少于 10 个点的多边形的成本可能会超过其实现的效果。
但再次强调：这都是基于直觉或旧文章的知识。如果您想知道 gfx 卡驱动程序中的错误是否会影响结果，您必须亲自动手并编写一个测试来测量每种情况所需的时间。由于外部因素，无法通过简单地查看来判断任何复杂算法的运行时间：内存分配例程的速度、可用内存量（何时开始交换）、可以使用的 CPU 核心数、多少个其他进程会与你争夺 CPU、屏幕上最终多边形的裁剪、实现细节和优化、错误等。