线段-多边形相交
您好，
我想检测一个线段是否仅“接触”多边形或与其交叉。
图
解释了我的疑问。如何知道情况A和B的区别？ 请注意，在这两种情况下，红线在两个顶点处穿过多边形，一个顶点与外部相接触，另一个顶点与内部相交。我有一个段-段相交算法，但我不知道如何正确使用它。任何帮助表示赞赏。
Greetings,
I would like to detect if a segment only 'touches' a polygon or cross it.
The Figure
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为可能没有比在低级别计算细节更容易的方法了。
首先，您需要强大的代码来计算两个线段之间的交集。
此处对此进行了讨论（通过代码）。一旦有了交点，你需要
计算多边形边界如何与这些区域的邻域中的线段相互作用
交叉点。这本质上是
使用我书中的符号重复
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.
一般来说，交叉点可能包含许多点。例如，请参阅 http://cagd.cs.byu.edu/~557 /text/ch7.pdf 其中讨论了平面曲线如何相交，并表示切线曲线在“正确计数”的两个点处相交，这是违反直觉的。对于具有掠射线的凸多边形，交点是否有“正确计数”的两个点？在你的例子中，是否有两个交点，每个交点有两个点？
因此，O'Rourke 教授给出了一种计算交点点数的算法。实际上，用于计算交叉点的包是否应该返回每个交叉点的点数？
Generalizing, an intersection may comprise many points. For example, see http://cagd.cs.byu.edu/~557/text/ch7.pdf which discusses how planar curves intersect, and says tangent curves intersect at two points "properly counted", which is counter-intuitive. In the case of a convex polygon with a grazing line, does the intersection have two points "properly counted?" In your case, are there two intersections with two points each?
So Prof. O'Rourke gives an algorithm for computing the number of points in the intersection, so to speak. Pragmatically, should a package for computing intersections return the count of points in each intersection?