Most Elegant Way to Get Around This Polymorphism Issue

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.

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.

C++ run-time polymorphism has a single dispatch (the base class vtable).

There are various solution to your problem but none of them is "elegant", since they all try to force the language to do more that it can natively support (Alexandrescu Loki multimethods is a very goodly hidden set of hacks: it encapsulates the "bad things", but doesn't make then good)

The concept, here, it that you need to write all the N² functions of the possible combinations and find a way to call them based on the actual runtime-type of TWO parameters. The "visitor pattern" (call back a virtual unction from another virtual function), the "mutimethod" technic (use a generic dspatch table), the "dynamic cast" into a virtual function or the "dual dynamic_cast" out all of the functions all do the same thing: call a function after two indirection. None of them can technically be defined "better then the other" since the resulting performance is mostly the same.

But some of them cost more then the other in code writing and other cost more in code maintenance. You have most likely to try to estimate in your case what the trade-off is. How many other classes do you think you may need to add in the future?