ในการสร้างตาข่าย (mesh generation ) การปรับแต่งแบบเดลาเนย์ (Delaunay refinements)เป็นอัลกอริธึมสำหรับการสร้างตาข่ายโดยอาศัยหลักการของการเพิ่มจุดสไตเนอร์ (Steiner points)ให้กับรูปทรงเรขาคณิตของข้อมูลป้อนเข้าที่จะสร้างตาข่าย ในลักษณะที่ทำให้การสร้างสามเหลี่ยมแบบเดลาเนย์ (Delaunay triangulation ) หรือ การสร้างสามเหลี่ยมแบบเดลาเนย์ที่มีข้อจำกัด ( constrained Delaunay triangulation)ของข้อมูลป้อนเข้าที่เพิ่มเข้ามานั้นตรงตามข้อกำหนดด้านคุณภาพของแอปพลิเคชันการสร้างตาข่าย

เมื่อทำการจำลองด้วยคอมพิวเตอร์ เช่นพลศาสตร์ของไหลเชิงคำนวณ (Computational Fluid Dynamics : CT) เราเริ่มต้นด้วยแบบจำลอง เช่น โครงร่าง 2 มิติของส่วนปีกเครื่องบิน ข้อมูลป้อนเข้าสำหรับวิธีไฟไนต์เอเลเมนต์ 2 มิติ จะต้องอยู่ในรูปของสามเหลี่ยมที่เติมเต็มพื้นที่ทั้งหมด และแต่ละสามเหลี่ยมจะต้องเติมด้วยวัสดุชนิดเดียว – ในตัวอย่างนี้คือ "อากาศ" หรือ "ปีก" สามเหลี่ยมที่ยาวและแคบจะไม่สามารถจำลองได้อย่างแม่นยำ เวลาในการจำลองโดยทั่วไปจะแปรผันตรงกับจำนวนสามเหลี่ยม ดังนั้นจึงต้องการลดจำนวนสามเหลี่ยมให้น้อยที่สุด ในขณะที่ยังคงใช้สามเหลี่ยมจำนวนมากพอที่จะให้ผลลัพธ์ที่แม่นยำพอสมควร – โดยทั่วไปจะใช้ตารางแบบไม่เป็นระเบียบ (unstructured grid ) คอมพิวเตอร์จะใช้อัลกอริทึมการสร้างตาข่าย (meshing algorithm) เพื่อแปลงแบบจำลองรูปหลายเหลี่ยมให้เป็นสามเหลี่ยมที่เหมาะสมสำหรับวิธีไฟไนต์เอเลเมนต์

อัลกอริทึมที่สองของ Chewใช้ ระบบ เชิงเส้นแบบแบ่งส่วน (PLS) และส่งคืนการสร้างสามเหลี่ยม Delaunay ที่มีข้อจำกัดเฉพาะสามเหลี่ยมคุณภาพ โดยคุณภาพจะถูกกำหนดโดยมุมต่ำสุดในสามเหลี่ยม พัฒนาโดย L. Paul Chew สำหรับการสร้างตาข่ายพื้นผิวที่ฝังอยู่ในพื้นที่สามมิติ^{[ 1 ]}อัลกอริทึมที่สองของ Chew ได้รับการนำมาใช้เป็นตัวสร้างตาข่ายสองมิติเนื่องจากมีข้อได้เปรียบในทางปฏิบัติมากกว่าอัลกอริทึมของ Ruppertในบางกรณี และเป็นตัวสร้างตาข่ายคุณภาพเริ่มต้นที่ใช้งานในแพ็คเกจ Triangle ที่มีให้ใช้งานฟรี^{[ 2 ]}อัลกอริทึมที่สองของ Chew รับประกันว่าจะสิ้นสุดและสร้าง ตาข่ายที่มี ขนาดคุณลักษณะเฉพาะที่ไล่ระดับโดยมีมุมต่ำสุดประมาณ 28.6 องศา^{[ 3 ]}

อัลกอริทึมเริ่มต้นด้วยการสร้างสามเหลี่ยมเดอลานีย์แบบมีข้อจำกัดของจุดยอดอินพุต ในแต่ละขั้นตอนจุดศูนย์กลางวงกลมล้อมรอบของสามเหลี่ยมคุณภาพต่ำจะถูกแทรกเข้าไปในสามเหลี่ยมที่สร้างไว้ โดยมีข้อยกเว้นหนึ่งประการ: หากจุดศูนย์กลางวงกลมล้อมรอบอยู่ด้านตรงข้ามของส่วนของเส้นตรงอินพุตกับสามเหลี่ยมคุณภาพต่ำ จุดกึ่งกลางของส่วนของเส้นตรงนั้นจะถูกแทรกเข้าไป นอกจากนี้ จุดศูนย์กลางวงกลมล้อมรอบใดๆ ที่เคยแทรกไว้ภายในทรงกลมเส้นผ่านศูนย์กลางของส่วนของเส้นตรงเดิม (ก่อนที่จะถูกแบ่ง) จะถูกลบออกจากสามเหลี่ยมที่สร้างไว้ การแทรกจุดศูนย์กลางวงกลมล้อมรอบจะทำซ้ำจนกว่าจะไม่มีสามเหลี่ยมคุณภาพต่ำเหลืออยู่

กราฟเส้นตรงระนาบอินพุต

ผลลัพธ์ที่สอดคล้องกับการสร้างสามเหลี่ยมเดลานีย์

ตัวอย่างของอัลกอริทึมของรูเพิร์ต

อัลกอริทึมของ Ruppertรับกราฟเส้นตรงระนาบ (หรือในมิติที่สูงกว่าสอง ระบบ เชิงเส้นแบบแบ่งส่วน ) และส่งคืนการสร้างสามเหลี่ยม Delaunay ที่สอดคล้องกันของสามเหลี่ยมคุณภาพเท่านั้น สามเหลี่ยมจะถือว่ามีคุณภาพต่ำหากมีอัตราส่วนรัศมีวงกลมล้อมรอบต่อขอบที่สั้นที่สุดมากกว่าเกณฑ์ที่กำหนดไว้ ค้นพบโดย Jim Ruppert ในช่วงต้นทศวรรษ 1990 ^{[ 4 ]} "อัลกอริทึมของ Ruppert สำหรับการสร้างตาข่ายคุณภาพสองมิติอาจเป็น อัลกอริทึม การสร้างตาข่ายที่รับประกันทางทฤษฎีเป็นครั้งแรกที่น่าพอใจอย่างแท้จริงในทางปฏิบัติ" ^{[ 5 ]}

ฟังก์ชัน Ruppert( points , segments , threshold ) คือT := DelaunayTriangulation( points ) Q := เซตของส่วนที่ถูกรุกล้ำและสามเหลี่ยมคุณภาพต่ำ ในขณะที่Q ไม่ว่างเปล่า: // ลูปหลักถ้าQมีส่วนs อยู่ : แทรกจุดกึ่งกลางของsลงในT มิฉะนั้นQจะมีสามเหลี่ยมคุณภาพต่ำt : ถ้าจุดศูนย์กลางวงกลมล้อมรอบของtล้ำเข้าไปในส่วนของเส้นตรงs : เพิ่มs ลง ในQมิ ฉะนั้น : แทรกจุดศูนย์กลางวงกลมล้อมรอบของtลงในT จบถ้าจบถ้า อัปเดตQ จบในขณะที่ส่งคืนT สิ้นสุด Ruppert

• ขนาดคุณลักษณะเฉพาะที่
• ตาข่ายรูปหลายเหลี่ยม
• เท็ตเจน
• แผนภาพโวโรนอย

• ริโน, ลอเรนต์. "การสร้างสามเหลี่ยมและตาข่ายแบบสอดคล้องกันใน 2 มิติ" . สืบค้นเมื่อ28 ธันวาคม 2018 .

• เชวชุก, โจนาธาน. "Triangle: โปรแกรมสร้างตาข่ายคุณภาพสองมิติและตัวสร้างสามเหลี่ยมเดลานีย์" . สืบค้นเมื่อ28 ธันวาคม 2018 .

• Si, Hang (2015). "TetGen: เครื่องมือสร้างตาข่ายทรงสี่เหลี่ยมด้านเท่าคุณภาพสูงและเครื่องมือสร้างสามเหลี่ยมเดลานีย์ 3 มิติ" . เก็บถาวรจากต้นฉบับเมื่อวันที่ 29 ธันวาคม 2018 . สืบค้นเมื่อเมื่อวันที่ 28 ธันวาคม 2018 .{{cite web}}: CS1 maint: bot: สถานะ URL เดิมไม่ทราบ ( ลิงก์ )