How can I remove doubles without creating intersections? I've got a mesh of a terrain. I'd like to create a simpler version that follows roughly the same shape. I've been using Remove Doubles to do this (which gives me a better result than the Decimate modifier), but have noticed that it can create intersections in the mesh, which causes me problems later on, particularly when using the Boolean modifier.

Original mesh:



When removing doubles (red areas are intersecting faces):



What's the best way to remove these intersections after removing the doubles (or preventing them from happening)? I'm scripting this process, so would love to hear of any solution that doesn't involve manually selecting visible/invisible faces. Thanks!

Edit: Here's the Blend file in case anyone is interested.
The mesh cleanup tools can help with this, especially limited dissolve.



Select all mesh elements in edit mode, then go to the Mesh --> Cleanup --> Limited Dissolve tool. Then triangulate all faces with CtrlT.



The larger the angle, the stronger the effect.