Как выполнить пространственное разбиение в n-измерениях?

Question

Я пытаюсь спроектировать реализацию векторного квантования как шаблонный класс c ++, который может обрабатывать разные типы и измерения векторов (например, 16-байтовые векторы байтов или 4d-векторы двойников и т. Д.).

Я перечитывал алгоритмы и понимаю большинство из них:

здесь и здесь

Я хочу реализовать алгоритм Линде-Бузо-Грея (LBG), но мне сложно разобраться в общем алгоритме разделения кластеров. Я думаю, что мне нужно определить плоскость (гиперплоскость?), Которая разделяет векторы в кластере, чтобы на каждой стороне плоскости было одинаковое число.

[изменить, чтобы добавить больше информации] Это итеративный процесс, но я думаю, что начну с нахождения центроида всех векторов, затем использую этот центроид, чтобы определить плоскость расщепления, получая центроид каждой из сторон плоскости, продолжая, пока у меня не будет количества кластеров необходим для алгоритма VQ (итерация для оптимизации для меньшего искажения по пути). Анимация в первой ссылке выше показывает это хорошо.

Мои вопросы:

Что такое алгоритм для поиска плоскости, когда у меня есть центроид?

Как проверить вектор, чтобы увидеть, находится ли он по обе стороны от этой плоскости?

Answer 1

Если вы начинаете с одного центроида, вам придется разделить его, в основном, удвоив его и слегка раздвинув точки в произвольном направлении. Плоскость - это просто плоскость, ортогональная этому направлению.

Но вам не нужно вычислять эту плоскость.

В более общем смысле, область (i) определяется как набор точек, которые ближе к центроиду c_i, чем к любому другому центроиду. Когда у вас есть два центроида, каждый регион - это полупространство, разделенное (гипер) плоскостью.

Как проверить вектор x, чтобы увидеть, на какой стороне плоскости он находится? (это с двумя центроидами)

Просто вычислите расстояние || x-c1 || и || x-c2 ||, индекс минимального значения (1 или 2) даст вам, к какой области принадлежит точка x.

В целом, если у вас есть n центроидов, вы бы вычислили все расстояния || x-c_i ||, и центроид x ближе всего (то есть, для которого расстояние минимально) даст вам область x принадлежащий.

Answer 2

Я не совсем понимаю алгоритм, но второй вопрос прост:

Назовем V вектором, который расширяет от любой точки на плоскости до рассматриваемой точки. Тогда рассматриваемая точка находится на той же стороне (гипер) плоскости, что и нормаль N тогда и только тогда V · N > 0