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

Question

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

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

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

Есть предложения?

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

Я предполагаю, что должен быть цикл, который берет ссылку на 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;