代码之家 › 专栏 › 技术社区 › kevin42

如何在N维中进行空间划分?

space-partitioning math algorithm

4

kevin42 · 技术社区 · 14 年前

我尝试设计矢量量化作为C++模板类的一种实现,它可以处理向量的不同类型和维度(例如字节的16维向量,或双倍的4D向量等)。

我一直在读算法,我了解其中的大部分:

我想实现linde-buzo-gray(lbg)算法,但是我很难找到划分集群的通用算法。我想我需要定义一个平面(超平面?)它将一个簇中的向量分割开来,这样在平面的每一侧都有一个相等的数字。

[编辑以添加更多信息] 这是一个迭代过程,但我认为我首先找到所有向量的质心,然后使用该质心定义分割平面,得到平面各边的质心,继续直到我有VQ算法所需的簇数(迭代以优化F或者减少沿途的变形)。上面第一个链接中的动画很好地显示了它。

我的问题是:

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

我如何测试一个向量,看它是否在平面的两边?

2 回复 | 直到 13 年前

1

2

Olivier Verdier 14 年前

如果你从一个质心开始,那么你必须把它分开,基本上是把它加倍,然后在任意方向上稍微移动点。平面就是与那个方向垂直的平面。

但你不需要计算那个平面。

更一般地说,区域(i)被定义为比任何其他质心更接近质心c_i的一组点。当有两个质心时,每个区域都是一个半空间,因此被一个(超)平面隔开。

如何在向量x上进行测试以查看它在平面的哪一侧?(有两个质心)

只要计算距离x-c1和x-c2,最小值(1或2)的索引将给出点X所属的区域。

更一般地说,如果有n个质心,你会计算出所有的距离,质心x最接近(也就是说,距离最小)会给你区域x所属的。

2

0

BlueRaja - Danny Pflughoeft 14 年前

我不太了解算法,但第二个问题很简单:

我们打电话来 V 延伸的向量从飞机上的任何一点到问题的关键。那么问题点就在(超)平面与法向平面的同一侧。 n 敌我识别 V·N gt 0