Non-Convex Triangulation

Nov 20, 2014 at 8:27 PM
Hi,

Firstly; a very impressive library. Its far better than my own attempts.

My question ; I am triangulating a linear feature (i.e. non convex 2D shape) and clearly am getting poor results from the MIConvexHull Delauny triangulation because it internally calculates a convex hull of the point cloud. Before I go dashing off and trying to pass in my already known hull points (in fact in my case all my known points are the entire hull as they are the boundary of my linear feature) I wanted to ask if you'd already provided for passing in a known hull, or if not, whether you would foresee any problems in the underlying algorithm if the hull was not actually convex.

Thanks in advance,.
Developer
Dec 15, 2014 at 1:11 AM
Edited Dec 15, 2014 at 4:15 PM
EDIT: What I wrote is actually incomplete. What you want is called constrained triagulation and this library cannot do it on it's own. Before the triangles are removed, a few edge flips might need to be performed to ensure it's a triangulation of the original polygon.

Hi Phillip,

sorry I didn't get to you sooner I've only noticed the post now.

In case it is still relevant:

It took me a while to understand what you want and I hope I got it.... To solve your problem you will actually have to post-process your result and remove some triangles.
  • For your 2D you should be able to decide if a point lies inside it or not. There are algorithms for that (for example http://www.codeproject.com/Tips/84226/Is-a-Point-inside-a-Polygon).
  • For each triangle compute its geometrical center and test if it's inside the shape or not.
  • Correcting the adjacency is also easy -- one way is for each removed triangle, go to its adjacency and mark the corresponding element null.
Hope it helps or that you solved your problem already,
David