Need curvature for triangulation of a 2D area (or a good algorithm)

Question

I want to triangulate a bounded 2D area in order to interpolate the colors, but unfortunately I'm not a clever mathematician, so I could need some clever idea.

Let's have a look at this sample:

The area is bounded by a series of 2D-points, and there is some special point C that is not outside of the bounded area.

I started out with a bounded area like on the left, so when following the points of the border clockwise, I could set up triangles A starting at C (point 1) and continuing with points 2 and 3 (each vertex also has a color property, and inside the triangle I can interpolate linearly). The final triangle was composed of both end points and the "center" point C.

The algorithms seems to work because the curvature of the border is the same as the "direction of movement" (sorry, I cannot express it better in mathematics' words).

However when looking at the right example building triangles the same way (like (1, 2, 3)), the triangles $A_1$ cross border area, also resulting in incorrect interpolation.

So my idea was to select a point 4 on the border (but which exactly?) to build triangles $A_2$ like (2, 3, 4), but I don't know which condition to use, and more importantly how to compute the condition efficiently.

So what I have is an array of 2D points with a color attribute (like RGB) and some reference point C (also with a color attribute). (I picked C to be one corner of the triangles, because it seemed just handy to do so.)

So what algorithm would you suggest? The algorithm should need only one pass through the array of points, preferably.

One obvious solution might be using a "dynamic C", but I have to idea how to pick it, specifically as I would not know the color of it without interpolating from other points.

Answer 1

It sounds like you need to first triangulate an arbitrary polygon and there are several algorithms for that. For example, Nathan's answer for Turn an enclosed region into a triangle mesh mentions the "reasonably straightforward" ear clipping algorithm.

However, you also said 'one pass' through the vertices, but ear clipping is an $O(n^2)$ algorithm. I saw there is an $O(n)$ algorithm but AFAIU it is likely very complicated.

FWIW I implemented Seidel's Algorithm** which is $O(n\, log^* n)$ - note the '*' on the log - which is virtually linear, but it creates trapeziums*** as part of its processing, which might not make your shading work as well.

** A word of warning - there is an article from Graphics Gems (http://gamma.cs.unc.edu/SEIDEL/ ) that implements a method 'based-on' Seidel's, but it appears it leaves out a critical step so is 'only' $O(n\, log\, n)$

***(or if you are in the US where, apparently, they got it back-the-front due to an error in an early textbook, "trapezoids")