Индексы объектов в списке не избыточных пар

Я реализую алгоритм обнаружения столкновений, хранит расстояние между всеми объектами в одном узле октодерева. Например, если в узле 4 объекта, между объектами есть расстояние 1&2, 1&3, 1&4, 2&3, 2&4 и 3&4. Формула для общего количества пар имеет вид t = n * (n-1) / 2, где t — общее число Парижа, а n — количество объектов в узле.

У меня вопрос, как мне преобразовать позицию в списке в пару объектов? Например, используя приведенный выше список пар, 3 вернет пару 2&3.

Чтобы сэкономить место в памяти, список представляет собой просто список с плавающей точкой для расстояния, а не содержит расстояние и указатели на 2 объекта.

Я не уверен, как математически преобразовать индекс одного списка в пару чисел. Любая помощь будет отличной. Я надеюсь, что смогу разбить это на 2 функции, первая возвращает первый объект в паре, а вторая возвращает второй, обе функции принимают две переменные, одна из которых является индексом, а другая — общим количеством объектов в узел. Если возможно, я бы хотел создать функцию без зацикливания или с рекурсивной функцией, потому что она будет выполняться в реальном времени для моего алгоритма обнаружения столкновений.

1

Решение

Исходя из моего понимания вопроса, один из способов получить пару&б (1 на основе, 2&3 в вашем примере) из индекса (на основе 0, 3 в вашем примере) и количества объектов n (4 в вашем примере):

t = n * (n - 1) / 2;
a = n - floor((1 + sqrt(1 + 8 * (t - index - 1))) / 2);
b = index + (n - a) * (n - a + 1) / 2 - t + a + 1;

Некоторые кредиты http://oeis.org/A002024

Обобщенные алгоритмы (для кортежей, а не пар) можно найти на Рассчитать комбинацию на основе позиции а также http://saliu.com/bbs/messages/348.html, но они, кажется, включают вычисление комбинаций в цикле.

Редактировать: более приятная формула для (из того же источника):

a = n - floor(0.5 + sqrt(2 * (t - index)));
2

Другие решения

Я предлагаю использовать Коллексографический порядок, как в этом случае вам не нужно указывать общее количество объектов. Заказать ваши пары, как это:

 0:   1:   2:   3:   4:   5:   6:   7:   8:   9:  10:  11:  12:  13:  …
0&1, 0&2, 1&2, 0&3, 1&3, 2&3, 0&4, 1&4, 2&4, 3&4, 0&5, 1&5, 2&5, 3&5, …

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

Вы также можете визуализировать упорядочение коллекса следующим образом:

 a: 0  1  2  3  4  5 …
b:
1   0
2   1  2     index of
3   3  4  5       a&b
4   6  7  8  9
5  10 11 12 13 14
6  15 16 17 18 19 20
⋮   ⋮                 ⋱

Давайте сначала превратим пару в единый индекс. Хитрость в том, что для каждой пары вы смотрите на вторую позицию и представляете все пары, у которых в этой позиции было меньшее число. Так например для пары 2&4 сначала вы подсчитываете все пары, у которых второе число меньше 4. Это число возможных способов выбрать два элемента из набора из 4 (то есть чисел от 0 до 3), чтобы вы могли выразить это как биномиальный коэффициент 4C2 , Если вы оцените это, вы получите 4 (4−1) / 2 = 6. К этому вы добавляете первое число, так как это число пар с меньшим индексом, но с тем же номером во втором месте. За 2&4 это 2, поэтому общий индекс 2&4 4 (4−1) / 2 + 2 = 8.

В общем, за пару &б индекс будет б(б-1) / 2 +.

int index_from_pair(int a, int b) {
return b*(b - 1)/2 + a;
}

Один из способов включить единый индекс я обратно в пару чисел будет увеличиваться б до тех пор б(б+1) / 2> я, то есть ситуация, когда следующее значение б приведет к индексам больше, чем я. Тогда вы можете найти как разница знак равно яб(б-1) / 2. Этот подход путем увеличения б один за раз включает в себя использование цикла.

pair<int, int> pair_from_index(int i) {
int a, b;
for (b = 0; b*(b + 1)/2 <= i; ++b)
/* empty loop body */;
a = i - b*(b - 1)/2;
return make_pair(a, b);
}

Вы могли бы также интерпретировать б(б−1) / 2 = я как квадратное уравнение, которое вы можете решить, используя квадратный корень. Реальный б вам нужен пол с плавающей точкой б вы получите в качестве положительного решения этого квадратного уравнения. Поскольку при таком подходе вы можете столкнуться с проблемами из-за ошибок округления, вы можете проверить, б(б+1) / 2> я. Если это не так, приращение б как вы сделали бы в циклическом подходе. Когда у вас есть б, вычисление остается такой же.

pair<int, int> pair_from_index(int i) {
int b = (int)floor((sqrt(8*i + 1) + 1)*0.5);
if (b*(b + 1)/2 <= i) ++b; // handle possible rounding error
int a = i - b*(b - 1)/2;
return make_pair(a, b);
}

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

for (int = 0; i < n*(n - 1)/2; ++i) {
pair<int, int> ab = pair_from_index(i);
int a = ab.first, b = ab.second;
// do stuff
}

тебе лучше написать

for (int i = 0, b = 1; b != n; ++b) {
for (int a = 0; a != b; ++a) {
// do stuff
++i;
}
}
4

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector