How do I check if a simplex contains the origin?
collision, haskell, linear-algebra, math, physics
Solution
(change theme to light one if formulae are not recognizible)
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 `j`s.
Therefore, we should to compute at least `2` determinants of `d*d` matrices, and maximum `d + 2` (of A1,1 and of Aj,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.
Problem
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] ```