Overview Of GJK Algorithm

Here is a convex object and an origin point outside it.

$V_0$ is an arbitrary point in the boundary. Find the farthest point on the boundary along the vector $\overrightarrow{v_0o}$ . Name the farthest point $w_0$ .

We get a new vector $\overrightarrow{w_0o}$ to find the farthest point on the boundary along the direction $\overrightarrow{w_0o}$ . The point $w_1$ is added to the simple vertices set $S_2$ = { $w_0$ , $w_1$ }.

Connect points $w_0$ and $w_1$ , find the closet point $v_2$ on the line segment to the origin O. Find the farthest point $w_2$ on the boundary with direction $\overrightarrow{v_2o}$ . The point $w_2$ is added to the simple vertices set $S_3$ = { $w_0$ , $w_1$ , $w_2$ }.

Find the closest point $v_3$ on the triangle ( $w_0$ , $w_1$ , $w_2$ ). We can find the farthest point $w_3$ on the boundary along direction $\overrightarrow{v_3o}$ . Now we focus on the new convex hull $S_4$ = < $w_0$ , $w_3$ , $w_2$ >.

The length of the W triangle will become smaller as we continue these steps. For convex faceted objects, the closest point will be found in a finite number of steps.