从相交的线串计算有界面
从相交的线串计算有界面
提问于 2019-07-15 16:45:06
我正在使用boost几何，并且我正在尝试从相交的折线( Boost几何中的线串2d )计算一个“有界”多边形(见下图)。目前，我的方法是i)获得这些线之间的所有交点，然后ii)在交点处“分割”每条线。然而，这个算法有点详尽。有没有人知道boost geometry对此有没有更有效的方法？
此外，如何才能获得与两个交点相交的每个线串的线段(或点的向量)？例如，对于绿色线串，如果我有两个红色交点，我如何获得这两个点之间的线串(包含两个红色交点和两个内部蓝点的点的矢量)？boost几何图形中有没有什么“拆分”-like的功能？
任何建议都是非常感谢的。在此之前非常感谢。
回答 1
Stack Overflow用户
发布于 2019-07-16 18:11:00
从给定的描述中，似乎(多边形)线成对相交以形成单个循环，因此内部多边形被很好地定义。如果这不是真的，则解决方案不是唯一的。
由于线的数量很少，对两两相交的穷尽搜索将不会是一个大错。对于5条(多边形)线，有10对要尝试，而您期望的是5个交叉点。从交叉口形成环路并不是什么大问题。
最重要的是Boost Geometry是否使用有效的算法来相交多段线。不确定这是否记录在案。对于中等数量的顶点(例如低于100)，这并不那么重要。
如果点的数量真的很大，您可以求助于一种有效的线段求交算法，该算法将复杂度从O(n²+k)降低到O((n+k) log )。参见https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm。可以一次处理所有多段线。
如果多段线具有特定特性，则可以利用这些特性来简化任务。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/57036171
复制相关文章
相似问题
腾讯云开发者
