2021-02-05 碰撞检测GJK算法详解（初学者慎入）

碰撞检测有2个经典算法，一个是分离轴算法SAT,还有一个就是本文要介绍的GJK，GJK是三个人的名字首写大字母；这个算法的数学推导有点复杂，目前网上只有这篇
https://blog.csdn.net/u010016421/article/details/104788769/
相对比较详细的介绍了算法，其主要也是参考原始论文翻译的；考虑到原始论文比较难读，博主特地专门写一篇文章介绍，博主的这篇文章会必要的地方稍微简化一下

但是尽管如此，由于这个算法涉及到的数学概念较多，读者最好有一定的线性空间和线性代数的知识，否则的话会理解比较困难。

由于这篇文章没有绘图，全是公式推导，读者容易看着一头雾水，因此，先对整个算法的思路做一个概述；
1，首先，算法基于闵可夫斯基差（也是一个凸体），将两个凸体是否相交的问题转化为一个凸体是否包含原点的问题
2，巧妙的地方在于，该算法又不需要直接计算两个凸体的闵可夫斯基差，只需要一个和闵可夫斯基差有关的参数 $s_K(x)$ ,而这个参数，直接利用原来的两个凸体就可以计算；
3，算法的整体思想是迭代进行的，我认为该算法实际上是数学上单纯形法的一种应用方式
4，3维的单纯形是一个四面体，2维度是一个三角形，但该三角形可以是三维空间的三角形；
5，为何要用单纯形，个人认为是出于数学处理上的方便，给定单纯形的顶点集，则单纯形本身可以用一个关于顶点对称的线性方程来描述集合；同时，单纯形上的点到原点的距离可以有很好的数学表示
6，算法其实是不断的构建包含于闵可夫斯基差（这里只需理解为一个凸体）的单纯形，并使得原点到单纯形的距离越来越小；最终达到的状态就是单纯形到原点的距离就是闵可夫斯基差到原点的距离，
7，对于3维度空间而言，如果把闵可夫斯基差想象为一个四面体，则迭代最终的单纯形可能就是它的一个面，原点到这个面的距离就是原点到这个四面体的距离
8，由于单纯形到原点的距离是一个限制最优问题，所以文章先求出仿射空间到原点距离（非限制最优），如果单纯形是个三角形，则其仿射空间，就是这个三角形所在的平面，实际上就转化为平面到原点距离问题
9，通过线性方程，上述问题可以转化而为函数极值问题，其解可以有一个线性方程组来描述；
10，定理3给出了该方程组的行列式和代数余子式的递归构建方法，并且给出了判别准则：当这些行列式，和代数余子式满足什么关系时，对应的单纯形满足：该单纯形到原点的距离就是整个闵可夫斯基差到原点的距离，并且这是一个维度尽可能低的单纯形

下面开始正文

为了简化，本文将采用爱因斯坦求和表示法，
先给出一些概念定义：

1, $R$ ：表示所有实数的集合
2, $R^m$ : 由形如 $(x_1,x_2,...,x_m)$ 的元组组成的集合，其中 $x_i\in R$
3, 把 $R^m$ 中的元素看成向量，则可以向量加法以及数乘运算，则 $R^m$ 连同这两个运算可以看成系数域 $R$ 上的向量空间
4,凸体：（这里仅限为 $R^m$ 中的凸体） $R^m$ 的一个子集，其中任意两点连成的线段都属于该子集，则该子集就是一个凸体
5，集合 $S$ 的凸包：包含 $S$ 的最小凸体
集合 $S$ 的凸包用 $co(S)$ 来表示
6，集合 $S$ 和 $T$ 的距离:
定义为 $d(S,T):= \min\{|x-y|\}, x\in S ,y\in R\$
7，闵可夫斯基和：
向量空间 $R^m$ 中的两个子集 $S,T$ 的闵可夫斯基和为: $\{x+y| x\in S, y\in T\}$
闵可夫斯基差： $\{x-y| x\in S, y\in T\}$
8，线性无关：一组向量 $\{x_i\}$ 线性无关当且仅当方程
$k_ix_i =0$ 只有唯一解 $k_i=0$
9,仿射无关：一组向量 $\{x_i\}$ 仿射无关当且仅当 $\{x_j-x_1\}(j\neq 1)$ 线性无关
10，单纯形：仿射无关向量组成的集合的凸包
11，符号 $v(K)$ 表示集合 $K$ 中距离原点最近的点(当K是凸体时是唯一的)

算法输入: $R^m$ 中的两个凸体
输出：两个凸体的间距d

显然，该算法可以判断两个凸体是否相交，也就是根据输出d是否为0即可判断

算法思路：
记两个凸体为 $S,T$ ，显然，若两者相交，则其闵可夫斯基差必然包含原点；反之如果闵可夫斯基差包含原点，则必然相交

因此原问题转化为判断 $S,T$ 的闵可夫斯基差是否包含原点的问题
(容易证明（略）：两个凸体的闵可夫斯基差也是凸体)
我们记 $K$ 为 $S,T$ 的闵可夫斯基差

该算法没有直接计算闵可夫斯基差，而是想办法构造一个集合序列:
${V_0,V_1,V_2,..}$ 使得该序列中每个集合都是 $K$ 的子集，并且原点到 $V_i$ 的距离（见定义6，单个点看成由单个点组成的集合）逐渐变小，直到最终得到最小值，也就是目标值d;

我们限定在 $R^m$ 空间中讨论，构造函数 $h$ 如下：
$h_K(x):= max\{ x\cdot z\} （z\in K）$
这个函数的含义是，在集合 $K$ 中找到一个点 $z$ ,使得 $z$ 在 $x$ 方向上的有向投影值h最大，那么 $h |x|$ 就是函数的值,
对应的使得函数取最大值的 $z$ 记作 $s_K(x)$ ,有 $h_K(x)=s_K(x)\cdot x$

算法并没有显示的构建闵可夫斯基差 $K$ ，而是计算 $s_K(x)$ ,但是计算 $s_K(x)$ 并不需要 $K$ ,利用 $R,S$ 可以计算 $s_K(x)$

公式为: $s_K(x)=s_S(x)-s_T(-x)$

在陈述算法之前，先证明一个定理:
定理1：设 $K\subset R^m$ 是紧致凸集，定义 $g_K:R^m->R$ 为
$g_K(x)=|x|^2+h_K(-x) (x\in K)$
那么有:
1)如果 $g_K(x)>0$ ,存在一个点 $z\in co(\{s_K(-x),x\})$ 使得 $|z|<|x|$
2) $g_K(x)=0$ 当且仅当 $x=v(K)$
3) $|x-v(K)|^2<=g_K(x)$ （据此，必有 $g_K(x)>=0$ ）

证明：
(1) $h_K(-x)=s_K(-x)\cdot (-x)$ 代入 $g_K(x)$ 表达式，得到:
$g_K(x)=x\cdot x - s_K(-x)\cdot x = x\cdot(x-s_K(-x))$
过点 $x$ 做超平面 $P$ 与 $x$ 垂直， $g_K(x)>0$ 意味着， $x与x-s_K(-x)$ 夹角<90度，则如果该超平面的法向取为何 $x$ 同向，则 $s_K(-x)$ 位于该超平面的背面，从几何角度可以看出 $z$ 的存在性；
(2)根据1)如果 $g_K(x)=0$ ,则意味着 $s_K(-x)$ 在超平面 $P$ 上，由于 $x$ 也在该超平面 $P$ 上，且 $x$ 与 $P$ 垂直，根据 $s_K(-x)$ 的定义，在 $K$ 中所有点中，它是投影到 $-x$ 方向的有向长度最大的，而这个长度等于 $x$ 在 $-x$ 方向投影的有向长度，因此超平面 $P$ 的背面没有 $K$ 中的点，且 $x$ 与超平面 $P$ 垂直，则 $x=v(K)$ ;
反之，若 $x=v(K)$ 仍然根据超平面 $P$ 的性质， $x$ 在超平面上的有向投影就是 $h_k(-x)$ ,则 $g_K(x)=0$
(3) 根据2)中结论,
$g_K(v(K))=0$ => $|v(K)|^2 +h_K(-v(K))=0$ =>
$|v(K)|^2=-h_K(-v(K)) <=z\cdot v(K)$ 任意 $z\in K$
$-h_K(-v(K))=-s_K(-v(K))\cdot (-v(K))=v(K)\cdot s_K(-v(K))<=z\cdot v(K)$
则
$|x-v(K)|^2 = |x|^2-2x\cdot v(K) +|v(K)|^2 <=|x|^2-x\cdot v(K) <= |x|^2 + h_K(-x)$ ( $h_K(-x)=-x\cdot s_K(-x)$ ,
$x\cdot v(K) >= x\cdot s_K(-x)$ $v(K)-s_K(-x)$ 与 $x$ 同向)

算法流程如下,给定紧致凸集 $K\in R^m$ ,以及 $v(1<=v<=m+1)$ 个位于 $K$ 中的初始点 $y_1,...,y_v$ ,执行如下操作：
1，令 $V_0 = {y_i} , k=0$
2, 求出 $v_k = v(co(V_k))$
3,计算 $g_K(v_k)$ ,如果=0,令 $v(K)=v_k$ (根据定理1-2)，算法结束；
4,计算 $V_k'，V_k'$ 是具备下述性质的集合:
(1) $V_k'\subset V_k$ ,
(2) $v_k\in co(V_k')$ ,
(3) $V_k'$ 仿射无关且元素个数 $<=m$
5,令 $V_{k+1}=V_k'\cup {s_K(-v_k)}$ ,令 $k+=1$ ,返回第2步
关于 $V_k'$ 的存在性证明暂时略过

下面说明，该算法的递降性得以保证，也就是
$|v_{k+1}|<=|v_k|$
证明:
$|v_{k+1}|=|v(co(V_{k+1}))|<=|v(co({v_k,s_K(-v_k)})|<|v_k|$
（根据定理1-1）

定理2：假设 $Z$ 是一个凸多面体的顶点集， $K=co(Z)$ ,则上述算法作用于 $K$ 将在有限步之后终止
证明:显然 $Z\cup V_0$ 是有限集，设其非空子集个数为N,
根据以上分析，在算法迭代过程中,有 $|v_{k+1}|<|v_k|$
根据 $v(x)$ 的唯一性，必有 $V_{i}!=V_{j}$ (i!=j),可是
$V_{i}\subset Z\cup V_0$ ,则其可能的不同个数是有限的，矛盾；

在上述算法中，第二步，要计算 $v_k=v(co(V_k))$ ，以及第四步要计算 $V_k'$ ，下面来说明这两个的计算方法：
不妨设 $V_k={y_1,y_2,...,y_v}=Y$ ，利用我们的方法，我们最终将得到如下形式的表达（这三个式子整体在后面称作目标表达式）:
1, $v(co(Y))= \lambda_iy_i \quad i\in I \subset \{1,2,...,v\}$
2, $\sum\lambda_i =1 \quad \lambda_i>0 \quad i\in I\subset \{1,2,...,v\}$
3, $Y_I = \{y_i| i\in I\}$ 仿射独立
（实际上，从几何学的角度来看， $Y_I$ 的含义是，找到包含v(co(Y))的最小顶点集凸包，对于三维空间可以举一个特例如下：假设Y是一个单纯形（4面体）的顶点集，则如果v(co(Y))位于该四面体内部，则Y_I为4个顶点集合，如果v(co(Y))位于某个面上而不在任意一个边上，则Y_I为这个面的3个顶点集，如果v(co(Y))位于某条边上而不在任何顶点，则Y_I为这个边的两个顶点，如果v(co(Y))位于顶点上，则Y_I就是这个顶点）
很显然，以上表示已经覆盖了 $v_k=v(co(V_k))$ 和 $V_k'$ ,
$v_k = v(co(V_k))=\lambda_iy_i$
$V_k' = Y_I$

由于 $Y$ 的非空子集个数为 $2^{|Y|}-1$ ,令 $I$ 取遍 $\{1,...,v\}$ 的非空子集，则其中必有一个满足上述条件，下面我们给出一种方法，该方法对于每个 $Y_I$ 求出一组对应的参数 $\lambda_I$ ，并使得其中必有一个满足上述条件，这个方法如下：
用 $I'$ 表示 $I$ 关于 $\{1,...,v\}$ 的补集
$\Delta_i(\{y_i\}) = 1 ,i\in I$
$\Delta_j(Y_I\cup {y_j}) = \sum_{i\in I} \Delta_i(Y_I)(y_i\cdot(y_k-y_j))$ ( $k\in I ,j\in I'$ )
$\Delta(Y_I)=\sum_{i\in I}\Delta_i{Y_I}$
$\lambda_i = \Delta_i(Y_I)/ \Delta(Y_I)$
并且给出定理3:
目标表达式成立的充分必要条件是:
(1) $\Delta(Y_I)>0$
(2) $\Delta_i(Y_I)>0 (任意i\in I)$
(3) $\Delta_j(Y_I\cup {y_j}) <=0 (任意i\in I')$

下面给出证明:
对于 $Y_I \subset Y$ ，我们来计算 $v(aff(Y_I))$
其中 $aff(X):= \{\sum \lambda_i x_i |\sum\lambda_i = 1\ ,\lambda_i\in R \}$
假设 $Y_I$ 的元素个数为r,其元素为 $x_1,...,x_r$
则必有:
$v(aff(Y_I)) = \{\sum \lambda_i x_i\}$
将 $\lambda_1 = 1-\sum_{2}^r \lambda_i$ 代入，并化简，得到
$v(aff(Y_I))=x_1+\sum_{2}^r\lambda_i(x_i-x_1)$
由于 $v(aff(Y_I))$ 使得 $|v(aff(Y_I)|$ 取极小值，则必有
$f(\lambda_2,...,\lambda_r)=|x_1+\sum_{2}^r\lambda_i(x_i-x_1)|^2$ 取极小值，
则有 $\partial(f)/\partial(\lambda_i)=0$ ，显然该偏导数只与和 $\lambda_i$ 有关的项有关系
将上式展开，合并同类项，其中和 $\lambda_i$ 有关的项为:
$\lambda_i^2|(x_i-x_1)|^2 +2\sum_{j!=i}\lambda_i\lambda_j(x_i-x1)\cdot (x_j-x_1)+2\lambda_ix_1\cdot (x_i-x_1)$
求偏导并令其为0，得到方程:
$2\lambda_i|x_i-x1|^2+2\sum_{j!=i}\lambda_j(x_i-x_1)\cdot (x_j-x_1) +2x_1\cdot(x_i-x_1) = 0$
=>
$(x_i-x_1)\cdot[\lambda_i(x_i-x_1)+\sum_{j!=i}\lambda_j(x_j-x_1)+x_1] = 0$
=>
$(x_i-x_1)\cdot [ \sum_j\lambda_j(x_j-x_1)+x_1] = 0$
(其中 $j$ 取遍 $2,3,...,r$ )
=> （利用 $\lambda_1 = 1-\sum_{2}^r \lambda_i$ ）
$(x_i-x_1)\cdot\sum_j\lambda_j x_j = 0$ ( $j$ 取遍 $1...r$ )
=>
$\sum_j (x_i-x_1)\cdot x_j \lambda_j = 0$

令 $i$ 取遍历 $2,3,...r$
我们将得到，以下方程组:
$A_I \lambda = b$
其中，
$A_I=\left(\begin{array}{ccc} 1 & ... & 1\\\\ (x_2-x_1)\cdot x_1 & ... & (x_2-x_1)\cdot x_r\\\\ \quad... \quad ... \quad...\\\\ (x_r-x_1)\cdot x_1 & ... & (x_r-x_1)\cdot x_r\\\\ \end{array}\right)$
$b=\left(\begin{array}{ccc} 1\\\\ 0\\\\ ...\\\\ 0 \end{array}\right)$

从对称性可以看出，一般的,只要 $i!=k$ 有:
$\sum_j (x_i-x_k)\cdot x_j \lambda_j = 0$ ( $j$ 取遍 $1,...,r$ )

下面我们计算上述矩阵的行列式: $\Delta(A_I)$ ,
先复习一下矩阵的初等变换性质，
（1）将矩阵某行（列）乘以一个系数加到矩阵另外一行（列），矩阵的行列式不变；
（2）矩阵某行（列）乘以一个系数，行列式的值也乘以该系数
（3）交换矩阵两行（列），矩阵行列式变号
将第一行乘以 $-(x_i-x_1)*x_1$ 加到第 $i$ 行得到（行列式不变）:
$Delta(A_I)=\left|\begin{array}{ccc} 1 & ... & 1 &...& ...\\\\ 0 & (x_2-x_1)\cdot (x_2-x_1) &... & (x_2-x_1)\cdot (x_r-x_1)\\\\ \quad... \quad ... \quad...\\\\ 0 & (x_r-x_1)\cdot (x_2-x_1) & ... & (x_r-x_1)\cdot (x_r-x_1)\\\\ \end{array}\right|$
按照第一行第一列展开，得到:
$Delta(A_I)=\left|\begin{array}{ccc} (x_2-x_1)\cdot (x_2-x_1) &... & (x_2-x_1)\cdot (x_r-x_1)\\\\ \quad... \quad ... \quad...\\\\ (x_r-x_1)\cdot (x_2-x_1) & ... & (x_r-x_1)\cdot (x_r-x_1)\\\\ \end{array}\right|$
令矩阵
$Q=((x_2-x_1),(x_3-x_1),...,(x_r-x_1))$
则有 $Detla(Q^TQ) = Delta(A_I)$
(第 $i$ 行， $j$ 列元素都为 $(x_{i+1}-x_1)^T(x_{j+1}-x_1)=(x_{i+1}-x_1)\cdot (x_{j+1}-x_1)$ )
我们设 $A=Q^T , B= Q$
显然 $Delta(A_I)=Detla(Q^TQ)=Delta(AB)$
现在我们来看看对 $A_I$ 执行初等变换，将如何影响 $A,B$ ，稍加分析，有以下结论:
(1)对 $A_I$ 执行行变换，等价于对 $A$ 执行相同的行变换，
对 $A_I$ 执行列变换，等价于对 $B$ 执行相同的列变换
该结论记为定理X

现在，由于以上矩阵的推导是按照排序 $x_1,x_2,...,x_r$ 的顺序推导出来的，而是 $x_1,x_2,...,x_r$ 是 $Y_I$ 中元素任意一个排序，现在我们研究，如果改变排序方法，对上述矩阵行列式的影响；先只考虑交换2个元素的情形，
(1) $x_m$ 与 $x_n$ 的编号交换， $m,n$ 都不等于1
此时，新矩阵相当于原矩阵，交换 $x_m$ 和 $x_n$ 的情形:
我们观察
$A_I=\left(\begin{array}{ccc} 1 & ... & 1\\\\ (x_2-x_1)\cdot x_1 & ... & (x_2-x_1)\cdot x_r\\\\ \quad... \quad ... \quad...\\\\ (x_r-x_1)\cdot x_1 & ... & (x_r-x_1)\cdot x_r\\\\ \end{array}\right)$
如果把 $x_m,x_n$ 互换，可以等价为对该矩阵进行了一次行交换和一次列交换，则该矩阵的行列式在这个过程中值不变；
(2) $x_1$ 与 $x_t$ 交换
由于我们关心的是行列式的值，我们利用:
$Delta(A_I)=\left|\begin{array}{ccc} (x_2-x_1)\cdot (x_2-x_1) &... & (x_2-x_1)\cdot (x_r-x_1)\\\\ \quad... \quad ... \quad...\\\\ (x_r-x_1)\cdot (x_2-x_1) & ... & (x_r-x_1)\cdot (x_r-x_1)\\\\ \end{array}\right|$
将其写成 $Delta(A_I)=Detla(Q^TQ)=Delta(AB)$ 形式有:
$A = \left(\begin{array}{cccc} (x_2-x_1)^T\\\\ (x_3-x_1)^T\\\\ ...\\\\ (x_r-x_1)^T \end{array}\right)$
$B=((x_2-x_1),(x_3-x_1),...,(x_r-x_1))$
现在将 $x_1$ 与 $x_t$ 交换，设 $A_I$ 变为 $A_I'$ ,并且对应的展开为 $A',B'$ ，则
$A' = \left(\begin{array}{cccc} (x_2-x_t)^T\\\\ ...\\\\ (x_{t-1}-x_t)^T\\\\ (x_1-x_t)^T\\\\ (x_{t+1}-x_t)^T\\\\ ...\\\\ (x_r-x_t)^T \end{array}\right)$
$B'=((x_2-x_t),...,(x_{t-1}-x_t),(x_1-x_t),(x_{t+1}-x_t)...,(x_r-x_t))$
现在我们对 $A_I'$ 进行初等变换，根据定理X,只需要对 $A'$ 和 $B'$ 进行相应的行，列初等变换即可；
我们对 $A'$ 进行如下行变换（等价于对A_I'进行相同行变换）
1）将 $(x_1-x_t)^T$ 所在行 $*(-1)$ ,A_I'行列式累积变号1次

再将其分别加到其余行，则A'变为A, A_I'行列式累积变号1次
对 $'B'$ 进行如下行变换:
将 $(x_1-x_t)$ 所在列 $*(-1)$ ,A_I'行列式累积变号2次
将其分别加到其余列，则B'变为B,行列式累积变号2次；
综上，A_I'=A'B'进行以上变换变为 A_I=AB,并且行列式保持不变；

由于任何排序均可以看成依次执行交换两个元素的变换组合而成，也就是证明了 $Delta(A_I)$ 与选择的排序 $x_1,x_2,...,x_r$
那么我们可以记 $Delta(Y_I) = Delta(A_I)$

令 $\Delta_i(Y_I)$ 为 $A_I$ 中的 $y_i$ (设 $y_i=x_j$ ，由于 $Y_I$ 是取 $Y$ 的子集，其下标可能会变化)所在列的第一行元素的代数余子式,
根据线性方程组解公式，有:
$\lambda_j=\Delta_j(A_I)/Delta(Y_I)$
由于无论如何修改 $x_1,x_2,...,x_r$ 的排序，显然关联到 $y_i$ 的 $\lambda_i$ 值不变，则对应 $\Delta_j(A_I)$ 不变
则 $\Delta_i(Y_I)$ 的定义合法

根据以上的推理，我们还可以得到引理1:
$Y_I$ 仿射独立等价于 $Delta(Y_I)>0$
这一点根据 $A_I=Q^TQ$ 的分解可以得到

至此，我们可以来证明定理3了，先把定理3相关公式罗列一遍:
用 $I'$ 表示 $I$ 关于 $\{1,...,v\}$ 的补集
$\Delta_i(\{y_i\}) = 1 ,i\in I$ $...(A1)$
$\Delta_j(Y_I\cup {y_j}) = \sum_{i\in I} \Delta_i(Y_I)(y_i\cdot(y_k-y_j))$ ( $k\in I ,j\in I'$ ) $...(A2)$
$\Delta(Y_I)=\sum_{i\in I}\Delta_i{Y_I}$ $...(A3)$
$\lambda_i = \Delta_i(Y_I)/ \Delta(Y_I)$ $...(A4)$
目标表达式
1, $v(co(Y))= \lambda_iy_i \quad i\in I \subset \{1,2,...,v\}$ $...(B1)$
2, $\sum\lambda_i =1 \quad \lambda_i>0 \quad i\in I\subset \{1,2,...,v\}$ $...(B2)$
3, $Y_I = \{y_i| i\in I\}$ 仿射独立 $...(B3)$
成立的充分必要条件是:
(1) $\Delta(Y_I)>0$ $...(C1)$
(2) $\Delta_i(Y_I)>0 (任意i\in I)$ $...(C2)$
(3) $\Delta_j(Y_I\cup {y_j}) <=0 (任意i\in I')$ $...(C3)$

首先，我么证明我们定义的 $Delta(Y_I)$ 与 $Delta_i(Y_I)$ 满足定理3的递归等式:
1) $\Delta_i(\{y_i\}) = 1 ,i\in I$ 是平凡结论，显然成立
2) $\Delta_j(Y_I\cup {y_j}) = \sum_{i\in I} \Delta_i(Y_I)(y_i\cdot(y_k-y_j))$ ( $k\in I ,j\in I'$ )
将 $Y_I\cup {y_j}$ 对应的矩阵列出为:（令 $x_{r+1}=y_j$ ）
$B_I=\left(\begin{array}{ccc} 1 & ... & 1 &1\\\\ (x_2-x_1)\cdot x_1 & ... & (x_2-x_1)\cdot x_r & (x_{r+1}-x_1)\cdot x_{r+1}\\\\ \quad... \quad ... \quad...\\\\ (x_r-x_1)\cdot x_1 & ... & (x_r-x_1)\cdot x_r & (x_{r+1}-x_1)\cdot x_{r+1}\\\\ (x_{r+1}-x_1)\cdot x_1 &...& (x_{r+1}-x_1)\cdot x_r& (x_{r+1}-x_1)\cdot x_{r+1} \\\\ \end{array}\right)$
计算其第一行最后一列的代数余子式（对应 $x_{r+1}=y_j$ ）,为:
$(-1)^{1+r+1}\sum_{i=1}^{r} (-1)^{r+i}(x_{r+1}-x_1)\cdot x_i * Delta_i(Y_I)/(-1)^{i+1}$
$=\sum_{i=1}^{r}Delta_i(Y_I)x_i\cdot (x_1-y_j)$
根据对称性， $x_1$ 可以用任意 $x_k(k\in I$ 替换) ,即证
3) $\Delta(Y_I)=\sum_{i\in I}\Delta_i{Y_I}$
根据线性代数行列式计算法则，显然成立；

现在我们证明定理3的充分性：
几何上显然的事实是， $y = v(aff(Y_I))$ 等价于:
$y\cdot (y-y_k)=0 (k\in I)$ （ $D1$ ） ;
令 $y=v(aff(Y_I))$ ,
首先，根据引理1： $(C1)$ => $(B3)$ ;
并且显然，根据之前推导 $y$ 具备 $(B1)$ 右端的形式;
同时利用 $(C3)$ , $(A2)$ , $(A4)$ , $(C2)$ ,可以得到:
（将A4 代入A2）
$y\cdot(y_k-y_j) <=0 (k\in I ,j\in I')$
将 $k$ 遍历 $I$ 中元素，每项乘以 $\lambda_i$ 求和，得到：
$y\cdot (y-y_j) <= 0 (j\in I')$
同时，当 $j\in I$ 时，根据 $(D1)$ $y\cdot(y-y_j)=0$
综上 $y\cdot (y-y_i)<=0 (i \in \{1,2,...,v\})$
同时，对任意 $x\in co(Y)$ ，有方程:
$x=\sum_{i=1}^v \alpha_i y_i \sum\alpha_i=1 ,\alpha_i>=0$
则
$y\cdot(y-x) =$
$y\cdot(\sum_{i=1}^v\alpha_iy-\sum_{i=1}^v \alpha_i y_i )$
$\sum_{i=1}^v \alpha_iy\cdot (y-y_i) <=0$
则
$g_{co(Y)}(y)= |y|^2 + h_{co(Y)}(-y) = |y|^2-s_{co(Y)}(-y)\cdot y$
根据 $x$ 的任意性，可令 $x=s_{co(Y)}(-y)$
则 $g_{co(Y)}(y)<=0 => g_{co(Y)}(y)=0$
根据定理1 : $y=v(co(Y))$ $(B1)$

下面证明必要性:
1,显然(B3)=>(C1) (B2),(A4),(C1)=>(C2) ,
只需要证明 $(B1)=>(C3)$
假设 $y=v(co(Y))$ $(B1)$ 成立
根据定理1的结果 2,
有 $g_{co(Y)}(y)=0$ =>
$y\cdot(y-s_{co(Y)}(-y))=0$
则对任意 $y_i(1<=i<=v)$ ，因为 $y_i \in co(Y)$ ，则
$y\cdot(y-y_i)<=0 (1<=i<=v)$
由于 $\lambda_i>0 (B2)$ ，而有恒等式:
$\sum_{i\in I} \lambda_iy\cdot(y-y_i)$
$=y\cdot(y-\sum_{i\in I}y_i)$ （根据B1，点乘右边为0）
$=0$
则必有: $y\cdot(y-y_i)=0 (i \in I)$
根据(D1）, $y=v(aff Y_I)$ ，再结合引理1，得到 $(C1)$ ;
结合(B2)(C1)(A4),得到 (C2)

最后,根据 $y=v(aff Y_I)$ 有(D1): $y\cdot (y-y_k)=0 (k\in I)$
将 $y\cdot(y-y_j) (1<=j<=v)$ 减去 $y\cdot(y-y_k)=0 (i \in I)$
得到:
$y\cdot(y_k-y_j) (k\in I ,j\in I') <=0$
再根据（A2），（C2）,得到(C3)

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,491评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,856评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,745评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,196评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,073评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,112评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,531评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,215评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,485评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,578评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,356评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,215评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,583评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,898评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,174评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,497评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,697评论 2赞 335

2021-02-05 碰撞检测GJK算法详解（初学者慎入）

推荐阅读更多精彩内容