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

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

我会采取非聪明的,"让我们做一些线性代数来解决它"的方法.

单形内的每个点都是定义单形的点的凸组合.凸组合只是一个线性组合,其中系数都> = 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包括除原点之外的任何点相同.

这意味着这种解决方案可以减少问题

" 输入单形 是否包含原点？"

至

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

我认为这是将问题减少到另一个(希望更容易)问题的一个可爱的例子.

Answer 2

要严格确定该点是否位于单形或否定中,您只需要知道最大尺寸d + 2决定因素的迹象d * d.

让:

然后我们可以构造一个矩阵(j,k索引意味着:从每个剩余的行中排除j行和从中减去向量k的d行; 从行中的所有左侧定义一个位于j顶点的小平面):

但我们可以注意到

所以我们只能从比较的左手边计算一个决定因素(?):

并假设,该标志翻转为下一个js.

因此,应以计算至少2的决定因素d*d矩阵,和最大d + 2(的^1,1和A的^Ĵ,0对所有j在{1,2,...,d + 1}).如果符号在某个步骤上不匹配,则该点在单形的当前面之外,从而完全不在单面中.

额外:

如果右侧的一些决定因素为零,则该点与相应小平面的平面共面.