Maybe get the bounding box of the circle and set it to the same rotation as the rectangle? Then the side of the circle bounding box would be parallel with the nearest rectangle side, and regular rectangle to rectangle algorithms can then be used...I think.
Never done circle to rectangle myself so that's just a guess. Obviously this won't extend to ellipses.