search

artem-ogre / CDT

Constrained Delaunay Triangulation (C++)
https://artem-ogre.github.io/CDT/
Mozilla Public License 2.0
1.08k stars 136 forks source link

Introduce "inner" (non-boundary) constrained edges #109

Closed RotateMe closed 1 year ago

RotateMe commented 2 years ago

This PR introduces a flag on constraint edges that allows the distinction between "outer" and "inner" constraint edges, that is, edges that will be boundaries when removing the super triangle and holes, and edges that will simply be guaranteed to be part of the triangulation, but do not describe the boundaries of the triangulation, and will be ignored during "hole-detection".

I did not find any other way to achieve this, but maybe there's a much simpler way?

In any case, I wanted to publish our changes, and share them in this way. If you want to merge this, I'll gladly work in any comments that you might have.

artem-ogre commented 2 years ago

Thank you for the PR, Christopher! I will take a look when I’m back at the keyboard.

artem-ogre commented 1 year ago

Dear, Christopher @RotateMe

Sorry for taking so long with this...

I did not find any other way to achieve this, but maybe there's a much simpler way?

I've got an idea! CDT supports overlapping boundaries by keeping an overlap counter for each constraint edge. This counter is then used to correctly calculate triangle depths during layer peeling. With the tiny fix we can use this feature to support non-boundary edges: just insert such edges twice into the triangulation.

I've done the fix here: #123. Please check out the branch and try test files issue-42-full-boundary-overlap.txt and issue-42-full-boundary-overlap-2.txt to see the effect in action. What do you think? If you think it works fine for your use cases, I am open for any feedback how to make it into a more user-friendly API (and not a side-effect hack it is 🙂 )

artem-ogre commented 1 year ago

Fixed in #126 Feel free to re-open if the fix is good enough.