Delaunay refinement (#66)

[Stoeoef]

See #66.

This is the initial implementation which works sufficiently well already.

To use this, create a CDT, insert some constraint edges and then call

my_cdt.refine(RefinementParameters::new().exclude_outer_faces())

which will refine the cdt inplace. Note that, in order for exclude_outer_faces to work, the constraint edges should form a loop somewhere - otherwise, all faces will be considered to be outer faces and won't be refined.

Remaining TODOs (just mentioning for my own overview):

• Documentation of AngleLimit
• Documentation of RefinementParameters
• Documentation of fn refine
• Internal documentation by adding a few comments at appropriate places

TODOs for some follow-up PRs:

• Try to enable refinement algorithm for regular triangulations (if easy)
• Investigate if the refinement quality can be increased (though it's not too bad already)
• Add some images detailing how exclude_outer_faces works

[RobWalt]

This PR seems really interesting and useful. Is there something I could do to help you out here @Stoeoef ?

[Stoeoef]

@RobWalt Sorry for my long silence on this issue! Especially since the actual hard work - the implementation of the refinement algorithm - is already completed. I would appreciate support in bringing this over the finishing line!

I plan on looking into this branch within the next week to see where I've left things back then. In the meantime, if you want to help, feel free to simply try this out. Getting some feedback from actual users (I myself don't need this feature) would be helpful!
This is both in regards to feature set (is the refinement good enough?) as well as interface (is it easy to use and documented well enough?).
Though, if you have different ideas in mind, I don't mind either.

[RobWalt]

No rush, I didn't mean to stress you out with the message 😅

I have a good use case for it. We're working on some geometry and need to create tri-meshes from it. Unfortunately the software we're feeding the tri meshes into isn't happy about degenerate triangles. I think this feature here would make a lot of our own cleanup post processing unnecessary. It's also something I'd like to support with some new method on the newly integrated spade trait in the geo crate

I've already started reading into the code a bit, but I'm really new to some of the ideas here. I'll try to focus on giving some support and feedback by:

• exploring the interface a bit in terms of UX
• try out some of my use cases -> possibly creating some tests from that
• give the docs a thorough read through

From what I've seen, the triangulations are already looking really promising! In terms of quality I would already say that this is perfectly fine. Anything that is creating even just slightly friendlier triangulations is good enough and for the rest we can iterate on the initial solution 🔧

[RobWalt]

Just did a little testing and I'm in love. I still need to cleanup some parts but here is a sneak peek

[Stoeoef]

Ohh, that does look lovely.
The only strange thing are the many subdivisions on the left side. Any idea where these are coming from? (Edit: Or is this the missing cleanup activity?)

[RobWalt]

The only strange thing are the many subdivisions on the left side. Any idea where these are coming from?

I'm using OSM data here. I think the level of detail on the left side comes from a unnecessary subdivision of the leftmost line. This probably leads to very thin triangles. Since I refined with angle ~ 30 parameter that's probably just the result of the algo trying to refine those very thin triangles away.

[Stoeoef]

Alright, this is ready to go - merging in!
I'll publish a new version on crates.io afterwards. Happy refining!