重叠分割三角形

Question

我有一个三角形（红色，下面）。 （或二维三角网格）

如何计算从第一个三角形（绿色）减去第二个三角形（绿色）后得到的多边形（并依次镶嵌它们）？

（我使用Python和我在寻找一种方法，我可以拿，而不是不透明库建议的说明和伪码。（我目前使用gluTess*()做镶嵌的多边形，但是如何自己做tesselltation的解释会很有趣;我的紧迫问题实际上是布尔运算本身）。学习和理解解决方案将会很令人兴奋，我的三角形总是逆时针缠绕，如果使任何差异。）

Answer 1

让我们通过一些场景...

案例1：三角形不重叠（或者相切但不重叠）

试验这种情况下使用point-in-polygon algorithm看如果其中一个三角形的三个顶点中的任何一个位于另一个的内部或上面。

如果我们在案例1中，我们不需要做任何事情。

案例2：绿色三角形在红色三角形内。通过使用点的多边形算法要么

测试针对这种情况，看看是否所有三个绿色的顶点是红色三角形内部。另一种测试方法是查看绿色三角形的三条线段是否与红色三角形的三条线段中的任何一条相交。使用类似于algorithm的交点（此外，还必须检查以确保多边形内至少有一个绿色顶点 - 以确保缺少相交线不是因为实际上正在运行到案例1中）。

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

案例3：绿色三角形重叠红三角，绿色的三角形的两条边进入红色三角形，也留下了红色三角形。

测试针对这种情况通过检查恰好两个绿色边的每一相交的两个红色的两侧。再次使用线段交点算法。

现在，对于这种情况，从每个交点（每个绿侧与红侧相交的位置）绘制一条线段到每个红顶点。如果这些线段中的任何一条基本上都重复了红色边线，则将其移除。如果这些新线段中的任何一个交叉到绿色三角形中，则将其移除（可以通过针对每个绿色三角形的边使用线段交叉点方法来检查它）。现在，测试是否有任何剩余的新线段相互交叉;如果有任何两个线段相互交叉，则删除一个，然后重新测试，直到您没有更多的新线段相互交叉为止。

案例4：绿色三角形重叠红三角，绿色的三角形的两条边进入红色三角形，但他们不离开红三角了另一边。

测试针对这种情况通过检查恰好两个绿色边的每一相交恰好与一个红方（它并不一定是每个同一侧）。再次使用线段交点算法。

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

案例5：绿色三角形重叠红色三角形，其中绿色三角形的仅一侧进入红色三角形，并且其中相同的绿色侧离开红色三角形的不同侧。

测试针对这种情况通过检查恰好一个果岭边正好用两个红色的边相交。再次使用线段交点算法。

现在，对于这种情况，从每个交点（每个绿侧与红侧相交的位置）绘制一条线段到每个红顶点。如果这些线段中的任何一条基本上都重复了红色边线，则将其移除。如果这些新线段中的任何一个交叉到绿色三角形中，则将其移除（可以通过针对每个绿色三角形的边使用线段交叉点方法来检查它）。现在，测试是否有任何剩余的新线段相互交叉;如果有任何两个线段相互交叉，则删除一个，然后重新测试，直到您没有更多的新线段相互交叉为止。

并希望在这一点上你做！

Answer 2

这个问题的第一个步骤将是隔离红色三角形之后留下的区域你把绿色的三角形放在它上面。一旦你有了这些不同的形状（在上面的例子中，一个4面的形状和一个3面的形状），你将从“需要计算”列表中删除所有的形状（因为它们已经是三角形） 。

接下来，你应该留下一个单一的形状或没有形状（你可以只有一个或两个形状重叠一个三角形之后），但真的，如果你想要一个更一般的方法，你可以申请这适用于你留下的所有形状（在三角形之后）。现在隔离每个形状的顶点，并顺时针或逆时针给它们一个顺序。从顶点1开始，然后转到顶点1 + 2并尝试绘制一条线以生成三角形（检查边界问题，例如在原始三角形的边界之外画一条线）。如果遇到边界问题，请向上移动并尝试下一个顶点，尝试绘制一条线到顶点1 + 3。重点是你跳过最邻近的顶点，然后在紧接着的顶点之后画一条线，然后尝试所有的顶点，直到重新找到邻接点。按照定义，您正在构建三角形（因为它们必须使用此方法有三面）。

一旦你产生三角（通过成功地吸引来自一个顶点到另一个线）将被重新计算，你必须拆分成三角形，并重复上述过程，该地区的其余部分，直到你只剩下三角形。

这里有一个（诚然可怕）gif动画我做了该方法：

Answer 3

也许是愚蠢的做法，但它是晚，我的大脑在10个小时的工作后，过载：

1. 将所有三角形合并成一个多边形（有可能的孔）。
2. 三角形多边形。
3. 对于每个得到的三角形检查其是否属于仅到红色三角形。合并和三角多边形的

实施例：

实施例当所述三角形中的一个是完全内部另一：

三角测量时，特技将重用来自任何点完全封闭三角形。您还将拥有一系列代表现有三角形边和“软”线（绘制虚线）的“硬”线（绘制的实线），您必须通过三角测量确定线。

我肯定有这样做的更好的方法，但你去那里...

Answer 4

我敢肯定，你可以找到通用多边形减法，裁剪和可应用三角测量算法，但因为你仅限于三角形，所以适用更简单的方法。

基本方法是延长第二个（绿色）三角形的边缘，将它们视为无数行，然后将原始（红色）三角形分成三次，每个与红色三角形相交的绿色边缘一次，保持红色三角形之外的部分。算法：

resultSet := {} // set of triangles 
currentPoly := originalTriangle 
for each edge E of secondTriangle: 
    if E intersects currentPoly (*): 
     Extend edge E to line L 
     Split currentPoly by L into outerPoly and otherPoly (**) 
     // outerPoly is on the side corresponding to the outside 
     // of secondTriangle (right side if going CCW) 
     resultSet += triangulatation of outerPoly (***) 
     currentPoly := otherPoly 
if resultSet is empty: 
    resultSet := originalTriangle // no intersections 

(*)的线段如果段相交的任何多边形边的交叉的多边形，或者如果它完全包含在该多边形。对于这种算法，最好将重合线视为不相交（因为不会发生分割）。

(**)算法由线

result := [[],[]] // two empty lists of points 
intersectionCount = 0 
for each point P in the polygon: 
    // each point is added to one of the result polygons 
    result[intersectionCount % 2] += P 
    E := edge between P and the next point Q 
    if E intersects L at R: 
     // each intersection point is added to both result polygons 
     if R is not equal to P: 
      result[intersectionCount % 2] += R 
     intersectionCount += 1 
     if R is not equal to Q: 
      result[intersectionCount % 2] += R 

(***) outerPoly分割成凸多边形将始终是一个三角形或四边形，因此琐碎进行三角测量。