如何检查单纯形是否包含原点? [英] How do I check if a simplex contains the origin?

问题描述

我正在实现 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]

解决方案

要严格确定该点是否在单纯形中，您只需要知道最大d + 2行列式的符号即可.d * d大小. /p>

让我们

然后我们可以构造一个矩阵(j,k索引意味着:排除j行，并从其余d行中的每行中减去从原点到点k的向量；行中的所有左手边都定义了一个构面相对于j顶点):

上述矩阵的行列式是d!乘以d定向的超体积，由公式中涉及的点构成(严格地说，是平行六面体的定向超体积，其边由矩阵行给出).

如果点在单纯形内，则以下所有等式均成立(将j和0点对相对于构面的方向(指向超体积的符号匹配):

但是我们可以注意到，

所以我们只能从比较的左手边(?)计算一个行列式:

并假设该符号在下一个j时翻转.

因此，我们应该至少计算d*d个矩阵的行列式和最大d + 2(A ^1,1 和A ^{j，0 j的sup>).如果某个步骤上的符号不匹配，则该点位于单形的当前构面之外，从而根本不在单形之外.}

附加:

如果某些右侧行列式为零，则该点与相应小平面的平面共面.

I am implementing the Gilbert-Johnson-Keerthi algorithm which computes whether two objects are intersecting (ie. colliding).

The entry point to my code is the hasCollided function which takes two lists of points and returns True if they are intersecting. I believe I have implemented the paper correctly - however, I still have to implement the contains function.

The contains function should determine whether a simplex contains the origin. I am unsure as to how to implement this.

How do I efficiently determine if a simplex (collection of points) contains the origin?

---

The following is my implementation:

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

The helper functions are:

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]

解决方案

To strictly determine whether the point lies into the simplex or no you only need to know a signs of at maximum d + 2 determinants of d * d size.

Let:

then we can construct a matrices (j,k index means: exclude j row and subtract vector from origin to point k from each of d remaining rows; all the left hand sides in rows defines a facet lying against j vertex):

Determinant of the above matrix is d! times d-dimensional oriented hypervolume of a simplex, constructed from points involved in the formula (strictly saying is the oriented hypervolume of a parallelotope, whose edges are given by the matrix rows).

If point is inside the simplex, then all the below equations is true (matching the orientation (sign of oriented hypervolume) of j and 0 pair of points relative to a facet):

but we can note, that

So we can calculate only one determinant from left hand side of comparison (?):

and assume, that sign flips for next js.

Therefore, we should to compute at least 2 determinants of d*d matrices, and maximum d + 2 (of A^1,1 and of A^j,0 for all j in {1, 2, ..., d + 1}). If sign is not matched on some step, then the point is outside of a current facet of the simplex, and, thereby, out of the simplex at all.

ADDITIONAL:

If some of the right hand side determinants are zero, then the point is coplanar to planes of corresponding facets.

这篇关于如何检查单纯形是否包含原点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！