如何测试线是否与凸多边形相交? [英] 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屋！