Использование шаблона посетителя для обнаружения пересечения двух фигур

Я понимаю, что это очень специфический вопрос, поэтому было бы полезно, если бы ответ, который дают люди, включал в себя явные коды того, как это сделать. Спасибо.

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

class Shape
{
    .....
    virtual bool GetIntersection(Shape* _shape) = 0;
}

class Circle : public Shape  {...}
class Triangle : public Shape {...}

Оба этих производных класса переопределяют GetIntersection;

У меня есть:

//main.cpp
....
Shape* shape;
Shape* circle = new Circle;

if(input == 0) shape = new Circle;
else shape = new Triangle;

circle->GetIntersection(shape);

что дает ошибку.

Я читал что-то о шаблонах посетителей и думаю, что это может быть способом решить мою проблему, поскольку мне в основном нужно определить, какой производный класс использует параметр для GetIntersection. Может ли кто-нибудь объяснить, как мне реализовать шаблон посетителя для этого случая? Или если есть другое более простое решение этой проблемы.

Любая помощь будет оценена по достоинству.


person l3utterfly    schedule 08.07.2012    source источник
comment
Извините, я не имею в виду, что я получаю сообщение об ошибке, просто у меня возникла проблема. У меня нет возможности узнать, является ли рассматриваемая фигура кругом или треугольником, и у меня есть разные методы проверки пересечения для обоих.   -  person l3utterfly    schedule 09.07.2012


Ответы (4)


Я сейчас сталкиваюсь с той же проблемой с столкновениями между разными формами.

Я думаю, что мы не можем использовать шаблон Посетитель «как есть», потому что он требует, чтобы классы иерархии A (посетители) посещали классы другой иерархии B (посещаемые элементы), где классы B знают только об абстракции A (например, IVisitor), в то время как классы B знают о подклассах A (VisitedElement1, VisitedElement2... подклассы VisitedElement).

В нашем случае мы пытаемся посетить фигуры с помощью фигур, сохраняя при этом наш класс фигуры отделенным от подклассов, поэтому шаблон посетителя не применяется.

Лучшее решение, которое я могу придумать, это то, что класс Shape, напрямую или через другой интерфейс, объявляет методы "GetSpecificIntersection" для всех подтипов:

class Shape
{
    .....
public:
    virtual bool GetIntersection(Shape* _shape) = 0;    
protected:
    virtual bool GetSpecificIntersection(Circle* _circle) = 0;
    virtual bool GetSpecificIntersection(Triangle* _triangle) = 0;
}

class Circle
{
    .....
public:
    virtual bool GetIntersection(Shape* _shape);
    {
        return _shape->GetSpecificIntersection(this);
    }
protected:
    virtual bool GetSpecificIntersection(Circle* _circle) { ... }
    virtual bool GetSpecificIntersection(Triangle* _triangle) { ... }
}

class Triangle { /* analog to Circle */ }

Следовательно, вы должны реализовать эти конкретные методы пересечения для каждого типа фигуры с любым другим типом формы, а класс Shape связан со всеми возможными формами. Если я не ошибаюсь, это нарушает OCP, но сохраняет LSP.

Другой вариант, который я только что придумал, - это "предпочесть композицию наследованию" и сделать что-то вроде этого:

class Shape
{
    .....
public:
    virtual bool GetIntersection(Shape* _shape)
    {
        return _shape->figure->GetIntersection(this->figure);
    }

private:
    Figure* figure;
}

class Figure
{
    .....
public:
    virtual bool GetIntersection(Figure* _figure) = 0;
protected:
    virtual bool GetSpecificIntersection(Circle* _circle) = 0;
    virtual bool GetSpecificIntersection(Triangle* _triangle) = 0;
}

class Circle
{
    .....
public:
    virtual bool GetIntersection(Figure* _figure)
    {
        return _figure->GetSpecificIntersection(this);
    }
protected:
    virtual bool GetSpecificIntersection(Circle* _circle) { ... }
    virtual bool GetSpecificIntersection(Triangle* _triangle) { ... }
}

class Triangle { /* analog to Circle */ }

Это то же самое, что и раньше, но, делая это, вы отделяете свой класс Shape (который является интерфейсом, используемым классами вашей игры) от разных «фигур» (я не придумал лучшего имени), поэтому добавляя новый Цифры не должны даже приводить к перекомпиляции ваших клиентских классов. Это нарушает OCP только в иерархии "Рисунки" и сохраняет LSP как для "Формы", так и для "Фигура".

Если кто-то может предложить лучший способ сделать это, избегая понижения, я буду очень благодарен: D

person sergiou87    schedule 18.09.2012
comment
Большое спасибо за ответ. Я немного почитал после того, как написал свой вопрос, и понял, что использование шаблонов посетителей здесь практически нецелесообразно. Поэтому я решил воспользоваться вашим первым методом (который, кстати, кажется немного менее сложным, чем ваш второй). Спасибо за все время, которое вы потратили на написание такого длинного ответа, это очень ценно. - person l3utterfly; 20.09.2012
comment
В случае, если кому-то интересно, я отказался от своего первоначального плана иметь так много конкретных форм, которые ограничивают объекты в моем игровом движке, и вместо этого вернулся только к использованию выровненной по оси ограничивающей рамки для всего. Для определения пересечения требуется гораздо меньше усилий, и на самом деле гораздо быстрее выполнить очень быстрый (но широкий) тест пересечения между AABB и передать результат прямо в узкую фазу. Я надеюсь, что это поможет тем из вас, кто пытается обнаружить столкновения: не беспокойтесь о конкретных ограничивающих прямоугольниках. - person l3utterfly; 20.09.2012
comment
Пожалуйста! Я рад, что это полезно для вас :) (Могу ли я попросить +1 в моем ответе, пожалуйста? ха-ха) Как вы думаете, почему второй сложнее? Конечно, это добавляет новый шаг в процесс, но при этом вы отделяете свои клиентские классы от разных форм. Если вы добавите новую фигуру, при использовании второго метода вам не потребуется перекомпилировать классы, использующие фигуры. - person sergiou87; 20.09.2012
comment
Ну, я не знаю... Я думаю, это просто привычка программирования. Я предпочитаю использовать наследование. И одним классом меньше писать! :) (Кстати, я не думаю, что смогу поставить вам +1, потому что у меня недостаточно репутации... там написано, что для этого нужно 15. Извините. Но я отметил это как принятое отвечать.) - person l3utterfly; 21.09.2012


ваше решение правильное.

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

Затем, если есть столкновение, вы можете искать отдельные точки. Каждая фигура может возвращать точки или вектор своего контура, и вы можете легко узнать, есть ли коллизия или нет. Могут быть некоторые способы ускорить такие вещи, как легко узнать, находится ли точка внутри квадрата, или узнать, находится ли точка внутри круга, просто проверяя, что длина от точки до центра больше, чем радиус.

Затем вы можете сделать что-то вроде Shape { bool isPointInside(Point p) = 0; }

Что будет намного быстрее, чем проверка каждой отдельной точки.

Вы также можете переопределить getIntersection для круга, чтобы по-разному проверять квадраты и т. Д. Вместо только формы.

person Loïc Faure-Lacroix    schedule 08.07.2012
comment
Однако проблема в том, что у меня нет возможности заранее узнать, является ли фигура кругом или треугольником. Он должен иметь общий вид Shape*. Если я изменяю прототип функции GetIntersection(Shape* _shape) на GetIntersection(Circle* _circle) или GetIntersection(Triangle* _triangle), я получаю сообщение об ошибке, что нет подходящего преобразования из Shape* в Circle* или Triangle*. - person l3utterfly; 09.07.2012
comment
вы всегда можете вернуть набор точек для формирования вектора и проверить, находятся ли точки внутри или снаружи формы, образованной точками - person Loïc Faure-Lacroix; 09.07.2012
comment
но вы должны проверить с ограничивающей рамкой и, возможно, с ограничивающим кругом. а затем проверить баллы. Например, квадрат возвращает 4 точки, круг может возвращать много точек в зависимости от точности. скажем, 16 баллов достаточно. с двумя точками вы формируете вектор, и если вы создаете все вектора по часовой стрелке или против часовой стрелки, все нормали будут указывать либо внутри, либо снаружи формы, и вы можете выполнить некоторую векторную операцию, чтобы проверить, находится ли точка впереди или позади плоскости. вы можете создать точку x, y, z, используя x, y, 1, поскольку z не имеет большого значения. Он просто там, чтобы сделать некоторые геометрические операции - person Loïc Faure-Lacroix; 09.07.2012

Вы можете использовать f.x. dynamic_cast<Circle *>(shape) чтобы узнать, является ли фигура кругом. Он возвращает null, если shape не является Circle, в противном случае — действительный указатель на экземпляр Circle.

Используйте это, если один из ваших методов GetInserection знает, как пересекаться с определенным другим подтипом Shape.

Кроме того, следуйте рекомендациям из ответа Loïc Faure-Lacroix.

person Arne    schedule 09.07.2012