The discussion of triangle collisions just makes me glad that almost everything in my game is round. hypot ftw.
Circles do make everything easier. I started with those too.
N, thanks for the rotation matrix explanation - that looks really useful and makes me wish I'd paid more attention in maths classes. I'm going to try the matrix on the stars; it looks like it will be much faster than atan, leaving me more space in the 20ms per frame to fit in more and larger explosions.
That was definitely helpful. The main thing I would have added was translation (change of position), but you can do that as a separate step. In the case of stars, you'll want to build a rotation matrix with the player's angle negated, and then for each star subtract the player's world position, apply the rotation matrix, and add the player's screen position. You can actually compute a 2x3 matrix to to it all in one shot, but the translation part gets sort of complicated to work out.
If you describe your coordinate system (the directions positive X and Y point, which direction the zero angle points, and whether angles are clockwise or counterclockwise), I could try writing some C functions for you. I think you'll need to get a transform matrix given a position and angle, get the inverse of a transform matrix, rotate (local direction to world direction), unrotate (world direction to local direction), transform (local position to world position), and untransform (world position to local position).
It's true, I am trapped in the past. I really like Allegro's support for 8-bit graphics, which lets you do cool things with transparencies that would be impossible in other graphics modes. And I like the direct control it gives you over the display buffer at the pixel level, which allows things like reading the pixels making up the player's ship to calculate collisions.
If it still works for you, is there a big reason to change?
I'm a big fan of OpenGL myself, and I think your visual style would translate well to solid-filled GL primitives. It'd certainly make camera transforms and transparency effects a lot easier!

You'd lose the frame buffer tricks, but a good 2D physics engine would take the pain out of that and give you a lot of new toys to play with.
It's also C, which I like more than C++ (not that I understand C++ well enough to really be able to compare them).
While I work with C++ extensively, I do like the relative simplicity of C for libraries. C++ is a horrible, horrible languages that happens to be very popular.

Quick note: Box2D is C++, which will make it somewhat difficult to integrate into a pure C engine.