如何在n維中執行空間分區？

Question

我試圖設計一個矢量量化的實現作爲一個C++模板類，可以處理矢量的不同類型和尺寸（例如16維矢量字節，或4d矢量雙打等）。

我一直在閱讀了對算法，我理解大部分：

here和here

我要實現的林德BUZO灰色（LBG）算法，但我m難以找出劃分簇的一般算法。我想我需要定義一個平面（超平面？），將平面中的矢量分開，這樣在平面的每一側上都有相同的數字。

[編輯以添加更多信息] 這是一個反覆的過程，但我想我開始通過尋找所有向量的重心，然後使用質心來定義分裂平面，讓每一個的心直到我有VQ算法所需的簇的數量（迭代以優化以減少沿途的失真）爲止。上面第一個鏈接中的動畫很好地顯示了它。

我的問題是：

什麼是算法來找出飛機一旦我有質心？

如何測試矢量以查看它是否在該平面的任一側？

Answer 1

如果你開始一個質心，那麼你就必須拆分它基本上是通過將其加倍並稍微將點向任意方向分開。該平面就是與該方向正交的平面。

但是你不需要計算那個平面。更一般地，區域（i）被定義爲比任何其他質心更接近質心c_i的點的集合。當你有兩個質心時，每個區域都是半空間，因此被（超）平面隔開。

如何測試矢量x以查看飛機的哪一側？ （即有兩個質心）

只計算距離|| x-c1 ||和|| x-c2 ||，最小值（1或2）的索引將給出點x屬於哪個區域。更一般地說，如果你有n個質心，你可以計算所有距離|| x-c_i ||，並且質心x最接近（即距離最小）將會給你區域x屬於。

Answer 2

我不太瞭解的算法，但第二個問題很簡單：

讓我們把V這從在飛機上任何點延伸至點-A的輸入向量題。然後點中，問題在於對（超）平面的同一側正常ñ IFF V·ň> 0