How can I remove doubles without creating intersections?
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.