You're going to have to delete a lot of points or move a lot of points, so it's probably not any faster than doing a regular run through RDP and then interpolat

You're going to have to delete a lot of points or move a lot of points, so it's probably not any faster than doing a regular run through RDP and then interpolating. Interpolating is easy enough. The bottleneck (at least in the Objective-C++ implementation I have) is pow and sqrt, which are pretty hard to avoid. If you want to make it faster the best way to do it is to remove the interior points of each line segment in the polygon you're working with (before you run it through RDP). The easiest way to do that is to keep track of what direction you're extracting the points from, from whatever you've already edged (or however you're doing it) since most blob extraction algorithms return every point around the edge of each polygon. If you think about it you just need to throw away everything except for the corners. That's assuming you're working from bitmap images, which I guess is not necessarily the case. If you're working from a sparse set of points to begin with and you're not getting the performance you need you're going to have find other ways to speed it up obviously.