<p>It <em>sounds</em> like you need to <em>first</em> triangulate an arbitrary polygon and there are several algorithms for that. For example, Nathan's answer for <a href="https://computergraphics.stackexchange.com/q/4741/209">Turn an enclosed region into a triangle mesh</a> mentions the &quot;reasonably straightforward&quot; ear clipping algorithm.</p>
<p>However, you also said 'one pass' through the vertices, but ear clipping is an <span class="math-container">$O(n^2)$</span> algorithm. I saw there is an <span class="math-container">$O(n)$</span> algorithm but AFAIU it is likely <em>very</em> complicated.</p>
<p>FWIW I implemented <a href="https://www.sciencedirect.com/science/article/pii/0925772191900124" rel="nofollow noreferrer">Seidel's Algorithm</a>** which is <span class="math-container">$O(n\, log^* n)$</span> - <a href="https://en.wikipedia.org/wiki/Iterated_logarithm" rel="nofollow noreferrer">note the '*' on the log</a> - which is virtually linear, but it creates trapeziums***  as part of its processing, which might not make your shading work as well.</p>
<p>** <em>A word of warning - there is an article from Graphics Gems (<a href="http://gamma.cs.unc.edu/SEIDEL/" rel="nofollow noreferrer">http://gamma.cs.unc.edu/SEIDEL/</a> ) that implements a method 'based-on' Seidel's, but it appears it leaves out a critical step so is 'only' <span class="math-container">$O(n\, log\, n)$</span></em></p>
<p>***(<em>or if you are in the US where, apparently, they got it back-the-front due to an error in an early textbook, &quot;trapezoids&quot;</em>)</p>

CC BY-SA 4.0
2024-11-07T09:55:12.220Z
2024-11-16T09:10:47.580Z
2024-11-16T09:10:47.580Z
Simon F
<p>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.</p>
<p>Let's have a look at this sample:</p>
<p><a href="https://i.sstatic.net/rUwjJ1dk.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rUwjJ1dk.png" alt="Sample image showing triangulation problem" /></a></p>
<p>The area is bounded by a series of 2D-points, and there is some special point <strong>C</strong> that is not outside of the bounded area.</p>
<p>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 <strong>A</strong> starting at <strong>C</strong> (point <strong>1</strong>) and continuing with points <strong>2</strong> and <strong>3</strong> (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 &quot;center&quot; point <strong>C</strong>.</p>
<p>The algorithms seems to work because the curvature of the border is the same as the &quot;direction of movement&quot; (sorry, I cannot express it better in mathematics' words).</p>
<p>However when looking at the right example building triangles the same way (like (<strong>1</strong>, <strong>2</strong>, <strong>3</strong>)), the triangles <span class="math-container">$A_1$</span> cross border area, also resulting in incorrect interpolation.</p>
<p>So my idea was to select a point <strong>4</strong> on the border (but which exactly?) to build triangles <span class="math-container">$A_2$</span> like (<strong>2</strong>, <strong>3</strong>, <strong>4</strong>), but I don't know which condition to use, and more importantly how to compute the condition efficiently.</p>
<p>So what I have is an array of 2D points with a color attribute (like RGB) and some reference point <strong>C</strong> (also with a color attribute).
(I picked <strong>C</strong> to be one corner of the triangles, because it seemed just handy to do so.)</p>
<p>So what algorithm would you suggest?
The algorithm should need only one pass through the array of points, preferably.</p>
<p>One obvious solution might be using a &quot;dynamic <strong>C</strong>&quot;, but I have to idea how to pick it, specifically as I would not know the color of it without interpolating from other points.</p>

CC BY-SA 4.0
2024-11-21T13:14:14.263Z
So you mean that you have a polygon, rather than a curve?
Yves Daoust
CC BY-SA 4.0
2024-11-21T13:17:54.467Z
What you are asking is unclear. What is the relevance of the point C? In the case of the contour with a "fold", what interpolation result do you expect?
Yves Daoust
CC BY-SA 4.0
2024-11-21T20:58:57.157Z
@YvesDaoust I specified "...*there is some special point C that is not outside of the bounded area* ...". In many cases C is more or less near the center (thus the name), but it could get very close to the boundary. The interpolation is the next thing: In one case linear interpolation is fine, and actually the reason for the algorithm is that I want to substitute the linear interpolation from C to the border with a "stepwise linear" interpolation where I would compute the value from the point's coordinates. Actually I want to do it in PostScript.
U. Windl
CC BY-SA 4.0
2024-11-22T10:17:33.497Z
This does not answer my request for precision. How will you interpolate in the areas that are not reachable from C?
Yves Daoust
CC BY-SA 4.0
2024-11-22T18:08:06.043Z
The corners of A_2 (2,3,4) have known properties as described, because they are on the border.
U. Windl
CC BY-SA 4.0
2024-11-22T22:04:15.247Z
Without a clear explanation, I cannot help. Bye.
Yves Daoust
<algorithm><triangulation>
Need curvature for triangulation of a 2D area (or a good algorithm)
U. Windl
# Need curvature for triangulation of a 2D area (or a good algorithm)

(Asked by: username_0 on 2024-11-05)

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:

[![Sample image showing triangulation problem](https://i.sstatic.net/rUwjJ1dk.png)](https://i.sstatic.net/rUwjJ1dk.png)

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.

**Tags:** algorithm, triangulation

> **Comments:**
> **username_1**: So you mean that you have a polygon, rather than a curve?  
> **username_1**: What you are asking is unclear. What is the relevance of the point C? In the case of the contour with a "fold", what interpolation result do you expect?  
> **username_0**: @username_1 I specified "...*there is some special point C that is not outside of the bounded area* ...". In many cases C is more or less near the center (thus the name), but it could get very close to the boundary. The interpolation is the next thing: In one case linear interpolation is fine, and actually the reason for the algorithm is that I want to substitute the linear interpolation from C to the border with a "stepwise linear" interpolation where I would compute the value from the point's coordinates. Actually I want to do it in PostScript.  
> **username_1**: This does not answer my request for precision. How will you interpolate in the areas that are not reachable from C?  
> **username_0**: The corners of A_2 (2,3,4) have known properties as described, because they are on the border.  
> **username_1**: Without a clear explanation, I cannot help. Bye.  

---

## 1 answers

### Answer by username_2 on 2024-11-07. Score: 2

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](https://computergraphics.stackexchange.com/q/4741/209) 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](https://www.sciencedirect.com/science/article/pii/0925772191900124)\*\* which is $O(n\, log^\* n)$ - [note the '\*' on the log](https://en.wikipedia.org/wiki/Iterated_logarithm) - 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"*)


---

