2

我有一个名为 的抽象基类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 *). 这是因为 myCircle和Rectclasses 只有带有Circle *和Rect *作为参数的方法，而没有带有Unit *.

我也尝试在我的shape.hCircle中前向声明and ，但由于前向声明与我的实际and类不同，我只会得到相同的错误。RectCircleRect

在不删除公共基类的情况下，有没有办法实现这种行为？或者有没有办法让它工作？

附加信息

我有一个 2DWorld类，其中包含vector<Shape *> m_shapes;我需要查看两个形状是否相互重叠；

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

3 回答 3

6

欢迎多发！本质上，您要求一种相对于多个对象的运行时类型是虚拟的方法 - 在您的情况下，两个形状的类型被测试是否重叠。

在 C++ 中实现双重调度有几种常见的方法：例如，您可以使用访问者模式，或者基于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;
    }
};

这是ideone 上的运行演示。

使用 RTTI 方法，您将创建一个map<pair<type_info,type_info>,checker>where 检查器是一种函数类型，它接受两个指向 的指针，并根据形状是否重叠Shape返回true或。false您为每一对对象类型创建一个这样的函数，根据type_info预期的参数类型使用指向这些函数的指针填充映射，并在运行时使用此映射来调用所需的函数。

《更有效的 C++ 》一书的第 31 项深入解释了这两种方法，并提供了一些很好的示例。事实上，书中讨论的用例检测一对游戏对象之间的碰撞，与您正在实施的用例相似。

于 2013-07-16T11:14:36.827 回答
1

你需要的是一个“有多大other”类型的函数。如果我们让它变得非常简单，并且只使用一个边界框（一个大到足以覆盖整个形状的矩形），那么我们可以这样做：

（为简单起见，我使用rect矩形的术语）

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

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

};

显然，你必须fitsinside为两个矩形和BoundingBox每个形状编写函数，但这不应该太难。

做一个“这Star完全被这个覆盖了Oval吗？” 提出了一个更具挑战性的解决方案[您需要有两个形状的完整轮廓，并且Oval轮廓可能是相当多的点才能精确地成为椭圆形]。

于 2013-07-16T11:12:20.253 回答
1

让子类相互了解是个坏主意。如果您想要像素完美的碰撞，那么您将不得不遍历形状中的每个像素并与其他形状的像素进行比较。创建一个虚拟函数以从形状中获取一个像素 N，其中 N 是一个索引，以及另一个返回像素数的函数。对于当前形状中的每个像素 N，与其他形状中的所有像素 0..Nmax 进行碰撞比较。

索引 N 的像素顺序可以是任意顺序。如果您在附近 N 上交替形状的不同边之间的像素，并首先从外部像素开始，您可能更有可能在较低的 N 上检测到碰撞。

现在这个简单的方法很慢，特别是如果你有很多形状。解决方案是使用更便宜的算法来检查是否需要完美的算法。矩形边界框是最便宜的方式。计算出一个刚好能容纳你的形状的矩形的坐标。我不知道如何解决这个问题（几何不是我的强项）。您甚至可以在类中缓存边界框大小，以防止重新计算复杂形状。检查两个矩形是否重叠非常快速和容易。

只有在边界框重叠时才转移到代价高昂的算法。

您可以在某些对象对之间进行更快的检查。例如，如果两个矩形的边界框重叠，则它们会重叠。进行像素比较是矫枉过正的。但您可能不需要这种级别的性能。

于 2013-07-16T11:46:46.523 回答