段-多边形相交 [英] segment-polygon intersection

问题描述

问候，

我想检测一个线段是否仅接触或交叉了一个多边形。

I would like to detect if a segment only 'touches' a polygon or cross it.

人物

解释了我的疑问。如何知道案例A和案例B之间的区别？
请注意，在两种情况下，红线都在两个顶点上交叉多边形，一个顶点与外部相交，另一个顶点与内部相交。我有一个段-段相交算法，但是我不知道如何正确使用它。谢谢您的帮助。

explains my doubt. How to know the difference between cases A and B? Note that in both situations the red line crosses the polygons in two vertices, one touching by outside and other crossing by inside. I have a segment-segment intersection algorithm, but I don't know how to use it properly. Any help is appreciated.

推荐答案

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

I think there might not be any approach much easier than computing the details at a low level. First, you will need robust code to compute the intersection between two segments. This is discussed (with code) here. Once you have the intersection points, you need to compute how the polygon boundary interacts with your segment in the neighborhoods of those intersection points. This is essentially repeated LeftOf( ) computations, using the notation in my book. In your image, the segment passes through vertex b, while the adjacent vertices a and c (in a consecutive sequence (a,b,c)) are both to the same side of b. Therefore, the segment does not penetrate to the interior of the polygon in the neighborhood of b. But if a and c were on opposite sides of the segment, then it must penetrate.

这篇关于段-多边形相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！