将凹多边形分割成凸多边形

Question

是否存在简单的算法来将一个凹多边形分割成凸多边形或用三角形表示一个多边形?我知道有一个关于三角测量的维基百科条目，但这并没有真正帮助我。我知道已经有一个关于Stackoverflow的问题，但是这对我不是很有帮助。我将欣赏任何伪代码(或用可理解的编程语言编写的真实代码)将凹多边形分解为凸多边形或三角形。顺便说一句，该算法也应该适用于凸多边形，而不是把它们弄乱。

谢谢你的帮助!

Answer 1

根据评论者的建议，剪耳朵应该是三角测量最直接的方法。为了在实践中加快耳朵的验证过程，可以采用几何网格。

编写健壮和高性能的代码，特别是对于几何问题是非常具有挑战性的。为什么不使用现有的实现，如triangle或CGAL。

为了通过python使用CGAL，可以选择SWIG。