LINK:三维凸包

一个非常古老的知识点。估计也没啥用。

大体上了解了过程 能背下来就背下来吧.

一个bf:暴力枚举三个点 此时只需要判断所有的点都在这个面的另外一侧就可以说明这个面是三维凸包上的面了。

一个问题 :多点共面问题。一个trick:可以利用扰动法然后 就可以解决这个问题了。

正解:\(n^2\)的增量法求三维凸包。

先加入三个不共线的点组成一个面(正反两面然后不断加入点。

然后考虑每一个点 删除这个点可以看到的面 然后边界与新加入的点连边即可。

具体理解看代码(我也有点迷。。

05-28 11:28