假设您已经有一条直线的方程（在二维平面内），以及一个由多条直线组成的凸多边形（多边形可能是无界的）。如何判断这条直线是否与多边形相交呢？
此外，是否有计算几何库可以预定义此类任务？我提问是因为我对n维几何问题也感兴趣。
此外，是否有计算几何库可以预定义此类任务？我提问是因为我对n维几何问题也感兴趣。
4个回答
2
对于二维情况，我认为问题会简化一些。
直线将空间分成两个区域。
如果多边形只存在于这些区域中的一个，那么该直线不与其相交。
如果多边形同时存在于这两个区域中，则该直线与其相交。
所以：
取任何垂直于直线的线，使其与直线相交于原点。
将多面体的每个顶点投影到垂线上。
如果这些投影具有两个符号，则多边形与直线相交。
[根据elexhobby的评论进行更新。]
忘记包含处理无界情况的内容。
我的意思是可以创建一个“虚拟顶点”来代表开放区域。我们真正需要的是开放区域的“方向”。我们可以将其作为开放区域边界的向量的平均值。
然后，我们将该方向与法向量的点积视为顶点投影集合的一部分。
直线将空间分成两个区域。
如果多边形只存在于这些区域中的一个，那么该直线不与其相交。
如果多边形同时存在于这两个区域中，则该直线与其相交。
所以：
取任何垂直于直线的线，使其与直线相交于原点。
将多面体的每个顶点投影到垂线上。
如果这些投影具有两个符号，则多边形与直线相交。
[根据elexhobby的评论进行更新。]
忘记包含处理无界情况的内容。
我的意思是可以创建一个“虚拟顶点”来代表开放区域。我们真正需要的是开放区域的“方向”。我们可以将其作为开放区域边界的向量的平均值。
然后，我们将该方向与法向量的点积视为顶点投影集合的一部分。
- Keith
2
1嗯，其实并不是这样吧？左侧的图示中所有顶点与法向量的点积都具有相同的符号，但它们却与多面体相交。 - undefined
@elexhobby。谢谢 - 很对，我确实有考虑到这一点，然后忘记包括它了。请看编辑。 - undefined
0
让我们从有限多边形开始。
要求交点，线必须与其边之一相交。仅当两个点位于线的不同侧时，线与边之间才可能存在交点。
可以通过对边的两个点执行 sign(cross_product(Ep-Lp,Ld)) 进行简单检查。其中Ep 是边上的点，Lp 是线上的某个点，Ld 是线的方向向量，cross_product(A,B)=Ax*By-Ay*Bx。
为了处理无限多边形，我们可以引入 "无穷远点"。如果我们有一个半无限边，具有点 E1 和方向 Ed，它的 "第二个点" 可以表示为 E1+infinity*Ed，其中 infinity 是 "足够大的数字"。
cross_product(Ep-Lp,Ld)=
=cross_product(E1+infinity*Ed-Lp,Ld)=
=cross_product(E1-Lp+infinity*Ed,Ld)=
=cross_product(E1-Lp,Ld)+cross_product(infinity*Ed,Ld)=
=cross_product(E1-Lp,Ld)+infinity*cross_product(Ed,Ld)
如果cross_product(Ed,Ld)为零（直线与边平行），则符号由第一个分量决定。否则第二个分量将主导并确定符号。
- maxim1000
0
在几何学中，通常一个多边形是有界的（参见维基百科）。你所描述的通常被称为多面体或多面体图形（参见维基百科）。
有一些可用的几何库，其中两个我想到的是boost（多边形）和CGAL。通常，处理2D、3D和N-D的计算方法有明显的区别，这是显而易见的。
对于你的问题，我会使用一种二进制空间分割树的方法。我会取出你的“poly”的第一行，并将查询线与它进行修剪，创建一条射线。该射线将从两条线的交点开始，并沿着由“poly”的第一条线生成的半空间的内部方向前进。现在，我会使用射线和“poly”的第二条线重复该过程。（这可能会生成一个线段而不是射线）如果在某个时刻，射线（或现在的线段）起点位于当前考虑的多边形线的外侧并且不与其相交，则答案是否定的——该线不与你的“poly”相交。否则，它相交了。要特别注意各种平行边缘情况。非常简单直接，适用于多维情况。
有一些可用的几何库，其中两个我想到的是boost（多边形）和CGAL。通常，处理2D、3D和N-D的计算方法有明显的区别，这是显而易见的。
对于你的问题，我会使用一种二进制空间分割树的方法。我会取出你的“poly”的第一行，并将查询线与它进行修剪，创建一条射线。该射线将从两条线的交点开始，并沿着由“poly”的第一条线生成的半空间的内部方向前进。现在，我会使用射线和“poly”的第二条线重复该过程。（这可能会生成一个线段而不是射线）如果在某个时刻，射线（或现在的线段）起点位于当前考虑的多边形线的外侧并且不与其相交，则答案是否定的——该线不与你的“poly”相交。否则，它相交了。要特别注意各种平行边缘情况。非常简单直接，适用于多维情况。
- Nicko Po
0
我不完全确定，但我猜你可以通过使用对偶性来解决这个问题。首先将你的线性方程标准化为a.x+b.y=1，并考虑点集(a,b)。
这些点必须构成一个凸多边形，我猜新的直线可能不对应多边形内部的一个点。可以通过验证新点是否在所有边的同一侧来轻松检查这一点。（如果你不知道线的顺序，首先构造凸包。）
- user1196549
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接