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

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

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

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

Любые предложения?

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

Ответ 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;