4D中的凸壳

Question

假设四个4D点[1/3,1/6,1/3,1/6]，[0,0,1/2,1/2]，[0,0,0 ，1]和[0,0,2/3,1/3]。如何在Python中计算它们的凸包的以下属性？

1）设定的极值点

2）的凸包的投影到不同的坐标轴，即X轴，Y轴，...。

Answer 1

我不能为Python说话特别，但你想要的算法是Jarvis March (aka gift-wrapping method).开始通过寻找已知极值点一个（简单地通过数字比较的坐标）。然后，将该点与该集合中的每个其他点B配对，直到找到一个点，使得该集合中的所有其他点位于AB的一边。这意味着B是一个极端点，因此用A替换B并重复该过程。最终的结果是极端点和凸包。

注意复杂度为O（NH），其中ħ最终发现船体的顶点的数量。 Graham scan更高效，但它不能在三个维度上进行调整。