不同方向矩形的并集交集
Intersection over union for rectangles with different orientation
我需要在 swift 中实现一个算法，以找到二维 space 中两个不同方向的矩形之间的交集 (IoU)。我找不到任何教程或示例代码来教授如何实现这种算法。
谁能提供相关资源？
您可以使用O'Rourke algorithm计算两个凸多边形的交集。
C 和 Java 代码在书“Computational Geometry in C”
的页面上可用
算法遍历多边形的边直到找到交点（使用
定向测试）。相交后，它从两个可能的下一个边中选择 "the most inner" 条边来构建相交核心多边形（总是凸的）。
当你排序了顶点列表后，你可以用shoelace formula计算多边形面积。
为了得到并集的面积，我们可以计算（感谢 Yves Daoust 的提示）
Area(Union) = Area(P) + Area(Q) - Area(Intersection)
除了 MBo/O'Rourke 的非常好的解决方案，您还可以使用扫描线方法。
为方便起见，假设其中一个多边形是轴对齐的。然后当线碰到对齐矩形的顶部和底部时有两个 "events" 和当线碰到另一个顶点时有四个事件（根据方向，顶点有 8 种可能的排列）。
矩形的交点出现在这些事件定义的垂直范围内（您执行两个事件集的合并）并且在斜边和水平线之间最多有两个六个交点要计算。对于每条事件线，很容易确定两个矩形跨越的 X 间隔，并找到它们的交集或并集。并且两条事件线之间的区域是梯形。
要处理一般位置的矩形，可以
旋转两个多边形以对齐其中一个，
使用反向旋转坐标系，
在不移动多边形的情况下仍然用水平线执行扫描；但是然后有 8 个事件而不是 6 个和最多 8 个交集计算。
我需要在 swift 中实现一个算法，以找到二维 space 中两个不同方向的矩形之间的交集 (IoU)。我找不到任何教程或示例代码来教授如何实现这种算法。
谁能提供相关资源？
您可以使用O'Rourke algorithm计算两个凸多边形的交集。 C 和 Java 代码在书“Computational Geometry in C”
的页面上可用算法遍历多边形的边直到找到交点（使用 定向测试）。相交后，它从两个可能的下一个边中选择 "the most inner" 条边来构建相交核心多边形（总是凸的）。
当你排序了顶点列表后，你可以用shoelace formula计算多边形面积。
为了得到并集的面积，我们可以计算（感谢 Yves Daoust 的提示）
Area(Union) = Area(P) + Area(Q) - Area(Intersection)
除了 MBo/O'Rourke 的非常好的解决方案，您还可以使用扫描线方法。
为方便起见，假设其中一个多边形是轴对齐的。然后当线碰到对齐矩形的顶部和底部时有两个 "events" 和当线碰到另一个顶点时有四个事件（根据方向，顶点有 8 种可能的排列）。
矩形的交点出现在这些事件定义的垂直范围内（您执行两个事件集的合并）并且在斜边和水平线之间最多有两个六个交点要计算。对于每条事件线，很容易确定两个矩形跨越的 X 间隔，并找到它们的交集或并集。并且两条事件线之间的区域是梯形。
要处理一般位置的矩形，可以
旋转两个多边形以对齐其中一个，
使用反向旋转坐标系，
在不移动多边形的情况下仍然用水平线执行扫描；但是然后有 8 个事件而不是 6 个和最多 8 个交集计算。