spade
spade copied to clipboard
Stoeoef
Steiner points
Is the implementation of „steiner points“ / insertion of additional points to reduce the triangle size to a certain maximum area planned for this library?
That might be a good feature addition as it's a common next step after inserting a triangulation.
You're mentioning "reducing the triangle size" - is this the only criteria for which you would need to optimize? Making sure that the area is small should be comparably easy by inserting a steiner point into the center of each face that is too large. Alternatively, you could consider to overlay a triangulation with a point grid spaced by the desired target minimal size and only insert points that lie within the convex hull.
After a little reading it appears that the more challenging task is to prevent skewed triangles with small angles while explicitly allowing faces to remain large where little detail is needed (good grading). This overview presentation (from 2005) indicates that two common algorithms, Ruppert's and Chew's, would probably good candidates to implement in this case (with a few modifications to avoid issues with small angles). OTOH, I'm no expert in that region and didn't look at any research in that area after 2005 - please let me know if you had anything specific in mind.
Thanks @Stoeoef for your answer!
Besides max area i think the skewness of the triangles is also important in meshes.
I think not much has changed since 2005 and Rupperts' still seems to be a name. Here is a very nice presentation i found: http://mkacz91.github.io/Triangulations/
it starts with steiner points about half the way through: http://mkacz91.github.io/Triangulations/#/step-ruppert-intro-1
Results look promising so far (Red lines without intermediate straight points are the input):
This is an implementation of Ruppert's algorithm with a few tweaks around how small input angles are handled.
I still need to ponder a little how small input angles should be handled - currently the algorithm might "give up" too early.
In any case, if you have any example input data that you can share (preferably in an easy to parse format), feel free to share that and I'll see what the algorithm makes with that.
I still need to ponder a little how small input angles should be handled - currently the algorithm might "give up" too early.
@Stoeoef: Did you eventually figure this out in #68? I had to wrangle with this in my implementation of this same algorithm (in Julia, though) and eventually solved it. See e.g. the example below. Happy to discuss if you're still trying to think through this - otherwise feel free to ignore :).
