c++ - 复杂多边形的凸分解？

Question

对于我的 2D 物理系统 (box2D) 和 OpenGL，需要将复杂多边形分解为凸多边形。确保模型符合这一点很容易。但是，我还想随着模拟的进行编辑多边形，所以我需要一种动态的方法来将现有的多边形分解成更多仍然凸的多边形。

我希望这张图有助于描述我所追求的:

我的问题是，是否有现有的图书馆可以做到这一点？如果没有，我自己最不容易出错的方法是什么？

(我正在查看 Boost，它同时具有 Geometry 和 Polygon 模块，但文档证明有点太深奥了，我不知道是否可以做我想做的事情。)

Answer 1

我认为 this就是你要找的。

至于找到交点，那只是一个小代数；对于任何两条线段，很容易推导出相应的线('rise over run' 等)，

y = a1*x + b1

y = a2*x + b2

那么交点 (x', y') 是

x' = (b2 - b1) / (a1 - a2)

y' = a1*x' + b1

当然，这是线的交点，要确定线段实际相交，您需要使用 x、y 坐标进行简单的范围检查。