algorithm - 如何找到哪些折线完全包含给定的折线？

Question

我想找出哪些折线完全包含给定的折线。有一些像 Bentley-ottmann 这样的算法可以找到多段线交点，但我想要那些给定多段线完全属于它们的多段线。我认为用点集表示每条折线，然后删除那些不包含给定折线所有点的集可能会有所帮助。

Answer 1

假设折线是非退化的，要确定多维折线包含，您可以按斜率-y 截距对划分线段并解决几个一维问题。为了解决一维问题，使用扫掠线算法，按排序顺序处理段端点并维护两个标志，一个用于扫掠线是否与容器相交，一个用于扫掠线是否与容器相交。