C++ Overridden method not getting called

Here's your problem:

struct ShapePointPair {
        Shape shape;
        Point location;
};

You are storing a Shape. You should be storing a Shape *, or a shared_ptr<Shape> or something. But not a Shape; C++ is not Java.

When you assign a Rect to the Shape, only the Shape part is being copied (this is object slicing).

This problem is called slicing - you lose the derived functionality when copying to a base. To avoid this use pointers to the base class, i.e.

std::vector<Graphics::Shape*> s;
s.push_back(&some_rect);