填充多边形：缠绕规则的性能VS偶奇规则

Question

有关复杂多边形（即：自相交）。在绕线或奇偶填充规则之间的选择使得在该多边形被填充的方式的差异

但是，对于不相交的多边形是在那里的绕组或偶奇规则填充之间的任何性能差异。我的理解会被implentation具体但其中的算法是用于非复杂多边形更effecient。

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

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 /方案/ X服务器/ MI / mipoly.h？转= HEAD

该算法是这样的：它可以计算轮廓，然后创建跨度对象的边缘之间（这只是一个的x，y坐标和宽度）。如果使用EVENODD规则，如果有更多的交叉跨度的对象将被创建。如果没有问题（例如，当多边形是凸的），那么你就不会因为填充规则相当于在miFillPolygon（主回路中的布尔变量通知运行时的区别，即大部分的代码是两个相同填充规则）。

试图通过优化多边形的轮廓也不会买你很多在通常情况下，除非你知道你的面包含一个很高的数字不必要的点（比如说，你可以摆脱的一半数量以提高性能在通常情况下点）。优化的多边形<10点可能会花费超过它实现。

但再次：这都是基于直觉还是老款的知识。如果你想知道如果与你的结果显示卡驱动程序混乱的错误，你必须让你的手脏，写一个测试，测量每种情况下需要多长时间。有没有办法简单地看它，因为外部因素告诉任何复杂的算法的运行时间：内存分配例程的速度，可用内存量（什么时候交换开始），CPU核心数量就可以使用，有多少其他进程会打你的CPU，最终多边形的屏幕，实现细节和优化，臭虫等上剪裁。