Russian Qt Forum

Добрый день

Есть массив векторов (x, y, z). напр QPoint3D. Длина каждого вектора = 1. Необходимо разбить этот массив на подмассивы (группы) так чтобы угол между любыми 2-мя векторами в каждой группе не превышал заданный. Например группы могут выглядеть так

{ 0, 1, 10, 15 ... }  // первая группв (индексы элементов в исходном массиве)
{ 2, 5. 9, 24... }  // вторая группв
и.т.д

Элемент может принадлежать только 1 группе. Группа может содержать от 1 до N индексов (где N - размер исходного массива). Угол между 2-мя векторами единичной длины считается так

C++ (Qt)
inline float Angle( const Point3D & p0. const Point3D & p1 )
{
 return acos(p0.x * p1.x + p0.y * p1.y + p0.z * p1.z);
}

Как разбить на минимальное число групп?
Спасибо

Первое что приходит в голову.
Взять любой вектор, посчитать угол от него до всех остальных, отсортировать по по углу. Далее начинаем перебирать все вектора, когда превышена граница угла, за базовый берем следующий вектор и продолжаем перебирать дальше.

P. S. только не уверен насчет минимальногсти получившегося разбиения.

:) Именно этот вариант я и реализовал 2 дня назад (думал все просто). Увы, он бьет на фонге (attachment, артифакт на спинках стульев).
 
Разобрался почему: происходит "запуск козла в огород". То есть когда мы добавляем по отсортированному массиву - мы добавляем "все что подходит к первому". И получается что первому-то оно подходит - а остальным - не очень

Ну тогда стоит еще добавить к условию не только минимальность числа групп, но и однородность групп.
Можно попробывать применить кластер-анализ.

Сначала разбиение происходит по выше изложенному варианту, а потом вектора перераспределяются между полученными группами.
Можно почитать про метод кластеризации k-means.

Минимальное число групп и является наиболее однородным (вариант без артефактов имеет меньше групп, я вижу это тестируя в др. application - откуда пришли данные). Вариант с перераспределением видимо тупиковый - переливаниям не видно конца.

Первый шаг выглядит очень логичным: выделить "ноды". Берем первый вектор, создаем первую группу (хотя бы 1 группа всегда есть). Проверяем все остальные вектора - входят ли они в уже созданные группы? Если нет  - опять создаем новую группу. А вот что дальше - не соображу (пока).

Можно разбить минимально, но неоднородно.
 ++       ++++++
|++       +|++++|
хотя логичней
|++       |+++++|

Почитайте, может на какие мысли натолкнет
http://habrahabr.ru/blogs/data_mining/101338/

Стандартная проблема: вообще-то теория говорит умные вещи, но... трудновато использовать их для конкретной задачи  :)  Я сделал так:

1) Перебором нахожу хотя бы одну пару векторов угол между которыми превышает заданный. Если такой пары нет - то выход, все в 1 группе. Иначе создаю 2 группы

2) Цикл: перебором оставшихся нахожу все вектора которые не могут находится в уже имеющихся группах. Как только такой вектор найден - создаю новую группу

3) Цикл: перебором оставшихся нахожу "наилучший" вектор и группу в которую его добавить. Если найден, то добавляю его и опять выполняю "2" - могут возникнуть новые группы.  Если не найден, то первый из оставшихся - новая группа.

Результаты меня вполне устраивают, хотя, конечно, доказать минимальность/оптимальность я не могу. Заметим что реализовано в стиле "С", использование STL в данном случае пагубно  :)