ในเรขาคณิตเชิงคำนวณการสร้างสามเหลี่ยมของรูปหลายเหลี่ยมคือ ^{การแบ่งพื้นที่รูปหลายเหลี่ยม (รูปหลายเหลี่ยมแบบง่าย) P ออกเป็นเซตของสามเหลี่ยม [} 1 ]กล่าวคือการหาเซตของสามเหลี่ยมที่มี^{พื้นที่ภายใน}ที่ไม่ตัดกันเป็นคู่ๆ ซึ่งผลรวม ของสามเหลี่ยมเหล่านั้น คือP

อาจมองการสร้างรูปสามเหลี่ยมเป็นกรณีพิเศษของกราฟเส้นตรงระนาบได้ เมื่อไม่มีรูหรือจุดเพิ่มเติม การสร้างรูปสามเหลี่ยมจะสร้างกราฟ นอกระนาบสูงสุด

เมื่อเวลาผ่านไป มีการเสนออัลกอริทึมจำนวนมากเพื่อใช้ในการสร้างรูปสามเหลี่ยมจากรูปหลายเหลี่ยม

การแปลง รูปหลายเหลี่ยมนูน ใดๆ ให้เป็นรูปสามเหลี่ยมแบบพัดนั้นทำได้ง่ายและรวดเร็วโดยการลากเส้นทแยงมุมจากจุดยอดหนึ่งไปยังจุดยอดอื่นๆ ที่ไม่ใช่จุดยอดเพื่อนบ้านที่ใกล้ที่สุด

จำนวนวิธีทั้งหมดในการสร้างรูปสามเหลี่ยมด้านเท่าnด้าน นูน โดยใช้เส้นทแยงมุมที่ไม่ตัดกันคือจำนวนคาตาลันลำดับ ที่ ( n − 2) ซึ่งเท่ากับ

${\displaystyle {\frac {n(n+1)...(2n-4)}{(n-2)!}}}$,

สูตรที่ค้นพบโดยเลออนฮาร์ด ออยเลอร์^{[ 2 ]}

วิธีหนึ่งในการสร้างรูปสามเหลี่ยมจากรูปหลายเหลี่ยมอย่างง่ายนั้นอาศัยทฤษฎีสองหูเนื่องจากรูปหลายเหลี่ยมอย่างง่ายใดๆ ที่มีจุดยอดอย่างน้อย 4 จุดโดยไม่มีรูจะมี " หู " อย่างน้อยสองอัน ซึ่งเป็นรูปสามเหลี่ยมที่มีด้านสองด้านเป็นขอบของรูปหลายเหลี่ยมและด้านที่สามอยู่ภายในรูปหลายเหลี่ยมโดยสมบูรณ์^{[ 3 ]}จากนั้นอัลกอริทึมจะประกอบด้วยการค้นหาหูดังกล่าว ลบออกจากรูปหลายเหลี่ยม (ซึ่งส่งผลให้เกิดรูปหลายเหลี่ยมใหม่ที่ยังคงตรงตามเงื่อนไข) และทำซ้ำจนกว่าจะเหลือรูปสามเหลี่ยมเพียงอันเดียว

อัลกอริทึมนี้ง่ายต่อการใช้งาน แต่ช้ากว่าอัลกอริทึมอื่นๆ และใช้งานได้เฉพาะกับรูปหลายเหลี่ยมที่ไม่มีรูเท่านั้น การใช้งานที่เก็บรายการจุดยอดนูนและจุดยอดเว้าแยกกันจะใช้ เวลา O( n² ⁾วิธีนี้เรียกว่าการตัดหูและบางครั้งเรียก ว่า การเล็มหู อัลกอริทึมที่มีประสิทธิภาพสำหรับการตัดหูถูกค้นพบโดย Hossam ElGindy, Hazel Everett และGodfried Toussaint ^{[ 4 ]}

รูปหลายเหลี่ยมแบบง่ายจะเป็นแบบโมโนโทนเมื่อเทียบกับเส้นตรงLถ้าเส้นตรงใดๆ ที่ตั้งฉากกับLตัดกับรูปหลายเหลี่ยมไม่เกินสองครั้งรูปหลายเหลี่ยมแบบโมโนโทนสามารถแบ่งออกเป็นสองสายโซ่ แบบโมโนโทน ได้ รูปหลายเหลี่ยมที่เป็นแบบโมโนโทนเมื่อเทียบกับแกน y เรียกว่าแบบ y-โมโนโทน รูปหลายเหลี่ยมแบบโมโนโทนที่มี จุดยอด nจุดสามารถสร้างเป็นรูปสามเหลี่ยมได้ใน เวลา O( n )สมมติว่ารูปหลายเหลี่ยมที่กำหนดเป็นแบบ y-โมโนโทนอัลกอริทึมแบบโลภจะเริ่มต้นด้วยการเดินบนสายโซ่หนึ่งของรูปหลายเหลี่ยมจากบนลงล่างในขณะที่เพิ่มเส้นทแยงมุมเมื่อใดก็ตามที่เป็นไปได้^{[ 1 ]}จะเห็นได้ง่ายว่าอัลกอริทึมนี้สามารถนำไปใช้กับรูปหลายเหลี่ยมแบบโมโนโทนใดๆ ก็ได้

รูปหลายเหลี่ยมโมโนโทนสามารถสร้างเป็นรูปสามเหลี่ยมได้ในเวลาเชิงเส้นโดยใช้อัลกอริทึมของA. Fournierและ DY Montuno ^{[ 5 ]}หรืออัลกอริทึมของGodfried Toussaint ^{[ 6 ]}

หากรูปหลายเหลี่ยมไม่ใช่รูปหลายเหลี่ยมเอกรูป สามารถแบ่งออกเป็นรูปหลายเหลี่ยมย่อยเอกรูปได้ในเวลาO( n log n ) โดยใช้ แนวทางกวาดเส้น อัลกอริทึมนี้ไม่จำเป็นต้องให้รูปหลายเหลี่ยมเป็นรูปหลายเหลี่ยมแบบง่าย ดังนั้นจึงสามารถนำไปใช้กับรูปหลายเหลี่ยมที่มีรูได้โดยทั่วไป อัลกอริทึมนี้สามารถสร้างรูปสามเหลี่ยมจากการแบ่งย่อยระนาบที่มี จุดยอด n จุดได้ ในเวลาO( n log n ) โดยใช้ พื้นที่O( n ) ^{[ 1 ]}

กราฟที่มีประโยชน์อย่างหนึ่งที่มักเกี่ยวข้องกับการแบ่งรูปหลายเหลี่ยมP ออกเป็นรูปสามเหลี่ยม คือกราฟคู่ (dual graph ) เมื่อกำหนดการแบ่งรูปหลายเหลี่ยมP ออกเป็นรูปสามเหลี่ยม T _Pแล้วเราจะนิยามกราฟG ( T _P )ว่าเป็นกราฟที่มีเซตของจุดยอดเป็นรูปสามเหลี่ยมของT _Pโดยที่จุดยอด (รูปสามเหลี่ยม) สองจุดจะอยู่ติดกันก็ต่อเมื่อมีเส้นทแยงมุมร่วมกัน จะเห็นได้ง่ายว่าG ( T _P )เป็นต้นไม้ที่มีดีกรีสูงสุด 3

จนกระทั่งปี 1988 การที่รูปหลายเหลี่ยมอย่างง่ายสามารถสร้างเป็นรูปสามเหลี่ยมได้เร็วกว่า เวลา O( n log n )นั้นเป็นปัญหาที่ยังเปิดอยู่ในการคำนวณเรขาคณิต^{[ 1 ]}จากนั้นTarjan & Van Wyk (1988)ได้ค้นพบอัลกอริทึมการสร้างรูปสามเหลี่ยมที่มีเวลาO( n log log n ) ^{[ 7 ]}ซึ่งต่อมาได้รับการทำให้ง่ายขึ้นโดยKirkpatrick, Klawe & Tarjan (1992) [ ^{8 ] มี}วิธีการปรับปรุงหลายวิธีที่มีความซับซ้อนO( n log ^* n ) (ในทางปฏิบัติ แทบจะแยกไม่ออกจากเวลาเชิงเส้น ) ตามมา^{[ 9 ] [ 10 ] [ 11 ]}

เบอร์นาร์ด ชาเซลล์แสดงให้เห็นในปี 1991 ว่ารูปหลายเหลี่ยมแบบง่ายใดๆ ก็สามารถสร้างเป็นรูปสามเหลี่ยมได้ในเวลาเชิงเส้น แม้ว่าอัลกอริทึมที่เสนอจะซับซ้อนมากก็ตาม^{[ 12 ]}นอกจากนี้ยังมีอัลกอริทึมแบบสุ่มที่ง่ายกว่าซึ่งมีเวลาเฉลี่ยเชิงเส้นอีกด้วย^{[ 13 ]}

อัลกอริทึมการแยกส่วนของ Seidel ^{[ 10 ]}และวิธีการสร้างสามเหลี่ยมของ Chazelle ได้รับการอธิบายโดยละเอียดในLi & Klette (2011 ) ^{[ 14 ]}

ความซับซ้อนเชิงเวลาของการแบ่งรูปสามเหลี่ยมของรูปหลายเหลี่ยมn จุดยอด ที่มีรูนั้นมีขอบเขตล่างΩ( n log n ) ในแบบจำลองต้นไม้การคำนวณ เชิงพีชคณิต ^{[ 1 ]}เป็นไปได้ที่จะคำนวณจำนวนการแบ่งรูปสามเหลี่ยมที่แตกต่างกันของรูปหลายเหลี่ยมแบบง่ายในเวลาพหุนามโดยใช้การเขียนโปรแกรมแบบไดนามิกและ (โดยอิงจากอัลกอริทึมการนับนี้) เพื่อสร้าง การแบ่งรูปสามเหลี่ยม แบบสุ่มอย่างสม่ำเสมอในเวลาพหุนาม^{[ 15 ]}อย่างไรก็ตาม การนับการแบ่งรูปสามเหลี่ยมของรูปหลายเหลี่ยมที่มีรูนั้นเป็น ปัญหา #P-completeทำให้ไม่น่าจะสามารถทำได้ในเวลาพหุนาม^{[ 16 ]}

• ปัญหาการสร้างรูปสามเหลี่ยมทั้งสองแบบเป็นกรณีพิเศษของการสร้างรูปสามเหลี่ยม (เรขาคณิต)และเป็นกรณีพิเศษของ การแบ่ง รูปหลายเหลี่ยม
• การสร้างสามเหลี่ยมด้วยน้ำหนักต่ำสุดคือการสร้างสามเหลี่ยมที่มีเป้าหมายคือการลดความยาวด้านรวมให้เหลือน้อยที่สุด
• การสร้างรูปสามเหลี่ยมจากชุดจุดคือการสร้างรูปสามเหลี่ยมจากส่วนนูนของชุดจุด การสร้าง รูปสามเหลี่ยมแบบเดอลานีย์เป็นอีกวิธีหนึ่งในการสร้างรูปสามเหลี่ยมจากชุดจุด
• แอสโซซิอาเฮดรอนเป็นรูปทรงหลายเหลี่ยมที่มีจุดยอดสอดคล้องกับการแบ่งรูปหลายเหลี่ยมแบบนูนออกเป็นรูปสามเหลี่ยม
• การครอบคลุมรูปหลายเหลี่ยมด้วยสามเหลี่ยมซึ่งสามเหลี่ยมเหล่านั้นอาจซ้อนทับกันได้
• การปูพื้นด้วยรูปหลายเหลี่ยม โดยมีเป้าหมายคือการปูพื้นที่ทั้งหมดด้วยรูปหลายเหลี่ยมที่มีรูปร่างตามที่กำหนดไว้ล่วงหน้า

• กฎที่ไม่ใช่ศูนย์
• หมายเลขคาตาลัน
• กราฟระนาบ
• กราฟพลิก

• สาธิตในรูปแบบไฟล์ Flash swf โดยใช้อัลกอริทึม Sweep Line
• คำอธิบายของซงโฮเกี่ยวกับเทสเซลเลเตอร์ GLU ของ OpenGL