Thanks for all the feedback. I fixed some cases (quad with an additional vertex) but many are still unsolved (especially the + / x shape). Anyway, I have some new test polygons now and can fix them when I find the time to do so.
This is one of those algorithms that is reasonably straightforward as long as all the vertices are in “general position”, and gets very special-case-y and hard when they are not. As I discovered implementing my similar addons.
Yes that is true. It is a very discrete algorithm and thus unforgiving when it comes to imprecise calculations. These effects are amplified by “too perfect” inputs like parallel lines or perfectly symmetrical shapes.