假设你得到了一条线的方程（在 2d 中），以及形成凸多边形的线方程（多边形可以是无界的）。如何确定线是否与多边形相交？
此外，是否有预定义此类任务的计算几何库？我问是因为我不仅对 2D 版本感兴趣，而且对 n 维几何感兴趣。
问问题
2185 次
4 回答
1
对于 2D 情况，我认为问题简化了一点。
这条线将空间分成两个区域。
如果多边形仅存在于其中一个区域中，则该线不会与其相交。
如果多边形存在于两个区域中，则该线与它相交。
所以：
取任何垂直线，使与线的交点为原点。
将多面体的每个顶点投影到垂线上。
如果这些投影同时出现两个符号，则多边形与线相交。
[在 elexhobby 的评论之后更新。]
忘了包括无界案例的处理。
我的意思是补充一点，可以创建一个“虚拟顶点”来表示开放区域。我们真正需要的是开放区域的“方向”。我们可以将其作为开放区域边界的向量的平均值。
然后，我们用法线处理该方向的点积，并将其添加到顶点投影集。
于 2015-04-17T04:27:29.807 回答
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)为零（线平行于边缘），则符号将由第一个分量确定。否则，第二个分量将占主导地位并确定符号。
于 2015-04-17T09:53:50.250 回答
0
在几何中，通常参见维基百科，多边形是有界的。您所描述的通常称为多面体或多面体，请参阅维基百科
有几个可用的几何库，我想到的两个是 boost（多边形）和 CGAL。通常，出于显而易见的原因，处理 2d、3d 和 Nd 的计算方法之间存在明显的差异。
对于您的问题，我会使用某种二进制空间分区树方法。我会取你的“poly”的第一行并修剪查询线，创建一条射线。光线将从两条线的交点开始，并沿“多边形”的第一条线生成的半空间内部的方向前进。现在我将使用射线和“多边形”的第二行重复该过程。（这可能会生成一个线段而不是射线）如果在某个点射线（或现在的线段）原点位于当前考虑的折线的外侧并且不相交，那么答案是否定的 - 线不相交你的“聚”。否则相交。特别注意各种平行边缘情况。相当直截了当，适用于多维案例。
于 2015-04-17T00:22:52.123 回答
0
我不完全确定，但我想你可以通过使用对偶来解决这个问题。首先将您的线方程归一化为a.x+b.y=1，并考虑点集(a,b)。
这些必须形成一个凸多边形，我的猜测是新线可能与多边形内的一个点不对应。这很容易通过验证新点是否在所有边的同一侧来检查。（如果你不知道线的顺序，首先构造凸包。）
于 2015-04-17T08:09:11.713 回答