Was looking for a solution for this for months, on and off, trying all sorts of various algos that I was figuring out myself. I think the biggest breakthrough was your idea of marking edges as two-directional, and making sure each direction can only be traversed once.

My implementation is ugly as hell and really inefficient, but here it is in javascript, rendered with pixi.js:

https://dl.dropboxusercontent.com/u/705999/polyfinder/index.html

Thank you for this article!