Talk:Polygon triangulation

Polygon Partitioning: Monotone Triangulation Bader Al-Essa Dec. 2nd, 1997

Description of the Algorithm: Triangulating a Two-Dimensional Monotone Polygon

The main idea behind the algorithm is quite simple. First the vertices are sorted with respect to the line of monotonicity, which in the first case is the y-axis (which involves sorting the vertices by their y-coordinate), and in the second case it is the x-axis. Sorting becomes more complex when the line of monotonicity is neither the x nor the y-axis, yet it is not impossible. However, finding the line of monotonicity can be quite difficult to implement. This issue requires more effort and it lies beyond the scope of this report. After sorting the vertices from top to bottom, the triangles are cut off from the top.

The algorithm is summarized in pseudocode (taken from Computational Geometry in C by Joseph O'Rourke, 57):

Algorithm: Monotone Triangulation

  Sort vertices by y-coordinate. (or x-coordinate, whichever the case may be)
  Initialize reflex chain to be two top vertices.
  Let v be the third highest vertex.
  while v != lowest vertex, do:
     Case 1: v is on chain opposite reflex chain,
             Draw diagonal from v to second vertex from top of chain.
             and remove top of chain.
             if chain has one element, then add v and advance v.
     Case 2: v is adjacent to bottom of reflex chain.
             Case 2a: v+ is strictly convex.
                      Draw diagonal from v to second vertex from bottom of chain,
                      and remove bottom of chain.
                      if chain has one element, then add v and advance v.
             Case 2b: v+ is reflex or flat.
                      Add v to bottom of reflex chain,
  Advance v.

This algorithm takes advantage of the fact that at every new iteration of the monotone triangulation algorithm, the vertices above v are (1) all in one chain and (2) the chain is reflex (which means that all the internal angles are greater than or equal to pi). If the vertices weren't all in one chain, then the diagonal would have been found in an earlier iteration (Case 1), and if the chain were not reflex, the diagonal would also have been found earlier (Case 2a). —Preceding unsigned comment added by Baderalessa (talk • contribs) 00:17, 17 October 2008 (UTC)[reply]

A note for anyone who comes across this: this material is taken from a website here but is probably not a copyright violation, since the username (User:Baderalessa) corresponds to the author Bader Al-Essa of the webpage. The pseudocode is taken from a copyrighted source, and I recommend it be rewritten, but fair use may apply here. Dcoetzee 00:53, 17 October 2008 (UTC)[reply]

**Why the removal of O(n log*n) references?**

Svmich deleted the sentences I added regarding "O"(n log*n) triangulation algorithms, e.g. Seidel's, and replaced them with a reference to what appears to be a Delaunay triangulation algorithm. Since the reference is in Russian I can't tell if this is Constrained Delaunay Triangulation or not. Does it introduce additional (Stenier?) points? Fig 15 would seem to suggest it might, which surely goes against the strict, definition of polygon triangulation. Does anyone know of an English version of the paper? Simon Fenney (talk) 14:07, 24 July 2009 (UTC)[reply]

Dynamic Triangle Caching?

<quote>Finally, in 1998 the first practical O(n) algorithms were discovered and published by Alexey V. Skvortsov and Yuri L. Kostyuk.[6] The fastest of these algorithms employs dynamic triangle caching.</quote>

What is dynamic triangle caching? Should there be an article about this?

--140.180.12.189 (talk) 03:41, 23 March 2010 (UTC)[reply]

I doubt it is notable enough to deserve its own article, but this claim should have a citation. I'll see if I can find out what "dynamic triangle caching" is. Jwesley₇₈ 03:56, 23 March 2010 (UTC)[reply]

Claim About the Skvortsov Paper Dubious?

<quote>Finally, in 1998 the first practical O(n) average time algorithms were discovered and published by Alexey V. Skvortsov and Yuri L. Kostyuk.[8]</quote>

This claim was met with much skepticism (well, more like laughter) by the computational geometry group at my university. The origin of the claim may be this masters thesis by Gorkem Safak: http://w3.nada.kth.se/utbildning/grukth/exjobb/rapportlistor/2009/rapporter09/safak_gorkem_09126.pdf

Unfortunately, the link to the Skvortsov paper is broken and I can't seem to find it anywhere else. Does anyone have access to an electronic copy of this paper or know how to contact the authors? — Preceding unsigned comment added by 134.117.27.24 (talk) 21:51, 26 January 2012 (UTC)[reply]

I have checked the issue, and the comment above on the origin of the claim turned out to be false (the "origin" appeared just a decade later than the paper by Skvortsov and Kostyuk).

Link to that russian paper proved correct, the paper is available and looks valid.

You may try tsu.ru if you need to reach the authors.

The contribution looks important, so I restore it in the article.

95.25.208.67 (talk) 11:59, 18 February 2012 (UTC)[reply]

The claim does not violate verifiability rule for Wikipedia. And Delaunay triangulation is clearly applicable and relevant to polygon triangulation. Please don't remove that note. 95.25.208.67 (talk) 18:54, 19 February 2012 (UTC)[reply]

Delaunay triangulation is a completely different problem from polygon triangulation; it is a form of point set triangulation. And linear average time algorithms for Delaunay triangulation of random inputs have been known for a very long time; see e.g. Bentley, Jon Louis; Weide, Bruce W.; Yao, Andrew C. (December 1980), "Optimal Expected-Time Algorithms for Closest Point Problems", ACM Trans. Math. Softw., 6 (4): 563–580, doi:10.1145/355921.355927. —David Eppstein (talk) 20:48, 19 February 2012 (UTC)[reply]

Using monotone polygons -- vertices of points?

"For each point, check if the vertices are both on the same side." Vertices if what, may I ask? Do they mean adjacent points? Other points close to the scan line? —Preceding unsigned comment added by Dave.rudolf (talk • contribs) 06:11, 11 April 2010 (UTC)[reply]

Using Polygon triangulation for rendering

On the web, there are a lot of discussions on rendering that link here. To cater for this audience, I would suggest that the scope of the article be broadened so that it also cover algorithm(s) that use more than n - 2 triangles. I am convinced the time it takes to set up the extra triangles are in most cases less than the time it takes to set up the complicated data structures required by the algorithms currently mentioned in this article.

In particular, an algorithm that fills the polygon similar to water filling the shape from the lowest point will be very simple and use only twice as many triangles as the algorithms that are currently mentioned. -- Nic Roets (talk) 21:17, 21 January 2011 (UTC)[reply]

Is the Euler formuler wrong?

The Article page says:

the total number of ways to triangulate a convex n-gon by non-intersecting diagonals is

(I rewrite as) 4*6*10...(4n-10)/(n-1)!

a solution found by Euler

The 1st number should be 2? I.e., should be as the following?

2*6*10...(4n-10)/(n-1)!

Special cases - fan from single concave vertex

Is it worthy of note in the Special cases section that a polygon having only 1 concave vertex can also be trivially triangulated with a fan originating from that concave vertex? Cebderby (talk) 11:20, 11 August 2020 (UTC)[reply]

Depends — do you have published reliable sources for that special case? —David Eppstein (talk) 16:50, 11 August 2020 (UTC)[reply]