如何进行n维空间划分？

Question

我正在尝试将矢量量化的实现设计为 C++ 模板类，可以处理不同类型和维度的矢量（例如字节的 16 维向量，或双精度数的 4d 向量等）。

我一直在阅读算法，并且我理解其中的大部分：

这里 和 这里

我想实现 Linde-Buzo-Gray (LBG) 算法，但我很难弄清楚用于分区集群的通用算法。我想我需要定义一个平面（超平面？），它将向量分割成一个簇，这样平面的每一侧都有相同的数量。

[编辑以添加更多信息]这是一个迭代过程，但我想我首先找到所有向量的质心，然后使用该质心定义分割平面，获取平面每条边的质心，继续直到获得簇数VQ 算法所需（迭代以优化以减少失真）。上面第一个链接中的动画很好地展示了这一点。

我的问题是：

一旦我有了质心，找到平面的算法是什么？

如何测试矢量以查看它是否位于该平面的任一侧？

Answer 1

如果您从一个质心开始，那么您必须将其分割，基本上是通过将其加倍并在任意方向上稍微移动点分开。该平面就是与该方向正交的平面。

但您不需要计算该平面。

更一般地，区域(i)被定义为比任何其他质心更接近质心c_i的点的集合。当有两个质心时，每个区域都是半空间，因此由（超）平面分隔。

如何测试向量 x 以查看它在平面的哪一侧？（有两个质心）

只需计算距离|| X-C1 || || x-c2 ||，最小值（1或2）的索引将为您点X所属的哪个区域。

更一般地，如果您有 n 个质心，您将计算所有距离 ||x-c_i||，并且最接近的质心 x（即距离最小）将为您提供 x 所属的区域。

Answer 2

我不太明白算法，但第二个问题很简单：

我们打电话吧 V 延伸的向量 从 平面上任意一点 到 问题点。那么问题点与法线位于（超）平面的同一侧 氮 当且仅当 V·N > 0