Refactor triangulator

[elalish]

#528 helped a fair bit with reliability, but it certainly didn't solve everything (see the disabled test, as well as #529). The trick with the Boolean algorithm is I have a proof of topological robustness (manifoldness guarantee), but getting correct geometry is still dependent on the triangulator giving a geometrically valid result, and not just using its manifold fallback. I invented this triangulator, and it has no such mathematical guarantee, which is why it is the source of most of our bugs (along with the decimator). I've rewritten it several times as it got too complicated and I came to understand the problem space better - I think it's time to do this again.

There are some complexities I really don't like, as they feel like hacks and make it difficult to reason about. They mostly come down to logic that skips the sweep line, the worst offender being isHole which searches way ahead to determine the winding direction. This was only necessary because I didn't have a way to swap active edges out of being a hole, so I had to know it was a hole when it was first found in order to swap it in once and leave it there. However, there are plenty of other degenerate cases where a hole might need to be swapped, and it would fit more cleanly in the logic if everything can happen at the sweep line.

I would also like to build with a requirement in mind, inspired by @pca006132: any valid polygon should have the exact same result (and follow all the same branches) at any value of epsilon, including zero. Only polygons that are epsilon-valid, but invalid at a lower epsilon should get different results. This should allow us to better separate the code based on uncertainty, and I might even be able to check it automatically by having our tests compare verbose-mode outputs.

I think the general logic of the vertical ordering (sweep forward and sweep back) and the final monotone triangulator are good. It's the horizontal ordering (shiftEast, shiftWest) that needs refactoring, as I think the activePairs data structure is not adequate. Pairs are not the right unit, as they must be split and combined when swapping to or from a hole.

I think instead a list of active edges that only point to one vert, but implicitly always alternate down, up, down, up, ... will be more flexible. I believe we also need to keep track of how these edges have already been found to attach to each other: they each need to point to their end of a list of start and merge verts which are always ordered in rightward vertex progression. As currently, the key piece of information to store is the Eastern edge each merge vert should be inserted next to in the sweep back pass. Now we will be able to update these after the sweep line passes them, as we may need to use y-value information to determine where degenerate holes can be inserted in this list. I believe we can also get more concrete about what uncertain means, having it apply only eastwards and therefore representing the relative order uncertainty between adjacent edges, rather than in a particular direction.

[starseeker]

Just trying to figure out which issues I should be watching - is this the effort that will be intended to address #535?

[pca006132]

@starseeker yes