划分自相交多边形（C代码）

Question

我想将自相交多边形划分为简单的多边形。我将边缘和交点保存在数据结构（连接列表）中。

所以这里是一个例子。我有一个连接列表，包含边的x，y坐标和多边形的交点。根据这个picture中的多边形，它将是::（1） - >（2） - >（3）... - >（7）。我想要做的是获取简单多边形的边（这里是三角形）。在这种情况下:: 1,2,7/3,4,5/5,6,7。

Answer 1

我认为Bentley-Ottman将是你最好的选择。有一个很好的交互式可视化here。另一个很好的描述here。