将2d游戏地图的tile组成/拆分为凸多边形给 box2d?

Question

有这几种形状的地图贴片

想要把它们组成多个有洞的多边形, 切分成多个凸多边形或者三角形

(因为 box2d 处理两个线段组成的一个平面时容易在边的贴合处让角色走路发生磕碰, 所以要做合并, 而且 box2d 只能用凸多边形)

请问有什么现成的库或算法可以抄的吗? (用的 js, 其它语言我就想办法抄一下)
搜了老久只找到地理地图用的可以对多边形作布尔合并的库, 但没找到如何将有洞的多边形拆分为凸多边形或三角形

Answer 1

Martinez-Rueda polygon clipping algorithm -> 多边形的布尔操作, 可以合并成有洞的多边形
earcut (Triangulation by Ear Clipping) -> 把任意多边形拆成三角形

最后找了这两个

如果不需要加物理粒子效果也可以用 edge shape 而不用 polygon shape, 用 edge 拼起来很简单