Индексы объектов в списке не избыточных пар
Я реализую алгоритм обнаружения столкновений, хранит расстояние между всеми объектами в одном узле октодерева. Например, если в узле 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 на основе, 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)));
Другие решения
Я предлагаю использовать Коллексографический порядок, как в этом случае вам не нужно указывать общее количество объектов. Заказать ваши пары, как это:
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;
}
}