如何从一组线中找到包围点的多边形？

Question

我有一组非相交线,其中一些在顶点连接.我试图找到包含给定点的最小多边形(如果存在).因此,在下面的图像中,在所有线段的列表中,给定红色点,我想只获得蓝色线段.我正在使用Python,但可能适应其他语言的算法; 我不知道这个问题叫什么.

Answer 1

首先,删除具有至少一个空闲端点的所有线段,而不是与任何其他段重合.反复这样做,直到没有这样的段.

现在你有一个很好地细分为多边形区域的飞机.

找到最接近您的点的段.请注意,不是最近的终点,而是最近的段.找出您需要的段的方向(您的点应位于有向段的右侧).转到端点,向右转(即,取出您来自的那个段,逆时针计数).继续前进到下一个终点并向右转,直到再次到达最近的段.

然后,检查多边形是否包含给定点.如果不是,那么你找到了一个"岛屿"; 删除该多边形及其所属的整个连接组件,然后再次选择最近的段重新开始.通过简单的DFS可以找到连接的组件.

这为您提供了顺时针方向的多边形.如果你想逆时针,这通常是软件和文献中的默认"正"方向,从左边的点开始,在每个交叉点左转.

如果给定端点,您可以快速找到与其一起发生的所有段,这肯定会有所帮助.