Most Elegant Way to Get Around This Polymorphism Issue

Question

EDIT: I'm working with C++.

So, I am creating methods/functions to test intersection between shapes. I essentially have this:

class Shape {};

class Rectangle : public Shape {};

class Circle : public Shape {};

class Line : public Shape {};

Now, I need to decide on the best way to write the actual methods/functions to test intersection. But all my shapes will be stored in a list of Shape pointers, so I will be calling a method/function of the basic form:

bool intersects (Shape* a, Shape* b);

At that point, I need to determine which types of shapes 'a' and 'b' are, so I can properly detect collisions. I can easily do one of them, by just using some virtual methods:

class Shape
{
    virtual bool intersects (Shape* b) = 0;
}

That would determine one of the shapes ('a' is now 'this'). However, I would still need to get the type of 'b'. The obvious solution is to give Shape an 'id' variable to classify which shape it is, and then 'switch' through those, and then use dynamic_cast. However, that is not very elegant, and it feels like there should be a more OO way to do this.

Any suggestions?

Answer 1

As @Mandarse pointed out, this is typical double dispatch issue. In Object Oriented languages, or like C++ languages that can implement Object Oriented concepts, this is usually solved using the Visitor Pattern.

The Visitor interface itself defines one callback per concrete type, in general.

class Circle;
class Rectangle;
class Square;

class Visitor {
public:
  virtual void visit(Circle const& c) = 0;
  virtual void visit(Rectangle const& r) = 0;
  virtual void visit(Square const& s) = 0;
};

Then, the Shape hierarchy is adapted for this. We need two methods: one to accept any type of visitor, the other to create the "appropriate" intersection visitor.

class Visitor;
class Intersecter;

class Shape {
public:
  virtual void accept(Visitor&) const = 0; // generic
  virtual Intersecter* intersecter() const = 0;
};

The intersecter is simple:

#include "project/Visitor.hpp"

class Intersecter: public Visitor {
public:
  Intersecter(): result(false) {}
  bool result;
};

For example, for Circle it will give:

#include "project/Intersecter.hpp"
#include "project/Shape.hpp"

class Circle;

class CircleIntersecter: public Intersecter {
public:
  explicit CircleIntersecter(Circle const& c): _left(c) {}

  virtual void visit(Circle const& c);    // left is Circle, right is Circle
  virtual void visit(Rectangle const& r); // left is Circle, right is Rectangle
  virtual void visit(Square const& s);    // left is Circle, right is Square

private:
  Circle const& _left;
}; // class CircleIntersecter


class Circle: public Shape {
public:
  virtual void accept(Visitor& v) const { v.visit(*this); }

  virtual CircleIntersecter* intersecter() const {
    return new CircleIntersecter(*this);
  }
};

And the usage:

#include "project/Intersecter.hpp"
#include "project/Shape.hpp"

bool intersects(Shape const& left, Shape const& right) {
  boost::scope_ptr<Intersecter> intersecter(left.intersecter());
  right.accept(*intersecter);
  return intersecter->result;
};

If other methods need a double-dispatch mechanism, then all you need to do is create another "Intersecter-like" class that wrap the result and inherits from Visitor and a new "Factory" method rooted in Shape that is overriden by derived classes to provide the appropriate operation. It is a bit long-winded, but does work.

Note: it is reasonable to except intersect(circle, rectangle) and intersect(rectangle, circle) to yield the same result. You can factor the code is some methods and have CircleIntersecter::visit delegates to the concrete implementation. This avoid code duplication.

Answer 2

Andrei Alexandrescu detailed this problem in his classic Modern C++ Design. The companion library Loki contains the the implementation for Multi-Methods.

Update

Loki provides three implementations of Multi-Methods, depending on the user's needs. Some are for simplicity, some are for speed, some are good for low coupling and some provide more safety than others. The chapter in the book spans nearly 40 pages, and it assumes the reader is familiar with many of the book's concepts -- if you are comfortable using boost, then Loki may be down your alley. I really can't distill that to an answer acceptable for SO, but I've pointed you to the best explanation of the subject for C++ that I know of.