两张三角形构成的图像叠加后提取生成多边形的方法咨询

现有两张均由三角形构成的图像，二者叠加后会形成新的多边形。已知两张输入图像的所有三角形顶点(x,y)坐标均为精确值，具体三角形顺时针坐标如下（所在矩形宽512像素、高256像素）：

三角形顺时针坐标 [矩形宽512像素，高256像素]

三角形 a1 = [0,0] [512,128] [0,256]
三角形 a2 = [0,0] [512,0] [512,128]
三角形 a3 = [0,256] [512,128] [512,256]

三角形 b1 = [0,0] [200,256] [0,256]
三角形 b2 = [0,0] [150,0] [200,256]
三角形 b3 = [150,0] [512,0] [200,256]
三角形 b4 = [512,0] [512,256] [200,256] 

问：可以通过什么方式确定两张图像叠加后生成的所有多边形？应该直接处理叠加后的结果图像，还是可以通过输入三角形的坐标直接计算得到？ #

回答 #

直接用输入的精确三角形坐标计算是最优解，比处理渲染后的位图靠谱太多，具体说明如下：

为什么不建议处理叠加后的结果图像

你渲染出来的512x256位图只有像素级精度，就算做边缘提取、轮廓拟合，最多只能拿到整像素坐标，和原始的精确几何顶点差远了，还会有抗锯齿、采样偏差导致的轮廓误差，完全没必要走这个弯路。

坐标计算的实现逻辑

这个是计算几何领域的经典需求，叫平面叠加分析，你这个场景下实现起来很简单：

• 把A组3个三角形、B组4个三角形的所有边全部提取出来，两两求交点，所有相交的边在交点处打断成独立的子线段，保证最终所有子线段要么不相交，要么仅在端点相交。
• 用这些端点和子线段构建平面排列，会自动把整个画布切分成一个个互不重叠的封闭面，就是你要的所有叠加多边形。
• 给每个面打标签：看它在不在A的三角形里、在不在B的三角形里，就能区分出A独有的、B独有的、两者重叠的三类区域。

快速落地方法

不用自己手写求交、构建排列的底层逻辑，用现成的计算几何库就行：

• 用Python的话直接调shapely：分别把A、B组的三角形合并成多面几何体，调用交、差、异或接口就能直接输出所有叠加后的多边形，几行代码就能搞定。
• 追求更高精度和性能的话可以用CGAL的2D Arrangement模块，专门处理这类平面几何运算。

内容的提问来源于stack exchange，提问作者Lyrk