Is this a good algorithm for 2D collision, or will it allocate too much memory?
Your constructor arguments and defaults are unusual.
What does radius mean for a Rectangle?
Should there be an argument for initializing mass?
I suggest:

    static const Vec2f&amp; defaultCenter();
    static const Vec2f&amp; defaultSquareDimensions();
    static const Vec3f&amp; defaultColor();

    Rectangle(
        const Vec2f&amp; center = defaultCenter(),
        const Vec2f&amp; widthheight = defaultSquareDimensions(),
        // Assuming rotation angles are supported...
        const Vec2f orientation = defaultOrientation(),
        const Vec3f&amp; color = defaultColor()
    );


and/or maybe:

    Rectangle(
        const Vec3f&amp; color,
        const Vec2f&amp; center = defaultCenter(),
        const Vec2f&amp; widthheight = defaultSquareDimensions(),
        // Assuming rotation angles are supported...
        const Vec2f orientation = defaultOrientation()
    );



    inline const Vec2f&amp; getWidthHeight() const {
        return mWidthHeight;
    }


The static methods can return "static objects" that are constructed once each instead of always constructing new temps.

I can't tell what the return value of the following function represents. 
What is the north direction vector of a rectangle?
Can you give examples for different rectangles?
Can you explain how you would use the returned vector?

    inline Vec2f getDirection(V2D_DIRECTION dir) const {
        switch(dir) {
        case V2D_NORTH:
            return mNorth;

        case V2D_SOUTH:
            return mSouth;

        case V2D_EAST:
            return mEast;

        case V2D_WEST:
            return mWest;

        }
    }


This seemed missing?

    virtual bool Intersects( const Circle&amp; s ) const;


There should be some good reason not to make these private:

   Vec2f mCenter;


There seems to be no reason to make this a pointer.
There might be an argument for making it const.

   Vec2f mWidthHeight;
   Vec2f mOrientation;


If rectangles tend to come in a small selection of colors, 
you may be better off storing an index into a central 
pallette vector or possibly a pointer into a pool of shared colors.

There might be an argument for making this const if they don't change color.

   Vec3f mColor;


The following seem expensive to store and maintain and they also seem like they may be at least partly redundant? If they are redundant (derivable from a smaller set of parameters)
you should probably run benchmarks on code that stores these values 
and code that calculates them on the fly as needed.

private:
   Vec2f mNorth;
   Vec2f mSouth;
   Vec2f mEast;
   Vec2f mWest;
   void InitDirections();


It may be that there is a better way to express orientation and/or these other values that is more useful in finding intersections.
It seems strange to me to be considering even more of these vectors for NW, etc. but I'm not even sure yet what they mean.

To speed up intersection, I thought you MIGHT also want to store 
an additional widthheight representing the bounding box -- the smallest x/y
aligned rectangle that contains this rectangle in its current orientation.

SO MUCH depends on how your actual intersect logic uses all of these values.
Storing them all and more MIGHT be worthwhile.

CPU vs. memory trade-offs can be very tricky to predict.