我正在使用层次聚类来尝试可视化一组被展平到二维的大数据。我要做的是创建一个可视化，允许我从层次结构的不同高度查看数据，通过将集群渲染为其组成点的凸面外壳。这个问题最困难的部分是，我需要一个算法，当我向上移动层次时，可以有效地合并成对簇的凸包。我已经看过很多算法来计算点在O（n logn）时间内的凸壳，但在这种情况下，似乎更有效地利用问题的子结构，但我不确定具体是如何实现的。
编辑：
为了获得更多信息，数据结构是一个数组，它从集群的原始点开始，然后指出哪些点/集群组合起来形成下一个集群。所以它有点像树/指针结构，但是包含在一个大数组中。重要的一点是，查看任何超级簇的两个组成簇是什么是有效的，但是获取属于一个簇的所有点的集合是无效的。所以任何合理的算法都必须自下而上地工作。
假设我们在某个地方处于层次结构的中间，而预计算的层次结构表明A和B簇合并生成C簇。我们从下往上，所以我们已经计算了A和B簇中点的凸壳，所以我们只需要把它们组合起来就可以得到C簇的凸包。A簇的凸包实际上可以是一个点、一对或一个完整的多边形。集群B也是如此，所以有几个例子可以说明如何合并这些元素来形成集群C的凸包，但我敢打赌有一个聪明的解决方案，它可能会像对待多边形一样对待单子和对。
最明显的解决方案是用集群A和集群B的凸包的组合点集计算凸包。但是我需要在100k个点的层次上这样做，所以我想知道是否有更有效的方法来组合A和B的凸包。
编辑2：
/----5
1---/ / \
/ \ / B 8
2 A 3 C 6 /
\ / \ /
4--------7
好吧，我试着用ASCII来说明我的意思。簇A的凸壳为1-2-3-4，簇B的凸壳为5-6-7-8，簇C的凸壳为1-2-4-7-8-5。据推测，集群A和集群B在外壳内部包含额外的点，但这些点显然不可能成为C外壳的一部分，因此问题是一个算法，该算法根据点的坐标确定在何处“拼接”集群A和集群B的外壳以形成C外壳。这是整个过程的归纳步骤。（最终C将与D簇等组合，直到算法以最顶端的簇结束，该簇将所有点的凸包作为其凸包）。
最佳答案
至少有两种凸包合并算法，我知道——rotating calipers的图桑（第5节）和bridging algorithm的Preparata和洪（见第3节）。这两种算法在h=h1+h2中都是时间线性的，其中h1和h2分别是第一个和第二个凸壳中的壳顶点数。
关于python - Python中分层聚类的凸包，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12977747/