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

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

space-partitioning math algorithm

kevin42 · 技术社区 · 15 年前

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

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

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

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

我的问题是:

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

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

2 回复 | 直到 14 年前

Olivier Verdier 15 年前

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

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

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

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

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

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

BlueRaja - Danny Pflughoeft 15 年前

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

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

推荐文章

Muhammad Umer · 为什么这个随机数猜谜游戏模拟产生5.8

6 月前

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

6 月前

Jack Maessen · 当min-val不为0时,如何计算输入type=“range”中点之间的填充颜色

7 月前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

7 月前

Jukka · 计算中值

7 月前

D W · Python-将浮点数从2转换为10到100位小数

7 月前

Bartol · 确定python龟图形中的角度

11 月前

randomAlgo · 将弹簧设置为相同长度的成本最低

1 年前

Fyodor · 在C中使用sin和cos计算数学表达式不正确?

1 年前

Sergio · python中大量数字的乘法

1 年前