math - 如何检查单纯形是否包含原点？

Question

我正在实现 Gilbert-Johnson-Keerthi计算两个对象是否相交(即碰撞)的算法。

我的代码的入口点是 hasCollided接受两个点列表并返回 True 的函数如果它们相交。我相信我已经正确地实现了这篇论文 - 但是，我仍然需要实现 contains功能。
contains函数应确定单纯形是否包含原点。我不确定如何实现这一点。

如何有效地确定单纯形(点集合)是否包含原点？

以下是我的实现:

type Simplex = Set (Vector Double)

hasCollided :: [Vector Double] -> [Vector Double] -> Bool
hasCollided points1 points2 = gjk points1 points2 simplex (scale (-1) direction) p
  where simplex   = insert p empty
        p         = support points1 points2 direction
        direction = fromList [1, 0, 0]

gjk :: [Vector Double] -> [Vector Double] -> Simplex -> Vector Double -> Vector Double -> Bool
gjk points1 points2 simplex direction lastAdded =
  if p <.> direction < 0 then False
  else
    if contains simplex' (fromList [0, 0, 0]) direction p then True
    else gjk points1 points2 simplex' direction' p
  where p          = support points1 points2 direction
        simplex'   = insert p simplex
        direction' = cross ab $ cross ao ab
        ab         = sub p lastAdded
        ao         = sub origin3D lastAdded

辅助函数是:

contains :: Simplex -> Vector Double -> Vector Double -> Vector Double -> Bool
contains simplex point direction lastAdded = undefined


support :: [Vector Double] -> [Vector Double] -> Vector Double -> Vector Double
support points1 points2 direction = sub p1 p2
  where p1 = getFarthestPoint points1 direction
        p2 = getFarthestPoint points2 direction

getFarthestPoint :: [Vector Double] -> Vector Double -> Vector Double
getFarthestPoint points direction = points !! index
  where index       = fromJust $ elemIndex (maximum dotproducts) dotproducts
        dotproducts = map (direction <.>) points

origin3D :: Vector Double
origin3D = fromList [0, 0, 0]

Answer 1

我将采用不聪明的“让我们做一些线性代数来解决它”的方法。

单纯形中的每个点都是 convex combination定义单纯形的点。凸组合只是一个线性组合，其中系数都 >= 0 并且加起来为 1。

“单纯形是否包含原点”等同于询问是否存在等于零向量的单纯形点的凸组合。我们可以把它写成矩阵表达式吗？

假设我们正在使用由四个向量 x1 定义的单纯形。通过x4 .

我们将形成这些向量的任意线性组合，y = a1*x1 + a2*x2 + a3*x3 + a4*x4 .

我们要找a1通过a4这样y是零向量，a1 + a2 + a3 + a4 = 1 .

如果单纯形是三维欧几里得空间中的点，我将展示线性系统会是什么样子；让向量 xi有组件xi1 , xi2 , 和 xi3 .

[ x11  x21  x31  x41 ] [ a1 ]   [ 0 ]
[ x12  x22  x32  x42 ] [ a2 ] = [ 0 ]
[ x13  x23  x33  x43 ] [ a3 ]   [ 0 ]
[  1    1    1    1  ] [ a4 ]   [ 1 ]

该线性系统的前三行对应于 y 的约束。必须为零，即我们可以通过 x1的某种线性组合到达原点通过 x4 .最后一行对应于系数加起来为 1 的约束，这对于线性组合成为凸组合是必要的但不是充分的。矩阵方程没有表达的约束是 ai >= 0 .

选择您最喜欢的求解线性系统的方法并应用它。如果构成单纯形的向量是线性独立的，那么您将找不到任何解。如果线性系统有一个或多个解 和 至少一种解决方案具有所有 ai >= 0 ，则单纯形包含原点。

对于最后一步的算法，我没有任何现成的描述，确定解决方案集是否包含所有系数为正的任何点。我建议在纸上写几个例子——我希望你能找到一个。

编辑:确定解决方案集是否包括所有系数为正的任何点实际上与确定由解决方案空间与 ai >= 0 的交集定义的单纯形是否相同包括除原点以外的任何点。

这意味着这种解决方法减少了

“输入单工 是否包含原点 ？”

至

“另一个单纯形(从输入单纯形派生) 是否包含除原点 以外的任何点？”

我认为这是一个将问题简化为另一个(希望更容易)问题的可爱例子。