复杂多边形的凸分解？

Question

使用我的2D物理系统(box2D)和OpenGL,conplex多边形需要分解为凸多边形.确保模型符合这一点很容易.但是,我还想在模拟过程中编辑多边形,因此我需要一种动态方法将现有多边形压缩成更多仍然凸起的多边形.

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

我的问题是,是否有现成的图书馆可以实现这一目标？如果没有,那么自己最不容易出错的方法是什么？

(我正在浏览Boost,它有一个Geometry和一个Polygon模块,但是文档证明有点太深奥了,我不知道是否可以做我想要的.)

Answer 1

我想这就是你要找的。

至于求交点，那只是一点代数而已；对于任意两条线段，很容易得出相应的线（“上升超过运行”等），

y = a1*x + b1

y = a2*x + b2

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

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

y' = a1*x' + b1

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