Retrieve the list of outer triangles

[fontanf]

Thank you for this package.

Is there a way to retrieve the list of outer triangles, that is the triangles for which one edge belongs to the convex hull?

[artem-ogre]

Do you mean triangles outside the convex hull? Or the ones inside but on the boundary?

[artem-ogre]

I'm not sure I understand. See the image below:

With eraseSuperTriangle you get convex hull, but holes and boudaries are not detected. With eraseOuterTrianglesAndHoles you don't really get the convex hull. Could you please describe what is it that you would like to achieve in more detail?

[artem-ogre]

Anyway, I will try to guess, here's another idea: findi all the convex hull edges on a non-finalized triangulation: each triangle that has exactly one point on the super-triangle has exactly one convex hull edge connecting two other "normal" points. Store convex hull edges in an unordered map and select convex hull triangles by checking if triangle has any edges in that map.

[fontanf]

My final goal is to simplify a polygon with an outer approximation. I would like to try to implement something similar to what is proposed in this paper. The algorithm described in this paper computes a triangulation and then removes outer triangles until reaching a good compromise between complexity and quality of the approximation. This algorithm just takes points as input, not a polygon. So it cannot be directly applied in my case. But I would like to try to adapt it by computing a constrained Delaunay triangulation as first step.

[fontanf]

Your last suggestion looks good. I will try

[artem-ogre]

Your last suggestion looks good. I will try

Good luck! Keep in mind that before finalizing first three vertices are super-triangle vertices which are removed after the triangulation is finalized. You might need to adjust edges' vertex indices by 3.