填充多边形：缠绕规则与偶奇规则的性能
对于复杂的多边形（即：自相交），“缠绕”或“偶数-奇数”填充规则之间的选择会影响多边形的填充方式。
但对于不相交的多边形，“缠绕”或“偶奇”填充规则之间是否存在性能差异。 我知道这将是特定于实现的，但哪种算法对于非复杂多边形更有效。
后续问题是每个算法的复杂度是多少（即 O(what?) ）。 我想知道是否值得删除多边形中的某些点（主要是重复的点或位于同一行的点）以提高性能。
PS：如果有的话，我正在使用 xlib
PPS：我可以确认问题与硬件无关，因为使用不同的显卡不会改变性能
For a complex polygon (ie: self intersecting) the choice between the Winding or the Even-Odd filling rules makes a difference in the way the polygon is filled.
But for non intersecting polygons is there any performance difference between the Winding or the Even Odd filling rules. I understand it would be implentation specific but which of the algorithms is more effecient for non complex polygons.
A follow up question what is the complexity (ie O(what?) )of each of these algorithms. I want to know whether it is worth getting rid of some points in the polygon (mainly duplicates or ones that are on the same line) to improve performance.
PS: If it matters at all, I am using xlib
PPS: I can confirm the problem is not hardware related as using a different graphics card doesn't change the performance
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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
该算法的工作方式如下：它计算轮廓，然后创建跨度对象（只是 ax,y 坐标和 a宽度）之间的边缘。 如果使用 EvenOdd 规则，如果存在交叉点，将会创建更多跨度对象。 如果没有（例如，当多边形是凸的时），那么您将不会注意到运行时差异，因为填充规则相当于 miFillPolygon 的主循环中的布尔变量（即，两者的大部分代码是相同的）填写规则）。
在常见情况下，尝试通过优化多边形轮廓来提高性能不会给您带来太多好处，除非您知道多边形包含大量不必要的点（例如，您可以删除多边形中一半的点）常见情况）。 使用 < 优化多边形 10 分的成本可能会超过它所达到的效果。
但再次强调：这都是基于直觉或旧文章的知识。 如果您想知道 gfx 卡驱动程序中的错误是否会影响结果，您必须亲自动手并编写一个测试来测量每种情况所需的时间。 由于外部因素，无法通过简单地查看来判断任何复杂算法的运行时间：内存分配例程的速度、可用内存量（交换何时开始）、可以使用的 CPU 核心数、有多少个其他进程会与你争夺 CPU、屏幕上最终多边形的裁剪、实现细节和优化、错误等。
Today, most implementations of X use the 2D hardware of your graphics card so the difference between the two is probably negligible.
Since this is a performance question, chances of my answer being correct is about 10%, though (with performance, you have a 90% chance to be wrong without measuring). If you want to be sure, there is no way but to write a small performance test and see for yourself.
x11perf might help.
You can find the algorithm for the hardware independent polygon fill here: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD
There is a second version which is much faster if you are sure your polygon is convex: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD
The second version ignores the fill rule (which doesn't apply to convex polygons). Comments about the algorithm: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipoly.h?rev=HEAD
The algorithm works this way: It calculates the outline, then creates span objects (which are just a x,y coordinate and a width) between the edges. If you use the EvenOdd rule, more span objects will be created if there are intersections. If there are none (for example, when the polygon is convex), then you will not notice a runtime difference because the filling rule amounts to a boolean variable in the main loop of the miFillPolygon (i.e. most of the code is the same for both fill rules).
Trying to improve performance by optimizing the outline of the polygon will not buy you much in the common case except if you know that your polygons contain a very high number of unnecessary points (say, you can get rid of half the number of points in the common case). Optimizing a polygon with < 10 points will probably cost more than it achieves.
But again: This are all based on gut feeling or the knowledge of an old article. If you want to know if bugs in your gfx card driver mess with the result, you have to get your hands dirty and write a test which measures how long each case takes. There is no way to tell the runtime of any complex algorithm by simply looking at it because of external factors: Speed of the memory allocation routines, amount of free memory (when does swapping start), number of CPU cores you can use, how many other processes will fight you for the CPU, clipping of the final polygon on the screen, implementation details and optimizations, bugs, etc.