问4D中的凸壳

EN

我不能专门为Python说话，但您想要的算法是贾维斯·马奇(也称礼品包装法)。，首先要找到一个已知的端点A(只需比较数字坐标)。然后，把这个点和集合中的其他点B配对，直到你找到其中一个点，使得集合中的所有其他点都位于AB的一边。这意味着B是一个极端点，所以用B替换A，然后重复这个过程。最终的结果是极值点和凸包。

注意，复杂性是O(nh)，其中h是最终找到的船体顶点的数目。格雷厄姆扫描更有效率，但它不能超越三维。