Структура данных и алгоритм обнаружения столкновений движущихся объектов неправильной формы

Я наткнулся на этот вопрос интервью

Многие объекты неправильной формы движутся в случайных направлениях. Предоставьте структуру данных и алгоритм для обнаружения коллизий. Помните, что количество объектов исчисляется миллионами.

Я предполагаю, что каждый объект будет иметь координаты x и y. Другие предположения приветствуются. Я полагаю, также следует использовать определенный тип дерева, но я ничего не знаю об алгоритме.

Какие-либо предложения?


algorithm data-structures
person garima    schedule 22.03.2011    source источник
comment
Я бы ожидал, что эти объекты будут иметь более одной координаты x и y, а не только одну, как вы упомянули/ожидаете. Вы написали вопрос дословно? Думаю, нет, так как некоторые детали отсутствуют, ИМО. Например, что такое неправильная форма?   -  person Bart Kiers    schedule 22.03.2011

Ответы (4)


arrow_upward
3
arrow_downward

Я бы посмотрел на алгоритм развертки плоскости или Алгоритм Бентли-Оттмана. Он использует развертку плоскости, чтобы определить во времени O(n log(n)) (и в пространстве O(n)) пересечение линий на евклидовой плоскости.

person Nico Huysamen    schedule 22.03.2011
comment
пересечение неправильной формы и линии? Это может быть решение в 2D, но вы можете добиться большего, чем O (n log n). В 3D не работает. - person knivil; 22.03.2011
comment
@knivil - Алгоритм может быть расширен для работы в трехмерном пространстве, поэтому он называется разверткой PLANE, а не разверткой по линии. Алгоритмы были для справки. - person Nico Huysamen; 22.03.2011

arrow_upward
2
arrow_downward

Скорее всего, вы хотите разделить плоскость с помощью заполняющей пространство кривой, такой как z-кривая или кривая Гильберта, и, таким образом, уменьшить сложность 2D-задачи до 1D-проблемы. Ищите квадродерево.

Ссылка: http://dmytry.com/texts/collision_detection_using_z_order_curve_aka_Morton_order.html

person Gigamegs    schedule 22.03.2011

arrow_upward
1
arrow_downward

Есть много решений этой проблемы. Первое: используйте ограничивающие рамки или круги (шарики в 3D). Если ограничивающие прямоугольники не пересекаются, то дальнейшие тесты не нужны. Второе: разделите свое пространство. Вам не нужно проверять каждый объект против всех других объектов (то есть O (n ^ 2)). Вы можете иметь среднюю сложность O (n) с деревьями квадрантов.

person knivil    schedule 22.03.2011

arrow_upward
-2
arrow_downward

Я предполагаю, что должен быть цикл, который берет ссылку на координаты поиска 1 объекта, а затем проверяет остальные объекты, чтобы увидеть, есть ли какое-либо столкновение. Я не уверен, насколько хорошо мое решение для миллионов объектов. Псевдокод:

For each irregular shaped object1    

int left1, left2;
int right1, right2;
int top1, top2;
int bottom1, bottom2;
bool bRet = 1; // No collision

left1 = object1->x;
right1 = object1->x + object1->width;
top1 = object1->y;
bottom1 = object1->y + object1->height;

For each irregular shaped object2
{
    left2 = object2->x;
    right2 = object2->x + object2->width;
    top2 = object2->y;
    bottom2 = object2->y + object2->height;

    if (bottom1 < top2) bRet =0;
    if (top1 > bottom2) bRet = 0;

    if (right1 < left2) bRet = 0;
    if (left1 > right2) bRet = 0;
}

return  bRet;
person Hiren    schedule 22.03.2011
comment
Не знаю, насколько «неправильные» эти формы. Больше похоже на прямоугольники. - person gablin; 22.03.2011
comment
приведенный выше алгоритм NatashaD совершенно неверен, не следуйте ему. Вам нужно указать диапазон объектов и проверить, находится ли диапазон obj1 в диапазоне obj2, и наоборот, тогда столкновение не произошло. - person Jawad Amjad; 27.09.2011