math - 裁剪两个 2D 三角形

Question

我知道有高效的多边形裁剪算法(例如 Maillot、Vatti、Greiner-Hormann)。然而，这些算法适用于任意多边形，尽管它们适合我的情况，但在我看来，对像我这样的简单情况使用这种通用算法是一种矫枉过正。

我有两个 2D 三角形(见下图)，我想将一个三角形夹在另一个三角形上。在网上搜索除了通用的多边形裁剪算法之外没有找到任何东西。

问:是否有专门的算法来剪切两个 2D 三角形？

Answer 1

对于两个凸形状，传统方法只是 Sutherland Cohen，但带有更多或更少的标志。

例如在你的情况下:

• 蓝色A在红色AB之外，但在另外两个红色边缘之内；给它代码 100；
• 蓝色B相同；给它代码 100；
• 蓝色 C 在红色 BC 之外，但在另外两个 BC 之内，因此将其编码为 010。

从A开始:

• 代码非零，输出中不包含蓝色 A；
• 查看边缘蓝色 AB，二进制 AND 非零，因此不考虑输出；
• 蓝色 B 的代码非零，不包含在输出中；
• 将 B 和 C 编码为 0，以便对它们进行异或*。给出 110。因此找到蓝色 BC 与红色边 AB 和 BC 的交点，将它们添加到输出列表中；
• 蓝色 C 的代码非零，不包含在输出中；
• 蓝色 C 和 D 的代码再次表示与 BC 和 AB 相交，因此这样做并添加到输出中。

(* 或 OR 它们；我们已经确定它们没有任何共同点，因此没有区别 - 我认为 XOR 更具有描述性，表明您正在寻找差异)