填充多边形：执行缠绕规则与偶数奇数规则

Question

对于复杂的多边形（即：自相交），缠绕或偶奇数填充规则之间的选择会影响多边形的填充方式。

但是对于不相交的多边形，绕组或偶数填充规则之间会有任何性能差异。我知道这将是实现特定的，但哪些算法对于非复杂多边形更有效。

后续问题每种算法的复杂性（即O（what？））是什么。我想知道是否值得摆脱多边形中的某些点（主要是重复或同一行上的重复点）以提高性能。

PS：如果它在所有中，我使用的xlib

PPS：我可以证实这个问题是不是硬件相关的如使用不同的显卡不改变性能

Answer 1

今天，大多数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

该算法的工作原理如下：计算轮廓，然后在边缘之间创建跨度对象（只是x，y坐标和宽度）。如果使用EvenOdd规则，如果有交集，将会创建更多的跨度对象。如果没有（例如，当多边形是凸的时候），那么您将不会注意到运行时差异，因为填充规则在miFillPolygon的主循环中相当于一个布尔变量（即大部分代码对于两者都是相同的填充规则）。

试图通过优化多边形轮廓来提高性能在常见情况下不会给您带来太多的收益，除非您知道您的多边形包含非常多的不必要的点（例如，您可以摆脱一半数量普通情况下的点数）。使用<优化多边形可能会比实现更多的成本。

但是，这一切都是基于直觉或对旧文章的了解。如果你想知道你的gfx卡驱动程序中的错误是否与结果相混淆，你必须弄清楚你的手并编写一个测试每个案例需要多长时间的测试。由于外部因素的缘故，无法仅通过查看它来告诉运行时任何复杂算法：内存分配例程的速度，可用内存量（交换开始时间），可以使用的CPU内核数量，多少其他进程将与CPU对抗，裁剪屏幕上的最终多边形，实现细节和优化，错误等。