如何查找多边形内的线段列表

Question

我有一条线和一个多边形。该线可以部分在内部并且部分在多边形之外。该线可以在单点或多点处与多边形相交。线条的实施例被示出为下面

请参考图片。对于水平的红色线，我想获得线段列表。期望的输出是（A-B）（C-D）（E-F），对于垂直线我想要得到线段1-2。

我经历了how to detemine if a line segment is inside of a polygon?等堆栈溢出问题。

但无法获得最优化的算法以获取多边形内的线段列表。

我也通过以下链接 https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm但我的问题是有更多的优化算法来查找多边形内的线段？

Answer 1

我回答的情况是，不允许进行预处理，即您有一条线段（或几条）来处理给定的多边形。多边形是一般的（并且可以带有孔）。

旋转线条使其水平，同时旋转多边形顶点。

然后，如果端点具有不同符号的纵坐标，那么多边形的一侧会与段的支撑线相交。在这种情况下，您可以计算交叉点的位置。

多边形内部的子段由在段端点之间找到的有序交点组成。