重叠分裂三角形

Question

我有一个三角形(红色,下面). (或二维网格的三角形)

如何计算从第一个三角形中减去第二个三角形(绿色)所产生的多边形(并依次镶嵌它们)？

(我正在使用Python,我正在寻找可以采用的方法的解释和伪代码,而不是针对不透明库的建议.(我目前用于gluTess*()对多边形进行曲面细分,但是对如何做的解释我自己的问题很有趣;我迫切的问题实际上是布尔运算本身.)学习和理解解决方案会很令人兴奋.我的三角形总是逆时针缠绕,如果这有任何区别的话.)

Answer 1

让我们来看看一些场景......

情况 1：三角形不重叠（或者它们相切但不重叠）

通过使用多边形内点算法来测试这种情况，以查看其中一个三角形的三个顶点中的任何一个是否位于另一个三角形的内部或之上。

如果我们处于情况 1，则无需执行任何操作。

情况 2：绿色三角形位于红色三角形内部。

通过使用多边形内点算法来测试这种情况，看看所有三个绿色顶点是否都在红色三角形内部。另一种测试方法是查看绿色三角形的 3 条线段中的任何一条是否与红色三角形的 3 条线段中的任何一条相交；使用这样的算法进行相交（此外，您还必须检查以确保多边形内部至少有一个绿色顶点 - 只是为了确保缺少相交线不是因为您实际上遇到了情况 1）。

现在，对于这种情况，从每个绿色顶点到每个红色顶点绘制一条线段（总共 9 条新线段）。如果这些新线段中的任何一个与绿色三角形相交，则将其删除（您可以通过对绿色三角形的每条边使用线段相交方法来检查这一点）。现在，测试剩余的新线段是否彼此相交；如果有任何两条线段相交，则消除一条线段，然后重新测试，直到不再有新的线段彼此相交。

情况3：绿色三角形与红色三角形重叠，绿色三角形的两条边进入红色三角形，也离开红色三角形。

通过检查是否正好有两条绿色边与两条红色边相交来测试这种情况。再次使用线段相交算法。

现在，对于这种情况，从每个交点（绿色边与红色边相交的每个位置）到每个红色顶点绘制一条线段。如果这些线段中的任何一个基本上与红色边缘重复，则将其删除。如果这些新线段中的任何一个与绿色三角形相交，则将其删除（您可以通过对绿色三角形的每条边使用线段相交方法来检查这一点）。现在，测试剩余的新线段是否彼此相交；如果有任何两条线段相交，则消除一条线段，然后重新测试，直到不再有新的线段彼此相交。

情况4：绿色三角形与红色三角形重叠，绿色三角形的两条边都进入红色三角形，但不会将红色三角形从另一边留下。

通过检查是否正好有两条绿色边与一条红色边相交（不一定必须是同一边）来测试这种情况。再次使用线段相交算法。

现在，对于这种情况，从红色三角形内部的绿色顶点（使用多边形内的点算法来确定哪个绿色顶点在三角形内部）到每个红色三角形顶点绘制一条线段。

情况 5：绿色三角形与红色三角形重叠，其中绿色三角形只有一侧进入红色三角形，而同一绿色侧则从红色三角形的不同侧退出。

通过检查是否正好有一条绿色边与两条红色边相交来测试这种情况。再次使用线段相交算法。

现在，对于这种情况，从每个交点（绿色边与红色边相交的每个位置）到每个红色顶点绘制一条线段。如果这些线段中的任何一个基本上与红色边缘重复，则将其删除。如果这些新线段中的任何一个与绿色三角形相交，则将其删除（您可以通过对绿色三角形的每条边使用线段相交方法来检查这一点）。现在，测试剩余的新线段是否彼此相交；如果有任何两条线段相交，则消除一条线段，然后重新测试，直到不再有新的线段彼此相交。

希望此时您已经完成了！