段 - 多边形交集

Question

问候,

我想检测一个段是否只"触摸"多边形或交叉它.

图

解释我的怀疑.如何知道案例A和B之间的区别？请注意,在这两种情况下,红线在两个顶点中穿过多边形,一个在外面触摸,另一个在内部交叉.我有一个段段交叉算法,但我不知道如何正确使用它.任何帮助表示赞赏.

Answer 1

我认为可能没有比在低级别计算细节更容易的方法了。首先，您需要强大的代码来计算两个段之间的交集。这在这里讨论（用代码）。获得交点后，您需要计算多边形边界如何与这些交点附近的线段相互作用。这基本上是重复LeftOf( )计算，使用我书中的符号。在您的图像中，该段通过顶点b，而相邻的顶点a和c （在连续序列中 ( a,b,c )）都在b的同一侧. 因此，该线段不会穿透到b附近的多边形内部。但是如果a和c 位于线段的两侧，那么它必须穿透。