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?

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]