ผลต่างระหว่างรุ่นของ "โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม"

 
==== รหัสเทียม ====
 
<br />
Input: Monotone polygon P<br />
Output: Set of triangles<br />
: Sort the n vertices belonging to polygon P with respect to x-coordinate and store them in V.<br />
: Initialize sweep-line active list L<br />
:: L = a list with the first two points of V<br />
: WHILE V is not empty DO<br />
:: /* Extract the next vertex from V */<br />
:: p = MIN (V) <br />
:: IF (p is opposite to points in L) THEN<br />
::: WHILE |L| > 1 DO<br />
:::: Output Triangle {First (L), Second (L),p}<br />
:::: REMOVE (FIRST (L)) <br />
::: Add p to L<br />
ELSE
::ELSE<br />
::: WHILE (Angle{Last (L), Previous (Last (L)), p}is convex .AND. |L| > 1) DO<br />
:::: Output Triangle {last (L), Previous (last), p}<br />
:::: REMOVE last (L) <br />
::: /* The angle is reflex or cardinality of L is 1 */<br />
::: Add p to L<br />
 
=== ความซับซ้อนในการคำนวณ ===
โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นเป็นปัญหาที่มีการคิดกันมานานแล้วว่าจะสามารถทำให้ได้ไวกว่า O (n log n) ได้หรือไม่ ในปี 1990 นั้น [[David G. Kirkpatrick]],[[ Maria M. Klawe]], [[Robert E. Tarjan]] ได้ค้นพบอัลกอริทึมที่ใช้เวลาเพียง O (n log log n) สำหรับวิธีใช้อัลกอริทึมแบบสุ่มนั้นเช่นอัลกอริทึมของ [[Seidel's]] or [[Clarkson et al.'s]], ใช้เวลาเป็น O (n log* n) ซึ่งในความเป็นจริงแล้วแทบไม่ต่างอะไรกับ O (n) เลย <br /> <br />
6,995

การแก้ไข