Реализация абстрактного метода «перекрытий» для разных фигур?

Question

У меня есть абстрактный базовый класс под названием Shape, который выглядит примерно так:

class Shape { 
    public: 
     Shape(Point center); 
     virtual bool overlaps(Shape *other) = 0; 

    private: 
     Point m_center; // has getter&setter 
}; 

У меня возникли проблемы с методом overlaps(Shape *other);; Я не знаю, как реализовать его в подклассах.

Давайте рассмотрим два примера: (возможно, у меня будет не более двух или трех форм) Circle и Rect. В основном то, что я пытался это создать две перегрузки в обоих классах после того, как с использованием прямого заявления, чтобы позволить Circle и Rect «знать» друг с другом:

virtual bool Rect::overlaps(Circle *other); 
virtual bool Rect::overlaps(Rect *other); 
virtual bool Circle::overlaps(Circle *other); 
virtual bool Circle::overlaps(Rect *other) { return other->overlaps(this); } 

Теперь легко реализовать математику внутри всех перегрузках ; однако, я получу ошибку cannot allocate an object of abstract type 'Circle' и note: virtual bool Unit::overlaps(Unit *). Это связано с тем, что классы Circle и Rect имеют только методы с Circle * и Rect * в качестве их параметров, но без Unit *.

Я также попытался вперед declarating Circle и Rect в моем shape.h, но так как вперед заявление не являются одними и теми же классами, как мой фактический Circle и Rect, я только получаю ту же ошибку.

Не удаляя общий базовый класс, существует ли способ реализовать такое поведение? Или есть обходное решение, чтобы заставить его работать?

Дополнительная информация

У меня есть 2D World класс, который содержит vector<Shape *> m_shapes; и мне нужно будет увидеть, если две фигуры накладываются друг на друга;

for (unsigned int i = 0; i < m_shapes.size(); i++) { 
    if (certainShape->overlaps(m_shapes[i])) { 
     collapse(); 
    } 
} 

Answer 1

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

Существует несколько распространенных способов реализации двойной отправки в C++: например, вы можете использовать visitor pattern или создать карту на основе RTTI. Выбор того или другого зависит от вас.

Если вы решили пойти с шаблоном посетителя, вы делаете Shape «посещением», добавляя метод посещения.

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

#include <iostream> 
using namespace std; 

class ShapeVisitor; 

struct Shape { 
    virtual void accept(ShapeVisitor& v) = 0; 
    virtual bool overlaps(Shape& other) = 0; 
}; 

class Circle; 
class Square; 

struct ShapeVisitor { 
    virtual void visitCircle(Circle& c) = 0; 
    virtual void visitSquare(Square& s) = 0; 
}; 

// These three methods do the actual work 
bool checkOverlap(Square& s, Circle& c) { 
    cout << "Checking if square overlaps circle" << endl; 
    return false; 
} 
bool checkOverlap(Square& a, Square& b) { 
    cout << "Checking if square overlaps square" << endl; 
    return false; 
} 
bool checkOverlap(Circle& a, Circle& b) { 
    cout << "Checking if circle overlaps circle" << endl; 
    return false; 
} 

class Square : public Shape { 
    struct OverlapVisitor : public ShapeVisitor { 
     OverlapVisitor(Square& _my) : result(false), my(_my) {} 
     virtual void visitCircle(Circle& c) { 
      result = checkOverlap(my, c); 
     } 
     virtual void visitSquare(Square& s) { 
      result = checkOverlap(my, s); 
     } 
     bool result; 
     Square& my; 
    }; 
public: 
    virtual void accept(ShapeVisitor& v) { 
     v.visitSquare(*this); 
    } 
    virtual bool overlaps(Shape& other) { 
     OverlapVisitor v(*this); 
     other.accept(v); 
     return v.result; 
    } 
}; 

class Circle : public Shape { 
    struct OverlapVisitor : public ShapeVisitor { 
     OverlapVisitor(Circle& _my) : result(false), my(_my) {} 
     virtual void visitCircle(Circle& c) { 
      result = checkOverlap(my, c); 
     } 
     virtual void visitSquare(Square& s) { 
      // Important: note how I switched the order of arguments 
      // compared to Square::OverlapVisitor! There is only one 
      // square/circle overlap function checker, and it expects 
      // the square to be the first argument. 
      result = checkOverlap(s, my); 
     } 
     bool result; 
     Circle& my; 
    }; 
public: 
    virtual void accept(ShapeVisitor& v) { 
     v.visitCircle(*this); 
    } 
    virtual bool overlaps(Shape& other) { 
     OverlapVisitor v(*this); 
     other.accept(v); 
     return v.result; 
    } 
}; 

Вот это работает demo on ideone.

С RTTI подходом вы бы сделать map<pair<type_info,type_info>,checker> где шашка тип функции, которая принимает два указателя на Shape, и возвращает true или false в зависимости от того, или не перекрывают друг друга формы. Вы делаете одну такую ​​функцию для каждой пары типов объектов, заполняете карту указателями на эти функции на основе type_info их ожидаемых типов параметров и используете эту карту во время выполнения, чтобы вызвать нужную функцию.

В статье 31 книги More Effective C++ подробно объясняются оба этих подхода, с некоторыми замечательными примерами. Фактически, пример использования, описанный в книге, обнаруживающий столкновения между двумя игровыми объектами, аналогичен тому, который вы реализуете.

Answer 2

Что вам нужно, это «насколько велика other» функция типа. Если мы сделаем это очень простым и просто используем ограничивающий прямоугольник (прямоугольник, который достаточно велик, чтобы покрыть всю форму), мы могли бы сделать что-то вроде этого:

(Для упрощения я использую rect как срок для прямоугольника)

class Shape 
{ 
... 
virtual rect BoundingBox() = 0; 

bool overlaps(const Shape& other) 
{ 
    return BoundingBox.FitsInside(other.BoundingBox()); 
} 

};

Очевидно, что вам нужно будет написать функцию fitsinside для двух прямоугольников и BoundingBox для каждой формы, но это не должно быть слишком сложно.

Чтобы сделать «это Star полностью покрыто этим Oval?» делает несколько более сложное решение [вам нужно будет иметь полный контур обеих фигур, а контур Oval может быть довольно точным, чтобы быть точным овалом].

Answer 3

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

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

Теперь этот простой подход медленный, особенно если вы имеют много форм. Решение заключается в использовании более дешевого алгоритма для проверки того, необходим ли идеальный алгоритм. Прямоугольная рамка - самый дешевый способ. Выработайте координаты прямоугольника, который достаточно велик, чтобы удерживать вашу фигуру. Я не знаю, как это сделать для круга (геометрия - не мой сильный костюм). Вы даже можете кэшировать размеры рамки в классе, чтобы предотвратить пересчет для сложных фигур. Проверка того, перекрываются ли два прямоугольника, очень быстро и просто.

Только тогда перейдите на дорогостоящий алгоритм, если ограничивающие поля перекрываются.

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