我正在尝试将向量量化的实现设计为一个 c++ 模板类，它可以处理不同类型和维度的向量（例如 16 维字节向量或 4d 双精度向量等）。
我一直在阅读算法，我了解其中的大部分内容：
我想实现 Linde-Buzo-Gray (LBG) 算法，但我很难弄清楚划分集群的一般算法。我想我需要定义一个平面（超平面？），将向量分成一个簇，这样平面的每一侧都有相等的数量。
[编辑以添加更多信息] 这是一个迭代过程，但我想我首先找到所有向量的质心，然后使用该质心定义分割平面，获取平面每个边的质心，继续直到我获得了 VQ 算法所需的集群数量（迭代以优化以减少沿途的失真）。上面第一个链接中的动画很好地展示了它。
我的问题是：
一旦我有了质心，找到平面的算法是什么？
如何测试向量以查看它是否在该平面的任一侧？
如果您从一个质心开始，那么您将不得不拆分它，基本上是通过将其加倍并在任意方向上稍微移动点分开。该平面只是与该方向正交的平面。
但是您不需要计算该平面。
更一般地，区域 (i) 被定义为比任何其他质心更接近质心 c_i 的点集。当你有两个质心时，每个区域都是一个半空间，因此被一个（超）平面隔开。
如何在向量 x 上进行测试以查看它在平面的哪一侧？（有两个质心）
只需计算距离 ||x-c1|| 和 ||x-c2||，最小值（1 或 2）的索引将为您提供点 x 所属的区域。
更一般地，如果您有 n 个质心，您将计算所有距离 ||x-c_i||，并且质心 x 最接近（即距离最小）将为您提供 x 所属的区域。
我不太了解算法，但第二个问题很简单：
让我们称V为从平面上的任何点延伸到问题点的向量。然后，当V·N > 0时，问题点与法线N位于（超）平面的同一侧