polygon_clipping_rs

一个用于计算两个多边形布尔运算（即交集、并集、差集和XOR）的Rust包。

多边形表示

多边形表示为一组“轮廓”。每个轮廓是一个顶点的环。被偶数个轮廓包含的点被视为多边形外部，而被奇数个轮廓包含的点被视为多边形内部。请注意，“多边形”并不完全准确，因为这包括“多边形组”——本质上是不相交的两个完全不同的形状。

无效/不规范的多边形

此实现没有考虑到“不规范”的多边形。在这些情况下的行为是未定义的。一些不规范的多边形包括

• 包含 NaN 或 Infinity 坐标的的多边形。这显然会成问题。
• 包含重叠边的多边形。如果单个多边形包含重叠边，则不清楚边表示什么。换句话说，任何包含重叠边的多边形都可以“重新组织”，使得新多边形中没有重叠边——重叠边从未被需要！

算法

这是对以下论文的实现

Francisco Martínez, Carlos Ogayar, Juan R. Jiménez, Antonio J. Rueda,
A simple algorithm for Boolean operations on polygons,
Advances in Engineering Software,
Volume 64,
2013,
Pages 11-19,
ISSN 0965-9978,
https://doi.org/10.1016/j.advengsoft.2013.04.004.
(https://www.sciencedirect.com/science/article/pii/S0965997813000379)

与原始算法的不同之处

这些是对原始算法的有意更改。

• 论文报告使用指针用于一切。这使得清理变得混乱，而Rust确实不喜欢所有循环引用，原因很明显。此实现使用单独的数据结构将数据分割成我们可以独立修改的块。这可能意味着比论文实现更多的（也许更少）内存使用。然而，此实现使用更少的少量分配——分配是分批进行的。
• 除了结果多边形外，我们还返回结果多边形中每个边的源边。这在源多边形的边有一些“元数据”并且您希望保留在结果多边形中的情况下非常有用。一个例子是，如果每个多边形是一个房间，边是墙壁，但有些边是门。可能需要知道结果多边形中哪些边仍然是门。

原始算法的缺陷

这些是在未来可以解决的实现中的问题。

• 本文描述了使用二叉搜索树实现“扫描线”数据结构。当前的实现使用排序的 Vec，因此某些操作可能会有不同的性能特征。文章还提到，事件可以存储其在扫描线上的位置以避免搜索。
• 此实现未能正确处理轮廓多于两条边在单个顶点相遇的情况。文章简要提到了一个解决方案（尽管不如我希望的那么清晰）。

个人笔记

这篇论文相当巧妙，总体思路相当直观。然而，论文似乎在看似无害的单句中隐藏了关键信息（例如，事件必须首先按非垂直边排序），更重要的是，它让读者去推理算法的细节。这使得我的版本与论文中的伪代码有重大差异时变得困惑。此外，一些标志被描述了，但没有说明如何计算它们，“特殊情况”被当作脚注处理，而不是需要大量时间和工作来重构和理解的算法部分。

好了，我抱怨完了。

许可证

根据 MIT 许可证 许可。