自相交多边形的分划算法
本文关键字：算法 多边形 自相交 | 更新日期: 2023-09-27 17:54:37
首先我知道有类似的问题已经问过了，但它使用不同的结构，并且是在C中(划分自相交多边形(C代码))，我的问题有点不同。
我有自相交多边形的点，它的边，我也能够找到它与自己相交的点使用Bentley-Ottmann算法。
我计划通过编辑交点周围的边来构建非自相交的多边形，但问题是当你有两条相交的边时，你不知道四条边中哪两条在多边形内，哪两条在多边形外。
我可以使用射线交叉算法来解决这个问题，但它太慢了。它的时间复杂度是O(n)对于每个交点我至少要做两次。所以它会非常慢，大约有200k个多边形点。
我的问题是，有没有更快的方法将自交多边形划分为非自交多边形
我需要这个，因为我在做多边形三角剖分。我已经完成了带孔的非自相交多边形的三角剖分的扫描线三角剖分算法。所以我只需要这些多边形的数组作为输入
作为预处理步骤，您可以计算每条边，边的哪一边决定多边形的外部。这比每个交点的O(n)时间要便宜得多。然后，当两条边相交时，您可以确定哪两条线段在外部，哪两条线段在内部。