улучшение при обнаружении столкновений

Question

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

Мои функции заключаются в следующем: Это функция, которая будет на самом деле называется на объекте:

bool ScreenObject::intersects(ScreenObject & a,ScreenObject & b) { 
    if(inter(a,b)) 
     return true; 
    else 
     return inter(b,a); 
} 

и это интер:

bool inter(ScreenObject & a,ScreenObject & b) { 
    if(a->getsx()>b->getsx()) { 
     if(a->getsx()<b->getSxmax()) { 
      if(a->getsy()>b->getsy())) { 
       if(a->getsy<b->getSymax()) { 
        return true; 
       } 
      } else { 
       if(b->getsy()>a->getsy())) { 
        if(b->getsy<a->getSymax()) { 
         return true; 
        } 
       } 
      } 
     } 
    } 
    return false; 
} 

getsx/getsy возвращает минимальное значение x/y (т.е. нижний левый угол объекта), тогда как getSxmax/getSymax возвращает максимум. Мой вопрос в том, есть ли способ сделать этот код лучше, поскольку в настоящее время это выглядит довольно плохо выполненным.

Answer 1

Вы правы. Это довольно грязно. Вы хотите, чтобы отслеживать прямоугольную степень каждого объекта:

typedef struct range { int min, max; } RANGE; 
typedef struct bb { RANGE x, y; } BOUNDING_BOX; 

Ключ операции является, чтобы найти, что есть нет перекрытия в одном измерении, определяя, что объект А должен лежать на любой стороне B. Это дизъюнктность :

bool disjoint(RANGE *a, RANGE *b) { return b->max < a->min || b->min > a->max; } 

Теперь мы можем использовать это дважды, чтобы найти там нет совпадения в 2d:

bool disjoint(BOUNDING_BOX *a, BOUNDING_BOX *b) { 
    return disjoint(&a->x, &b->x) || disjoint(&a->y, &b->y); 
} 

конечно же столкновения является Logica l дополнение непересекающихся, по крайней мере для прямоугольных объектов.

Для других форм вы все равно можете использовать прямоугольные экстенты, чтобы устранить большую часть затрат на испытания на столкновение. Если экстенты не пересекаются, вы уверены, что нет столкновения. Если они не пересекаются, то вы должны выполнить более дорогие тесты для столкновения общих полигонов. Существует некоторая основная информация here. Но есть несколько больших книг по этой теме.

Для @ DanielKO, которому не нравятся условные обозначения C, хотя они выражают вычисления более кратко, чем OO для этого вопроса; также опуская конструктор и другие шаблонного:

class Extent { 
    public: 
    bool isDisjointWithRespectTo(Extent &other) { 
     return max < other.min || other.min > max; 
    } 
    private: 
    int min, max; 
} 

class BoundingBox { 
    public: 
    bool isDisjointWithRespectTo(BoundingBox &other) { 
     return x.isDisjointWithRespectTo(other.x) || y.isDisjointWithRespectTo(other.y); 
    } 
    bool intersectsWith(BoundingBox &other) { return !isDisjointWithRespectTo(other); } 
    private: 
    Extent x, y; 
} 

Конструкторы должны убедиться, что min и max правильно заказать в обеих версиях.