如何测试一条线是否与凸多边形相交? [英] How to test if a line intersects a convex polygon?

问题描述

假设给定了一条线的方程(在 2d 中)，以及形成凸多边形的线方程(多边形可能是无界的).如何确定线是否与多边形相交?

Assume you are given the equation of a line (in 2d), and the equations of lines that form a convex polygon (the polygon could be unbounded). How do I determine if the line intersects the polygon?

此外，是否有预定义此类任务的计算几何库?我这么问是因为我不仅对 2D 版本感兴趣，而且对 n 维几何感兴趣.

Furthermore, are there computational geometry libraries where such tasks are pre-defined? I ask because I'm interested not just in the 2D version but n-dimensional geometry.

推荐答案

对于 2D 的情况，我认为问题稍微简化了一些.

For the 2D case, I think the problem simplifies a bit.

这条线将空间分成两个区域.

The line partitions the space into two regions.

如果多边形仅出现在其中一个区域中，则该线不会与它相交.

If the polygon is present in only one of those regions, then the line does not intersect it.

如果多边形在两个区域都存在，那么这条线确实与它相交.

If the polygon is present in both regions, then the line does intersect it.

所以:

取任何垂直于该线的线，使其与线相交线原点.

Take any perpendicular to the line, making the intersection with the line the origin.

将多面体的每个顶点投影到垂直线上.

Project each vertex of the polytope onto the perpendicular.

如果这些投影同时出现，那么多边形与线相交.

If those projections occur with both signs, then the polygon intersects the line.

[根据 elexhobby 的评论更新.]

[Update following elexhobby's comment.]

忘记包括无界案例的处理.

Forgot to include the handling of the unbounded case.

我想补充一点，可以创建一个虚拟顶点"来表示开放区域.我们真正需要的是开放区域的方向".我们可以把它作为开放区域边界的向量的平均值.

I meant to add that one could create a "virtual vertex" to represent the open area. What we really need is the "direction" of the open area. We can take this as the mean of the vectors for the bounding edges of the open area.

然后我们用法线处理该方向的点积，并将其添加到顶点投影集中.

We then treat the dot product of that direction with the normal and add that to the set of vertex projections.

这篇关于如何测试一条线是否与凸多边形相交?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！