Russian Qt Forum

Добрый день

Столкнулся с проблемой деления неравномерно распределенных данных. Пример для одномерного случая. Пусть есть N точек отсортированных по их значениям (допустим от 0 до 200). "Неравномерность" выглядит так

интервал значений                кол-во точек в интервале
-------------------------------------------------------------
0..1                                      1
1..2                                      0
2..3                                      0
3..4                                      1
4..5                                      1
..
100..101                                  0               // и.т.д - интервалы почти пустые
101..102                                  10000           // бум!
102..103                                  1               // опять пошли почти пустые интервалы
103..104                                  1                  
...
199..200                                  0

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

Если Вы знаете формулировку в теории - подскажите, буду благодарен

По длине чего? Общего интервала(0..200 в данном примере)?

Что значит глубина разбиения. Кол-во интервалов?


Не понятно что нужно делить, требует пояснения.

Задача построить дерево, конкретно BSP дерево (да, то самое что мы обсуждали в др. нитке). У дерева есть ветки и листья. Ветка хранит 2 указателя на children, каждый из которых может быть веткой или листом. Также ветка хранит divider - значение как делить (по расстоянию). Листья хранят указатели на конечные данные - для простоты пусть это одномерные значения. Пример: найти все точки в интервале [10..11].

- проверяем пересекает ли интервал общий (0..200)
- смотрим корень, это ветка разбивающая на 2 интервала (0..100) и (100..200). Значит идем по первой ветке.
- продолжаем спуск пока не оказались в листе. Здесь просто перебираем все точки принадлежащие листу

Глубина деления есть число шагов спуска. Деление останавливается если число данных в листе достаточно мало. Однако есть точки которые полностью совпадают (напр. 100 точек в 1 месте). Такое можно делить бесконечно но безуспешно. Поэтому глубина деления ограничена.

Одномерный случай приведен просто для простоты изложения - конечно для него проще сделать двоичный поиск по сортированному массиву. Но это не проходит для 2 и более измерений.

"Стремящийся поиск" что-то в этом роде.

Опять не совсем понятно.
Для начала приведи пример чисто для 1-мерного случая. Пример данных, процесс деления.
Затем уже будем разбирать многомерный(сколько измерений, есть ограничение?)
======

Если все же я правильно понял, то для одномерного случая:


Указываем не кол-во точек в интервале, а накопленные суммы:

Тогда бинарным поиском легко можно сделать разбивку по кол-ву точек. А кол-во точек в итервале - разница текущего со значением в предыдущем

У меня всегда 3 измерения (x. y. z). Но задача столь же актуальна для 2-х. Представим напр огромную карту местности, почти пустую, но с маленьким участком "город". Там и сосредоточено 99.99% всех данных, остальное огромная "пустыня". В этом случае деление пополам (кстати так делает и Qt) плохо - мы будем лупить и лупить большие площади, не останется памяти/ресурсов на город

Делал, получается неважно. Во-первых для 2-х и более измерений нужно все время сортировать точки при смене оси деления - не смертельно но неприятно. А главное - резко нарастает глубина спуска, такое "теоретически правильное" дерево работает медленно. Пример: ищем точку 1.5 (для данных описанных выше). Спуск будет выглядеть так:

1) (0 - 101.5)(101.5 - 200)
2) (0 - 101.25)(101.25 - 101.5)
3) (0 - 101.125)(101.123 - 101.25)
4) (0 - 101.120)..
5) (0 - 101.115)..
6) (0 - 101.110)..
... и.т.д

В 2-х и 3-х измерениях это становится невыносимым - нужно добираться по каждой из осей. Поэтому хотелось бы "локализовать" области с большой плотностью данных и заниматься ими отдельно.

Области с большей плотностью данных можно выделить кластерным анализом.

Конечная задача какая? Найти все точки в заданном интервале?

Пока рассмотрим только одномерный случай.
Диапазон 0-99
Имеем 12 точек  {0, 0, 4, 15, 15, 15, 15, 33, 33, 48, 75, 76}

1) Имеем равномерные интервалы размером 10 с полной разбивкой, тогда получаем
===
интервал   точек  суммы
===
1                3         3
2                4         7
3                0         7
4                2         9
5                1         10
6                0         10
7                0         10
8                2         12
9                0         12
10              0          12
===
Бинарным поиском по суммам легко сделать разбиение  на два под-интервала.
Например 50/50 - ищем сумму 12/2 = 6 :
[0-19] - 7 точек;
[20-99] - 5 точек;

2) Имеем равномерные интервалы размером 10 с не полной разбивкой - выкинуты вернее не внесены пустые.
получаем
===
интервал   точек  суммы
===
1                3         3
2                4         7
4                2         9
5                1         10
8                2         12
===
Все точно так же, только меньше мусора

3) Имеем неравномерные интервалы например минимум 2 точки с минимальным размером 10 и кратным 10
получаем

===
интервал   точек  суммы
===
0  - 9              3         3
10-19              4         7
30-39              2         9
40-80              3         12
===

Конечная задача с помощью построенного дерева находить полигоны на пути луча. Чтобы не вдаваться в предметную область, проще сказать что нужны:

а) хорошо сбалансированное дерево
б) быстрый спуск по нему

Как я пытался объяснить выше, при неравномерном распределении данных "а" и "б" конфликтуют

Так я об этом и спрашиваю  :)

Если у меня точки отсортированы по значению, то проще взять среднее между точками N/2 и N/2 + 1. Это проверялось, такое дерево работает медленно (и строится тоже). Хотелось бы вот так (* большая плотность, - маленькая)

    1             2                         3
             |*****|
---------|*****|-----------------------------------
             |*****|

Заметим, что интервалы не равны ни по расстоянию, ни по числу данных

Нужен алгоритм кластер-анализа?
Можно почитать тут (http://www.nsu.ru/matlab/MatLab_RU/fuzzylogic/book2/1/subclust.asp.htm) изложен кратко кластер анализ с удалением. Центры кластеров с его окрестностями и будут искомыми скоплениями. Если надо могу исходник из Matlab скинуть.

А можно ли дробить и\или объединять интервалы? Чтобы можно было оперировать сбалансированными (по количеству точек) интервалами.

Кластерный анализ здесь ни причем, хотя данную задачу можно решить с его помощью, поскольку она является подмножеством подобных задач (простой случай). Применять кластерный анализ здесь неэффективно.
Области с повышенной плотностью однородных данных можно выделить и более простыми и эффективными способами.

3-й вариант и был с неравными интервалами.
Без более четкого описания задачи: исходные данные, их структуры, принципы разделения, выходные структуры - тяжело что-то оптимизировать.
Это все слишком абстрактно и неоднозначно.
Попробуй более формально описать все это, начиная с простого одномерного случая. Если что выходи завтра на связь по Skype, обсудим.

мне кажется, что хоть тема и хорошая, но более подробно она обсуждалась (обсуждается и будет обсуждаться) на gamedev.ru

Спасибо, изучаю/вникаю

Ограничений нет, все данные на руках, можно оперировать чем угодно - но нужны идеи что делать (или теория)

Хорошо, давайте попробуем сформулировать кратко, не беда если повторюсь

1) Данные распределены неравномерно, в относительно маленьких участках (от общего пространства) может быть сконцентрирована их подавляющая масса. К слову сказать, достигается это очень просто: напр сделал пользователь какую-то модель вазы. 100 тысяч точек и она влазит в кубик 1х1х1. А потом сделал пол для нее - вот в нем аж 10 точек, зато размер 1000x1000 - готово!

2) Делить по размеру (расстоянию) плохо, вся сила дерева уходит на деление больших площадей

3) Делить по числу точек - тогда "дерево сбалансировано" но другая беда - медленный спуск (и медленное построение)

4) Возникает мысль разделить области с большой и малой плотностью.

Не очень понятно

>> Имеем неравномерные интервалы например минимум 2 точки с минимальным размером 10 и кратным 10
получаем

Да, я могу строить любые гистограммы (если я правильно употребляю этот термин), ну и что с ними делать? Напр. получил что-то такое (число данных в интервалах)

1, 5, 10, 100, 1, 200, 1, 2. 1000, 500, и.т.д

Как выбрать место деления? Из каких соображений выбирать длину интервалов?

Насколько я знаю, в играх эта проблема решается вручную (т.е. разработчик указывает кластера руками). Также некоторые утверждают что для таких ситуаций BSP не годится вообще и следует использовать octree. Однако я могу ошибаться, поэтому буду благодарен за наводки/ссылки.

Это понятно, и давно :)


Это понятно.


А это не понятно, особенно выделенное.


По сути не отличается от деления по кол-ву точек, с  интервалами разного размера.


Не понял!!!
Так есть хоть какой-то критерий разделения. Можно на примере выше, например вложенными круглыми скобками.

Да, поделить по числу точек можно, получится сбалансированное дерево. Да, для такого дерева поиск log2(N) операций - для любого запроса. И это было бы прекрасно - для поиска тех самых точек которые использовались для построения дерева. Но вот напр "найти все точки в радиусе R от заданной" - и, как ни странно, сбалансированное дерево работает плохо. Для любой точки будет выполняться напр 20 спусков, как если бы все пространство было равномерно заполнено. Очевидно что если бы в примере "ваза стоит на полу" мы бы использовали 2 дерева (одно для вазы, др. для пола) то для всех точек пола (которые запрашиваются) мы бы нашли соседей намного быстрее.

Я такой критерий и ищу. Вот максимально упрощенный пример

Длина      Число точек
---------------------
(0-8)        1
(8-11)      100
(11-100)     1

Здесь все ясно, разбиваем на 3 интервала, как они записаны в левом столбце. Но откуда их взять, ведь у меня никаких интервалов (еще) нет, я только могу их создавать используя сортированный массив. И плотности могут быть совсем не такими красивыми и круглыми как в примере. Мне надо как-то поймать ситуацию "скопление", а если ее нет, то не мудрствуя лукаво, делить пополам по длине.

Это уже другая задача. И зачем вообще использовать дерево!
Опять все та-же таблица:
интервал   точек  суммы  упорядоченные
                                     списки точек в интервале
1                3         3          *
2                4         7          *
4                2         9          *
5                1         10        *
8                2         12        *   

C*log(N) для любого запроса, в том числе и нахождения интервала где точки отстоят от заданной на расстоянии R+/-Delta. Delta зависит от способа построения таблицы, в пределах Delta прямой перебор точек. Если нет ограничения на кол-во записей в таблице, то Delta == 0 и понятие интервал исчезает - вместо него получаем координату точки и ее кратность.

Мне до сих пор мне не понятно для чего строиться дерево! Какие операции(запросы) будут с ним делаться далее. Какая частота этих операций, их кол-во, ... От этого все зависит. Отимизировать построение необходимо по конкретное использование получаемых данных.

Совершенно верно, для 1-мерного случая проще обойтись поиском  :), я об этом говорил в первом посте. Но это не распространяется на 2 и более измерений. В 2 измерениях (на плоскости) дерево выглядит как прямоугольники, который разбиваются на дочерние прямоугольники. Использование такого дерева:

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

3-х мерный случай ничем не отличается, проблема общая для любой размерности.

а я бы предложил другую схему.
обычно она как раз применяется в играх. но если делается 3д дизайнерский софт, то применить тоже логично и не сложно.
У нас имеется 3д пространство с 3д объектами.
Начнём с того, что каждый объект мы кладём в ббокс.
Ббокс = boundary box = bbox.
тем самым мы без проблем сможем находить с каким глобальным объектом пересёкся луч (например, траеторию пули моделируем с повреждением объектов) - быстро получили (к примеру) стол, стул и пол.
Допустим, каждый из этих объектов у нас весьма и весьма полигональный (ну пусть будет под 10000 полигонов каждый).
Разумеется, перебирать каждый для поиска луча - офигеешь.
ну в таком случае мы заранее определяем 2-3 уровня внутренних ббоксов типа "дерево" к последнему уровню которых привязаны реальные полигоны. к примеру, ббокс 1 будет состоять из 50 полигонов  - перебрать не сложно. находим нужные полигоны, и от них деревом берём ещё штук 50 полигонов ббокса 2 уровня, чекаем их, и там уже по дереву чекаем последние реальные полигоны для поиска нужного.

Вроде неплохо, но, на самом деле, тут будут и свои особенности.
Например при разработке игры нам требуются модельки монстриков, которым можно отдельно отстреливать конечности.
В самом начале мы отдаём дизайнерам задание - при разработке моделей определять им дополнительные ббоксы, и написать небольшую утилитку, которая будет перегонять эти модельки с ббоксами в удобоваримый рендеру-физике-движку вид.
Таки образом траектория пули определяется просто:
пересечение с глобальным ббоксом монста? - ок. понеслась.
пересечение с ббокс "голова"? - нет. дальше
пересечение с ббокс "рука"? - ок. понеслась.
пересечение с ббокс "локоть"? - нет. дальше
пересечение с ббокс "плечо"? - да.
для плеча ищем нужный полигон, рисуем на нём дырку, модифицируем как-то, если надо, заодно по всем полигонам  в группе "рука" накладываем текстуры кровяки (а точнее просто переключаем модель), в AI ставим флаги "невозможность действовать правой рукой кроме как дубиной" и радуемся жизни =) главная задача - это корректное разбиение по ббоксам внутреннего уровня - ну за этим уже следить сразу надо.

если же у нас не игра а 3д редактор, то нужно писать алгоритм (но с моей точки зрения не очень сложный) добавления объектам ббоксов.
алгоритм должен учитывать размер полигонов, туда включённых, или какие-то пользовательские группировки полигонов..
зато всё это настроить и сделать вполне реально и работать будет хорошо. =)
вполне возможно, что в большинстве случаев математический поиск сведётся всего лишь к перебору ббоксов, и до полигонов не дойдёт.

Вводим дополнительную индексацию прямоугольников. Для двумерного случая например сетка 100*100. Каждый элемент сетки так или иначе ссылается на  прямоугольники пересекающихся с ним. Нахождение элементов сетки пересекаемых лучем простое вычисление. Елементы сетки для оптимизации поиска и хранения индексов прямоугольников в них могут иметь разные типы, например: пустая, простой короткий список прямоугольников, список точек, дерево некоторого типа, подсетка, итд.

Я Вас прекрасно понял. Дело в том что мой случай "общий", я не могу делать никаких предположений. Да, сцена всегда сгруппирована по объектам и  эта информация мне известна. Но работать только по ббоксам - не проходит. Тысяча и более объектов в сцене - рядовой случай. 10-20 тысяч - тоже никого не удивишь. Так что даже перебор ббоксов может быть медленным.

Разумно выбирать делители на границе ббоксов объектов. Но тут начинается масса частных случаев. Объект может иметь мало полигонов, тогда деление по его границе ничего не даст. Или ббокс "закопан" в другие ббоксы. Словом, реализация получается хлопотливая. "Одно дерево на всех" намного проще.

Ну эта сетка выглядит ненужной надстройкой над деревом  :)  Если у нее много (полу) пустых ячеек - их придется все равно перебирать на пути луча

Добрый день

В общем нашел я решение. Алгоритм

- делю пополам по расстоянию
- смотрю сколько попало в левую и правую части. Нахожу отношение t = min/max. Если t > 0.1, все хорошо, приступаю к делению получившихся нодов. Иначе сдвигаю делитель в нужную сторону и повторяю деление. И так 8 раз, выход если t > 0.1

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

Спасибо всем принявшим участие в обсуждении, особенно Spectre. Как говорил мой старый друг "идеи приходят от общения"  :)