grg12: that sounds exactly like what I'm doing :]
I also tried to implement the offset algorithm, almost exactly as you describe - using the normal vector as a criterion for good/bad. The problem I came across was that it doesn't seem to like multiple intersections between several internal invalid loops, which usually happens when you have a complex curve with a large offset radius.
I've instead gone with a bitmap approach, although that has its own problems.
One point to note is that finding all intersections between all segments is O(n^2) time complexity. This is really really bad. I have implemented a sweep-line algorithm for finding intersections with O(log m) complexity, which brought my processing time from over 5 seconds to under 200ms.
here's the paper, it's for polygonal chains, but it was pretty easy to adapt to circular arcs.