boost - 从相交的线串计算有界多边形

我正在使用 boost 几何，我正在尝试从相交的折线（Boost 几何中的线串 2d）计算“有界”多边形（见下图）。目前，我的方法是i）获取这些线之间的所有交点，然后ii）在交点处“分割”每条线。然而，这个算法有点详尽。有谁知道 boost geometry 是否有更有效的方法？

此外，如何获得位于两个交点之间的每个线串的线段（或点向量）？例如，对于绿色线串，如果我有两个红色交点，如何获得这两个点之间的线串（包含两个红色交点和两个内部蓝色点的点向量）？boost几何中是否有任何类似“拆分”的功能？

任何建议都非常感谢。提前非常感谢。

标签： boostcomputational-geometryboost-geometry

从给定的描述来看，（多）线似乎成对相交以形成单个环，因此内部多边形被很好地定义。如果这不是真的，则解决方案不是唯一的。

由于线的数量很少，对成对交点的详尽搜索不会是一个大罪。对于 5 条（多段）线，有 10 对要尝试，而您预计有 5 个交叉点。从十字路口形成环路并不是什么大问题。

最重要的是 Boost Geometry 是否使用有效的算法与折线相交。不确定这是否记录在案。对于中等数量的顶点（比如低于 100），这并不重要。

如果点的数量确实很大，您可以求助于有效的线段相交算法，它将复杂度从 O(n²+k) 降低到 O((n+k) log n)。请参阅https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm。您可以一次性处理所有折线。

如果您的折线具有特定属性，则可以利用它们来简化任务。