สมการสำหรับเซตจำกัดของจุด S เป็นปัญหาของการหาสามเหลี่ยมของส่วนนูน CH(S) ที่ล้อมรอบจุดทั้งหมดของเซต S ส่วนของเส้นตรงไม่สามารถตัดกันระหว่างการหารูปสามเหลี่ยม - พวกมันสามารถบรรจบกันที่จุดร่วมที่เป็นของเซต S เท่านั้น เนื่องจากเป็นเส้นตรง ส่วนของเส้นตรงปิดสามเหลี่ยมเราจะถือว่ามันเป็นขอบ บนมะเดื่อ 1 แสดงรูปสามเหลี่ยมที่แตกต่างกันสองแบบสำหรับจุดชุดเดียวกัน (เราจะละเว้นวงกลมที่วาดในรูปเหล่านี้ชั่วคราว)

ข้าว. หนึ่ง

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

เซตของจุดใดๆ ก็ตาม ยกเว้นในบางกรณีเล็กน้อย อนุญาตให้มีมากกว่าหนึ่งวิธีในการวิเคราะห์ แต่ในขณะเดียวกันก็มีคุณสมบัติที่น่าทึ่ง: วิธีใด ๆ ของรูปสามเหลี่ยมสำหรับชุดที่กำหนดจะกำหนดจำนวนรูปสามเหลี่ยมเท่ากัน ซึ่งตามมาจากทฤษฎีบท:

ทฤษฎีบทเกี่ยวกับสมการของเซตของจุดสมมติว่าชุดของจุด S มี n>3 จุด และไม่ใช่ทั้งหมดที่เป็นเส้นตรง นอกจากนี้ ฉัน ชี้จากพวกเขาเป็นภายใน (กล่าวคือ อยู่ภายในตัวถังนูน CH(S) จากนั้น ด้วยวิธีการใด ๆ ในการหารูปสามเหลี่ยมของชุด S จะได้สามเหลี่ยม n + i - 2 รูป

ในการพิสูจน์ทฤษฎีบท ขั้นแรกเราจะพิจารณาสามเหลี่ยมของจุดขอบเขต n-i เนื่องจากเป็นจุดยอดทั้งหมดของรูปหลายเหลี่ยมนูน สามเหลี่ยมดังกล่าวจะส่งผลให้ (n - i) - 2 สามเหลี่ยม (ตรวจสอบได้ไม่ยากและยิ่งกว่านั้นยังแสดงได้ว่ารูปสามเหลี่ยมใดๆ ตามอำเภอใจรูปหลายเหลี่ยมด้าน m - นูนหรือไม่นูน - มี m - 2 สามเหลี่ยม) ทีนี้มาตรวจสอบว่าจะเกิดอะไรขึ้นกับรูปสามเหลี่ยมเมื่อเพิ่มจุดภายใน i ที่เหลือ ทีละจุด เราอ้างว่าการบวกแต่ละจุดดังกล่าวทำให้จำนวนสามเหลี่ยมเพิ่มขึ้นสองเท่า เมื่อเพิ่มจุดภายใน จะเกิดสองสถานการณ์ ดังแสดงในรูปที่ 2. ประการแรก จุดอาจอยู่ภายในสามเหลี่ยมบางรูป จากนั้นสามเหลี่ยมดังกล่าวจะถูกแทนที่ด้วยสามเหลี่ยมใหม่สามอัน ประการที่สอง หากจุดนั้นตรงกับขอบด้านใดด้านหนึ่งของรูปสามเหลี่ยม รูปสามเหลี่ยมสองรูปแต่ละรูปที่อยู่ติดกับขอบนี้จะถูกแทนที่ด้วยรูปสามเหลี่ยมใหม่สองรูป หลังจากบวกจุด r ทั้งหมดแล้ว จำนวนสามเหลี่ยมทั้งหมดจะเป็น (n - i - 2) + (2i) หรือแค่ n + i - 2

ข้าว. 2

ในส่วนนี้ เรานำเสนออัลกอริทึมสำหรับการสร้างรูปสามเหลี่ยมชนิดพิเศษที่เรียกว่า Delaunay triangulation รูปสามเหลี่ยมนี้มีความสมดุลที่ดีในแง่ที่ว่ารูปสามเหลี่ยมที่เกิดขึ้นมักจะเท่ากัน ตัวอย่างเช่น รูปสามเหลี่ยมที่แสดงในรูป 1a สามารถนำมาประกอบกับประเภทของสามเหลี่ยม Delaunay และในรูปที่ รูปสามเหลี่ยมในรูปที่ 1b มีรูปสามเหลี่ยมที่ยาวมากหลายรูปและไม่สามารถนำมาประกอบกับประเภท Delaunay ได้ บนมะเดื่อ 3 แสดงตัวอย่างรูปสามเหลี่ยม Delaunay สำหรับชุดของจุดจำนวนมาก

ข้าว. 3

เพื่อสร้างรูปสามเหลี่ยม Delaunay เราต้องการคำจำกัดความใหม่หลายอย่าง ชุดของจุดจะถือว่าเป็นวงกลมหากมีวงกลมที่จุดทั้งหมดของชุดนั้นอยู่ วงกลมดังกล่าวจะถูกกำหนดเป็นชุดของจุดที่กำหนด วงกลมที่มีเส้นรอบวงสำหรับรูปสามเหลี่ยมจะผ่านจุดยอดทั้งสามจุด กล่าวกันว่าวงกลมไม่มีจุดเมื่อเทียบกับเซตของจุด S ที่กำหนด หากไม่มีจุดจากเซต S ภายในวงกลม แต่อย่างไรก็ตาม จุดจากเซต S สามารถอยู่บนวงกลมที่ปราศจากจุดมากที่สุด

รูปสามเหลี่ยมของชุดของจุด S จะเป็นรูปสามเหลี่ยมของ Delaunay ถ้าวงกลมที่ล้อมรอบสำหรับสามเหลี่ยมแต่ละรูปไม่มีจุด ในแผนภาพสามเหลี่ยมในรูป 1a แสดงวงกลมสองวงที่ชัดเจนไม่มีจุดอื่นๆ อยู่ภายใน (คุณสามารถวาดวงกลมสำหรับสามเหลี่ยมอื่นๆ เพื่อให้แน่ใจว่าไม่มีจุดในชุดด้วย) กฎนี้ไม่ได้สังเกตในไดอะแกรมของรูปที่ 16 - จุดหนึ่งของสามเหลี่ยมอีกจุดหนึ่งเข้าไปในวงกลมที่วาด ดังนั้น Griangulation นี้ไม่ได้อยู่ในประเภท Delaunay

สามารถตั้งสมมติฐานได้สองข้อเกี่ยวกับจุดในชุด S เพื่อลดความซับซ้อนของอัลกอริทึมการหารูปสามเหลี่ยม ขั้นแรก เพื่อให้การหาสมการมีอยู่จริง เราต้องถือว่าเซต S มีจุดอย่างน้อยสามจุดและจุดเหล่านั้นไม่ได้อยู่ในแนวเดียวกัน ประการที่สอง เพื่อให้รูปสามเหลี่ยม Delaunay มีเอกลักษณ์เฉพาะตัว จำเป็นจะต้องไม่มีจุดสี่จุดจากเซต S อยู่บนวงกลมที่มีเส้นรอบวงวงเดียวกัน เป็นเรื่องง่ายที่จะเห็นว่าหากไม่มีสมมติฐานดังกล่าว รูปสามเหลี่ยม Delaunay จะไม่ซ้ำกัน เนื่องจากจุด 4 จุดบนวงกลมหนึ่งวงทำให้เราสามารถรับรู้รูปสามเหลี่ยม Delaunay ที่แตกต่างกันสองแบบ

อัลกอริทึมของเราทำงานโดยสร้างรูปสามเหลี่ยมปัจจุบันทีละรูปอย่างต่อเนื่อง ในขั้นต้น รูปสามเหลี่ยมปัจจุบันประกอบด้วยขอบด้านเดียวของเปลือก หลังจากอัลกอริทึมเสร็จสิ้น รูปสามเหลี่ยมปัจจุบันจะกลายเป็นรูปสามเหลี่ยม Delaunay ในการวนซ้ำแต่ละครั้ง อัลกอริทึมจะมองหาสามเหลี่ยมใหม่ที่เชื่อมต่อกับ ชายแดนรูปสามเหลี่ยมปัจจุบัน

คำจำกัดความของขอบเขตขึ้นอยู่กับรูปแบบการจำแนกขอบของสามเหลี่ยม Delaunay ต่อไปนี้ เทียบกับรูปสามเหลี่ยมปัจจุบัน แต่ละขอบสามารถ นอนหลับ, มีชีวิตอยู่หรือ ตาย:

• ซี่โครงอยู่เฉยๆ: ขอบสามเหลี่ยม Delaunay จะอยู่เฉยๆ หากยังไม่ถูกค้นพบโดยอัลกอริทึม
• ซี่โครงสด: ขอบจะมีชีวิตอยู่หากพบ แต่มีเพียงบริเวณเดียวที่อยู่ติดกันเท่านั้นที่ทราบ
• ซี่โครงตาย: จะถือว่าขอบนั้นตายหากพบและทราบพื้นที่ที่อยู่ติดกันทั้งสองแห่ง

ในขั้นต้น ขอบเดียวที่เป็นของจุด i นูนนั้นยังมีชีวิตอยู่ - ระนาบที่ไม่มีขอบเขตอยู่ติดกับมัน และขอบอื่นๆ ทั้งหมดจะอยู่เฉยๆ เมื่ออัลกอริทึมทำงาน ขอบที่อยู่เฉยๆ ก็จะมีชีวิต แล้วก็ตายไป ขอบเขตในแต่ละขั้นประกอบด้วยชุดของขอบที่มีชีวิต

ในการวนซ้ำแต่ละครั้ง ขอบใด ๆ ของขอบเขตจะถูกเลือกและจะถูกประมวลผลซึ่งประกอบด้วยการค้นหาพื้นที่ที่ไม่รู้จักซึ่งเป็นของขอบ e หากพื้นที่นี้กลายเป็นรูปสามเหลี่ยม f ที่กำหนดโดยจุดสิ้นสุดของ ขอบ e และจุดยอด v ที่สาม จากนั้นขอบ e จะกลายเป็นจุดตาย เนื่องจากตอนนี้ทราบพื้นที่ที่อยู่ติดกันทั้งสองแล้ว ขอบอีกสองด้านของรูปสามเหลี่ยม t จะถูกถ่ายโอนไปยังสถานะต่อไปนี้: จากหลับเป็นมีชีวิตหรือจากมีชีวิตเป็นตาย ที่นี่จุดยอด v จะถูกเรียก ผันด้วยขอบ e มิฉะนั้นหากพื้นที่ที่ไม่รู้จักกลายเป็นระนาบที่ไม่มีที่สิ้นสุด ขอบ e ก็จะตาย ในกรณีนี้ ขอบ e ไม่มีจุดยอดคอนจูเกต

บนมะเดื่อ 4 แสดงการทำงานของอัลกอริทึมซึ่งการกระทำเกิดจากบนลงล่างและบนลงขวา ขอบเขตในแต่ละขั้นจะถูกทำเครื่องหมายด้วยเส้นหนา

อัลกอริทึมถูกนำมาใช้ในโปรแกรม delaunayTriangulate โปรแกรมได้รับอาร์เรย์ s จาก n จุดและส่งคืนรายการของรูปสามเหลี่ยมที่เป็นตัวแทนของรูปสามเหลี่ยม Delaunay การใช้งานใช้คลาสรายการวงแหวนและคลาสจากส่วนโครงสร้างข้อมูลทางเรขาคณิต พจนานุกรมใดๆ ที่สนับสนุนการดำเนินการที่จำเป็นสามารถใช้เป็นคลาสพจนานุกรมได้ ตัวอย่างเช่น คุณสามารถแทนที่ #define Dictionary RandomizedSearchTree

รายการ * (จุด s, int n) ( จุด p; รายการ *สามเหลี่ยม = รายการใหม่ ; พจนานุกรม ชายแดน (edgeCmp); Edge *e = ขอบตัวถัง(s, n); แทรกชายแดน (e); ในขณะที่ (!frontier.isEmpty()) ( e = frontier.removeMin(); if (mate(*e, s, n, p)) ( updateFrontier(frontier, p, e->org); updateFrontier(ชายแดน, e ->ปลายทาง, p); สามเหลี่ยม->แทรก(สามเหลี่ยม(e->org, e->ปลายทาง, p)); ) ลบ e; ) กลับสามเหลี่ยม; )

ข้าว. สี่

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

Int edgeCmp (Edge *a, Edge *b) ( ถ้า (a->org< b->org) ส่งคืน 1; ถ้า (a->org > b->org) ส่งคืน 1; ถ้า (a->dest< b->ปลายทาง) กลับ -1; ถ้า (a->dest > b->dest) คืนค่า 1; กลับ 0; )

แล้วชายแดนเปลี่ยนจากขั้นตอนหนึ่งไปอีกขั้นอย่างไร และฟังก์ชัน updateFrontier เปลี่ยนพจนานุกรมขอบของเส้นขอบอย่างไรเพื่อสะท้อนการเปลี่ยนแปลงเหล่านี้ เมื่อแนบสามเหลี่ยมใหม่ t เข้ากับขอบเขต สถานะของขอบทั้งสามของสามเหลี่ยมจะเปลี่ยนไป ขอบของสามเหลี่ยม t ซึ่งอยู่ติดกับขอบเขตจะกลายเป็นจุดตายจากการมีชีวิต ฟังก์ชัน updateFrontier สามารถละเว้นขอบนี้ได้ เนื่องจากต้องถูกลบออกจากพจนานุกรมแล้วเมื่อเรียกใช้ฟังก์ชัน removeMin ขอบที่เหลือทั้งสองด้านของรูปสามเหลี่ยม t เปลี่ยนสถานะจากหลับเป็นมีชีวิตหากไม่เคยเขียนลงในพจนานุกรมมาก่อน หรือจากมีชีวิตเป็นตายหากขอบมีอยู่ในพจนานุกรมแล้ว บนมะเดื่อ 5 แสดงทั้งสองกรณี ตามรูป เราประมวลผล live edge af และหลังจากพบว่าจุด b เชื่อมต่อกันแล้ว เราก็เพิ่มสามเหลี่ยม afb เข้ากับรูปสามเหลี่ยมปัจจุบัน จากนั้นเรามองหา edge fb ในพจนานุกรม และเนื่องจากมันยังไม่มีและถูกค้นพบเป็นครั้งแรก สถานะของมันจึงเปลี่ยนจากหลับเป็นมีชีวิต ในการแก้ไขพจนานุกรม เราจะหมุนขอบ fb เพื่อให้พื้นที่ที่ไม่รู้จักซึ่งอยู่ติดกันอยู่ทางด้านขวาและเขียนขอบนี้ลงในพจนานุกรม จากนั้นเราจะพบขอบ ba ในพจนานุกรม - เนื่องจากอยู่ในนั้นจึงมีชีวิตอยู่ (พื้นที่ที่รู้จักซึ่งอยู่ติดกับมันคือสามเหลี่ยม abc) เนื่องจากพื้นที่ที่ไม่รู้จัก สามเหลี่ยม afb เพิ่งถูกค้นพบ ขอบนี้จึงถูกลบออกจากพจนานุกรม

ฟังก์ชัน updateFrontier แก้ไขพจนานุกรมชายแดน ซึ่งสถานะของขอบเปลี่ยนจากจุด a ไปจุด b:

ข้าว. 5

เป็นโมฆะ updateFrontier(Dictionary &ชายแดน, จุด &a, จุด &b) ( Edge *e = new Edge (a, b); if (frontier.find (e)) frontier.remove(e); else ( e->flip(); frontier.insert( จ); ) )

ฟังก์ชัน hullEdge ค้นหาขอบตัวถังระหว่างจุด n ของอาร์เรย์ ฟังก์ชันนี้ใช้ขั้นตอนการเริ่มต้นและการทำซ้ำครั้งแรกของวิธีการห่อของขวัญ:

Edge *hullEdge (จุด s, int n) ( int m = 0; for (int i = 1; i< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }

ฟังก์ชันสามเหลี่ยมเพียงแค่สร้างและส่งกลับรูปหลายเหลี่ยมสำหรับจุดสามจุดที่ส่งผ่านเป็นพารามิเตอร์:

รูปหลายเหลี่ยม *สามเหลี่ยม (จุด &a, จุด &b, จุด &c) ( รูปหลายเหลี่ยม *t = รูปหลายเหลี่ยมใหม่; t->insert (a); t->insert (b); t->insert (c); return t; )

โมเดล GRID เป็นโมเดลของเซลล์ปกติ

ให้ระบบพิกัด
และ และ
. ชุดผู้ใช้
และขั้นตอนการสุ่มตัวอย่าง
.

,

- พิกัดทางกายภาพของจุด

คำนวณ
และ
,
- ตารางบิต

- ค่าเชิงปริมาณ จริง:

- พารามิเตอร์อัลกอริทึม - จำนวนคะแนน - น้ำหนัก. ยิ่งใกล้จุดน้ำหนักยิ่งมาก

- ระดับของระยะทาง (1 หรือ 2)

ปัจจัยการทำให้เป็นมาตรฐาน:

ยังไง ยิ่งมีค่าเข้าใกล้ 1 มากเท่าไหร่ก็ยิ่งมีการพิจารณาคะแนนที่ถ่วงน้ำหนักมากขึ้นเท่านั้น

นี่คือวิธี IDW - ยาวสำหรับแต่ละ t จำเป็นต้องหาเพื่อนบ้าน สามารถหาชุดเพื่อนบ้านได้อย่างมีประสิทธิภาพ - ใกล้ที่สุด แต่ละจุดสร้าง "หมุด" ที่มีความสูงระดับหนึ่ง ขึ้นอยู่กับความไม่สม่ำเสมอของการกำหนดจุดสำหรับสิ่งนี้
หรือ
เหล่านั้น. แบ่งเป็นภาค ๆ และสร้างในบริเวณใกล้เคียงจุด

ความได้เปรียบ– ความเรียบง่าย

ข้อบกพร่อง:

------ตั๋วใบที่ 14. ดีบุกโมเดล. อัลกอริทึมสามเหลี่ยม Delaunay ------

1) รูปสามเหลี่ยม (ดีบุก)

สามเหลี่ยม– การสร้างฟังก์ชันในรูปของเซตของฟังก์ชันเชิงเส้นทีละส่วน

สามเหลี่ยม– การแก้ไขภายในพื้นที่นูน

สามเหลี่ยมเป็นกราฟระนาบที่มีขอบภายในเป็นรูปสามเหลี่ยม วิธีแทนพื้นที่ในรูปสามเหลี่ยมติดกันโดยไม่ซ้อนทับกัน Triangulation สร้างขึ้นจากชุดของจุดในหลายวิธี

เราต้องการอัลกอริทึมเพื่อสร้างรูปสามเหลี่ยมที่เหมาะสมที่สุด

เครื่องบินผ่าน 3 จุด

1) ค้นหาสามเหลี่ยมที่
;

2)
- เราสร้างสมการของระนาบ

ในการตรวจสอบว่ามีจุดต่างๆ อยู่ภายในสามเหลี่ยมหรือไม่ คุณต้องแทนค่าลงในสมการของเส้น - ขอบของสามเหลี่ยม ถ้าสมการทั้ง 3 สมการ > 0 ข้างใน

ดูโครงสร้าง:

รูปสามเหลี่ยมแต่ละรูปมีจำนวนรูปสามเหลี่ยมเท่ากัน

, ที่ไหน คือจำนวนจุดภายใน
- จำนวนคะแนน

สามเหลี่ยมโลภ

เราเชื่อมต่อจุดทั้งหมดด้วยขอบ เลือกค่าต่ำสุด เพิ่มไปยังรูปสามเหลี่ยม ต่อไป เราจะใช้ค่าต่ำสุดถัดไปที่ไม่ตัดกับค่าต่ำสุดก่อนหน้า เป็นต้น ผลที่ได้คือรูปสามเหลี่ยมโลภ

สามเหลี่ยม Delaunay

จุดของสามเหลี่ยมอื่นๆ จะไม่อยู่ในวงกลมที่ล้อมรอบสามเหลี่ยมใดๆ สร้างด้วยวิธีใดวิธีหนึ่ง

การพลิกคือการพลิกของขอบ ช่วยให้คุณเปลี่ยนจากการหาค่าสามเหลี่ยมแบบเดิมเป็นค่าสามเหลี่ยมแบบ Delaunay หากต้องการตรวจสอบว่าจุดใดเป็นของวงกลมหรือไม่ ให้แทนที่ if< R, то внутри.

สภาพ Delaunay

สมการของวงกลมผ่านจุดสามจุด:

ถ้าน้อยกว่าศูนย์ นอกนั้น - ภายใน

คือภาวะเดลาอูเนย์

อัลกอริทึมสำหรับการสร้างรูปสามเหลี่ยม Delaunay:

1) อยู่ระหว่างการสอบสวนเพิ่มคะแนนเป็นอัลกอริธึมการวนซ้ำอย่างง่าย:

มีชุด
เพิ่มไปยังรูปสามเหลี่ยมการก่อสร้างจะดำเนินการ
พาร์ติชันของรูปสามเหลี่ยม
สร้างใหม่ ในขั้นศูนย์ เราเพิ่มจุดสมมติ 3-4 จุดซึ่งครอบคลุมซองจดหมายของเราอย่างเห็นได้ชัด จุดทั้งหมดอยู่ข้างใน หลังจากที่เราโยนจุดแล้ว ให้ดูว่าสามเหลี่ยมใดที่โดน แบ่งออกเป็น 3 ส่วนสำหรับแต่ละสามเหลี่ยม เราจะตรวจสอบเงื่อนไขของ Delaunay และพลิกขอบ จำนวนการสร้างใหม่โดยเฉลี่ยคือสาม

ความซับซ้อนทางทฤษฎี

2) วิธีการเร่งความเร็วขึ้นอยู่กับคะแนนที่ขึ้นอยู่กับสถิติ สามเหลี่ยมเมล็ดคือสามเหลี่ยมที่จุดก่อนหน้าตกลงมา จากนั้นเราเชื่อมต่อสองจุด - จุดก่อนหน้าและจุดใหม่

เราย้ายจากจุดแรกไปยังอีกจุดหนึ่ง

คำจำกัดความและคุณสมบัติพื้นฐาน

สามเหลี่ยมคือกราฟระนาบซึ่งพื้นที่ภายในเป็นรูปสามเหลี่ยมทั้งหมด

คุณสมบัติ:

· รูปสามเหลี่ยม Delaunay สอดคล้องแบบหนึ่งต่อหนึ่งกับแผนภาพ Voronoi สำหรับจุดชุดเดียวกัน

· ผลที่ตามมา: หากไม่มีจุดสี่จุดอยู่บนวงกลมเดียวกัน รูปสามเหลี่ยม Delaunay จะไม่ซ้ำกัน

· รูปสามเหลี่ยม Delaunay เพิ่มมุมต่ำสุดระหว่างมุมทั้งหมดของรูปสามเหลี่ยมที่สร้างขึ้นทั้งหมด ดังนั้นจึงหลีกเลี่ยงรูปสามเหลี่ยม "บาง"

· สามเหลี่ยม Delaunay ช่วยเพิ่มผลรวมของรัศมีของลูกบอลที่ถูกจารึกไว้

· Delaunay triangulation ลดการทำงานของ Dirichlet ที่ไม่ต่อเนื่องให้เหลือน้อยที่สุด

· สามเหลี่ยม Delaunay ลดรัศมีสูงสุดของทรงกลมที่ล้อมรอบน้อยที่สุด

· รูปสามเหลี่ยม Delaunay บนระนาบมีผลรวมขั้นต่ำของรัศมีของวงกลมที่ล้อมรอบสามเหลี่ยมในบรรดารูปสามเหลี่ยมที่เป็นไปได้ทั้งหมด

รูปที่ 1 สามเหลี่ยม

สามเหลี่ยมนูนเป็นรูปสามเหลี่ยมที่รูปหลายเหลี่ยมขั้นต่ำที่ล้อมรอบสามเหลี่ยมทั้งหมดเป็นรูปสามเหลี่ยมนูน สามเหลี่ยมที่ไม่นูนเรียกว่าไม่นูน

ภารกิจในการสร้างรูปสามเหลี่ยมจากชุดของจุดสองมิติที่กำหนดคือปัญหาของการเชื่อมต่อจุดที่กำหนดให้กับส่วนที่ไม่ตัดกันเพื่อให้เกิดรูปสามเหลี่ยม

มีการกล่าวว่ารูปสามเหลี่ยมเป็นไปตามเงื่อนไขของ Delaunay หากไม่มีจุดรูปสามเหลี่ยมใด ๆ ที่อยู่ภายในวงกลมที่ล้อมรอบรอบรูปสามเหลี่ยมที่สร้างขึ้น

รูปสามเหลี่ยมเรียกว่าสามเหลี่ยม Delaunay ถ้ามันนูนและเป็นไปตามเงื่อนไข Delaunay

รูปที่ 2 สามเหลี่ยม Delaunay

วิธี Delaunay ลูกบอลเปล่า การก่อสร้างในกรณีทั่วไป

ลองใช้ลูกบอลเปล่าซึ่งเราจะย้ายโดยเปลี่ยนขนาดเพื่อให้สัมผัสจุดของระบบ (A) แต่ยังคงว่างเปล่าอยู่เสมอ

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

รูปที่ 3

ความเรียบง่ายของ Delaunay เติมเต็มพื้นที่โดยไม่มีช่องว่างและการทับซ้อนกัน

ทรงกลมที่อธิบายของซิมเพล็กซ์ใด ๆ ไม่มีจุดอื่น ๆ ของระบบอยู่ภายใน

ให้นี่เป็นจุด j มาเพิ่มรัศมีของลูกบอลกันต่อไปโดยรักษาจุดทั้งสองไว้บนพื้นผิว เพิ่มขึ้น ลูกบอลจะไปถึงจุดที่สามของระบบ จุด k ในกรณีสองมิติ "วงกลมว่าง" ของเราจะได้รับการแก้ไขในขณะนี้ นั่นคือ มันเป็นไปไม่ได้ที่จะเพิ่มรัศมีของมันต่อไปในขณะที่ปล่อยให้วงกลมว่างเปล่า ในเวลาเดียวกันเราจะเปิดเผยการกำหนดค่าสองมิติเบื้องต้นของสามจุด (i, j, k) ซึ่งกำหนดรูปสามเหลี่ยมบางรูปซึ่งมีลักษณะเฉพาะคือไม่มีจุดอื่น ๆ ของระบบ (A) ภายในขอบเขต วงกลม. ในสามมิติ ลูกบอลไม่ได้ถูกกำหนดด้วยสามจุด มาเพิ่มรัศมีกันต่อไปโดยรักษาจุดที่พบทั้งสามไว้บนพื้นผิว สิ่งนี้จะเป็นไปได้จนกว่าพื้นผิวของลูกบอลจะตรงกับจุดที่สี่ของระบบ หลังจากนั้นการเคลื่อนที่และการเติบโตของลูกบอลเปล่าจะเป็นไปไม่ได้ จุดสี่จุดที่พบ (i, j, k, l) กำหนดจุดยอดของจัตุรมุขซึ่งมีลักษณะเฉพาะคือไม่มีจุดอื่นของระบบ (A) ภายในทรงกลมที่ล้อมรอบ จัตุรมุขดังกล่าวเรียกว่า Delaunay simplex

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

เราได้สร้าง Delaunay simplex ขึ้นมาหนึ่งลูก อย่างไรก็ตาม โดยการวางลูกบอลเปล่าในที่ต่างๆ และทำขั้นตอนเดียวกันซ้ำ จะสามารถกำหนดจุดอื่นๆ ได้ มีการระบุไว้ว่าชุดของ Delaunay simplices ของระบบ (A) ทั้งหมดเติมเต็มช่องว่างโดยไม่มีการทับซ้อนและช่องว่าง เช่น ใช้การแบ่งพื้นที่ แต่คราวนี้เป็นจัตุรมุข การแบ่งนี้เรียกว่า พาร์ติชัน Delaunay(รูปที่ 3)

การประยุกต์ใช้รูปสามเหลี่ยม Delaunay

มักใช้รูปสามเหลี่ยม Delaunay ในปริภูมิยุคลิด ต้นไม้สแปนนิงแบบยุคลิดขั้นต่ำรับประกันว่าจะอยู่ในรูปสามเหลี่ยม Delaunay ดังนั้นอัลกอริทึมบางอย่างจึงใช้รูปสามเหลี่ยม นอกจากนี้ จากสมการสามเหลี่ยม Delaunay ปัญหาเกี่ยวกับพนักงานขายเดินทางแบบยุคลิดก็ได้รับการแก้ไขโดยประมาณแล้ว

ในการแก้ไขแบบ 2 มิติ Delaunay triangulation จะแยกระนาบออกเป็นสามเหลี่ยมที่หนาที่สุดเท่าที่จะเป็นไปได้ หลีกเลี่ยงมุมที่แหลมหรือป้านเกินไป สามเหลี่ยมเหล่านี้สามารถใช้สร้างได้ เช่น การประมาณค่าแบบทวิเนียร์

ปัญหาอีกประการหนึ่งที่มักเกิดขึ้นในภูมิสารสนเทศคือการสร้างพื้นที่ลาดเอียง ที่นี่จำเป็นต้องกำหนดทิศทางที่โดดเด่นของความลาดชันโดยจุดสำคัญและแบ่งพื้นผิวออกเป็นภูมิภาคที่มีทิศทางที่แน่นอน เนื่องจากคำจำกัดความของการเปิดรับแสงไม่สมเหตุสมผลสำหรับส่วนแนวนอนของพื้นผิว ตัวอย่างเช่น พื้นที่ในแนวนอนหรือมีความลาดเอียงเล็กน้อย จะถูกจัดสรรให้กับพื้นที่แยกต่างหาก<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

รูปที่ 4

งานคำนวณค่าความลาดชันมักใช้ในการวิเคราะห์การส่องสว่างของโลก ในเรื่องนี้ จำเป็นต้องคำนึงถึงตำแหน่งปัจจุบันของดวงอาทิตย์เพิ่มเติมด้วย กล่าวคือ การเปิดรับแสงจะคำนวณเป็นทิศทางระหว่างปกติถึงสามเหลี่ยมและทิศทางของดวงอาทิตย์

ดังนั้นแต่ละรูปสามเหลี่ยมสามารถจำแนกตามหลักการของการเป็นของภูมิภาคใดภูมิภาคหนึ่ง หลังจากนั้นคุณเพียงแค่เรียกอัลกอริทึมการเลือกภูมิภาค

สามเหลี่ยมเชิงพื้นที่ Delaunay

ปัญหาในการสร้างเครือข่ายของรูปสามเหลี่ยมที่ไม่ทับซ้อนกันเป็นหนึ่งในปัญหาพื้นฐานในเรขาคณิตเชิงคำนวณและมีการใช้กันอย่างแพร่หลายในคอมพิวเตอร์กราฟิกและระบบสารสนเทศภูมิศาสตร์สำหรับการสร้างแบบจำลองพื้นผิวและการแก้ปัญหาเชิงพื้นที่

เป็นครั้งแรกที่ปัญหาในการสร้างเครือข่ายของรูปสามเหลี่ยมที่ไม่ทับซ้อนกันเกิดขึ้นในปี 1934 ในงานของนักคณิตศาสตร์ชาวโซเวียต บี. เอ็น. เดโลน ซึ่งเป็นผู้กำหนดเงื่อนไขที่เกี่ยวข้องด้วย

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

เครือข่ายของสามเหลี่ยมดังกล่าวเรียกว่าสามเหลี่ยม Delaunay หากเป็นไปตามเงื่อนไขบางประการ:

ไม่มีจุดเริ่มต้นใดอยู่ในวงกลมที่อธิบายไว้รอบๆ สามเหลี่ยมใดๆ (รูปที่ 5.3)

รูปสามเหลี่ยมมีความนูนและเป็นไปตามเงื่อนไขของ Delaunay ที่กำหนดไว้ข้างต้น

ผลรวมของมุมต่ำสุดของรูปสามเหลี่ยมทั้งหมดคือค่าสูงสุดของรูปสามเหลี่ยมที่เป็นไปได้ทั้งหมด

ผลรวมของรัศมีของวงกลมที่ล้อมรอบสามเหลี่ยมนั้นมีค่าน้อยที่สุดในบรรดาสามเหลี่ยมที่เป็นไปได้ทั้งหมด

เกณฑ์ข้อแรกข้างต้นสำหรับการสร้างรูปสามเหลี่ยม Delaunay ที่เรียกว่ารูปวงกลมเป็นหนึ่งในเกณฑ์หลักและถูกตรวจสอบเพื่อหาคู่ของรูปสามเหลี่ยมที่มีใบหน้าเหมือนกัน การตีความเกณฑ์ทางคณิตศาสตร์ตามมาจากรูปที่ 5.3:

(5.2)

มีหลายวิธีในการสร้างรูปสามเหลี่ยม Delaunay ซึ่งเป็นหนึ่งในวิธีที่ได้รับความนิยมมากที่สุดในการสร้างตาข่ายรูปสามเหลี่ยมในช่วงไม่กี่ปีที่ผ่านมา มีการใช้ในระบบ GIS จำนวนมากสำหรับการสร้างแบบจำลองภูมิประเทศ

เมื่อนำไปใช้กับปริภูมิสองมิติ จะมีการกำหนดดังนี้: ระบบของสามเหลี่ยมที่ไม่ซ้อนทับกันซึ่งเชื่อมต่อกันจะมีเส้นรอบวงที่เล็กที่สุดหากไม่มีจุดยอดใดอยู่ในวงกลมใดๆ ที่อธิบายไว้รอบๆ สามเหลี่ยมที่เกิดขึ้น (รูปที่ 5.4)

ข้าว. 5.4. สามเหลี่ยม Delaunay

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

อัลกอริธึมจำนวนมากสำหรับการสร้างรูปสามเหลี่ยม Delaunay ใช้ทฤษฎีบทต่อไปนี้

ทฤษฎีบท 1. รูปสามเหลี่ยม Delaunay สามารถหาได้จากรูปสามเหลี่ยมอื่น ๆ ในระบบจุดเดียวกันโดยสร้างคู่ของรูปสามเหลี่ยมใกล้เคียง ABC และ BCD ที่ไม่เป็นไปตามเงื่อนไขของ Delaunay เป็นคู่ของรูปสามเหลี่ยม ABD และ ACD (รูปที่ 5.5)

ข้าว. 5.5 สร้างรูปสามเหลี่ยมขึ้นใหม่ที่ไม่เป็นไปตามเงื่อนไขของ Delaunay

การดำเนินการสร้างใหม่นี้มักเรียกว่าการพลิกกลับ ทฤษฎีบทนี้อนุญาตให้เราสร้างรูปสามเหลี่ยม Delaunay ตามลำดับ ขั้นแรกสร้างรูปสามเหลี่ยมบางส่วน แล้วจึงปรับปรุงตามลำดับในแง่ของเงื่อนไข Delaunay เมื่อตรวจสอบเงื่อนไข Delaunay สำหรับคู่ของสามเหลี่ยมใกล้เคียง เราสามารถใช้คำจำกัดความได้โดยตรง แต่บางครั้งก็ใช้วิธีอื่นตามเงื่อนไขที่ระบุไว้ข้างต้น

ภายใต้เงื่อนไขเหล่านี้ ลักษณะรวมของรูปสามเหลี่ยมทั้งหมดจะปรากฏขึ้น (ผลรวมของมุมต่ำสุดหรือผลรวมของรัศมี) โดยการปรับให้เหมาะสมเพื่อให้ได้รูปสามเหลี่ยม Delaunay

ดังที่กล่าวไว้ข้างต้น การดำเนินการที่สำคัญที่สุดอย่างหนึ่งเมื่อสร้างรูปสามเหลี่ยมคือการตรวจสอบเงื่อนไข Delaunay สำหรับคู่ของรูปสามเหลี่ยมที่กำหนด ตามคำจำกัดความของสามเหลี่ยม Delaunay และเงื่อนไขที่สอดคล้องกัน ในทางปฏิบัติมักจะใช้วิธีการตรวจสอบหลายวิธี:

- การตรวจสอบผ่านสมการของวงกลมที่มีเส้นรอบวง

– ตรวจสอบด้วยวงกลมเส้นรอบวงที่คำนวณไว้ล่วงหน้า

– ตรวจสอบผลรวมของมุมตรงข้าม

เป็นการตรวจสอบผลรวมของมุมตรงข้ามที่แก้ไขแล้ว

หลายระบบทดสอบด้วยวงกลมที่คำนวณไว้ล่วงหน้า แนวคิดหลักของอัลกอริทึมสำหรับการตรวจสอบผ่านวงกลมที่คำนวณล่วงหน้าคือการคำนวณล่วงหน้าสำหรับสามเหลี่ยมที่สร้างขึ้นแต่ละอันซึ่งเป็นศูนย์กลางและรัศมีของวงกลมที่ล้อมรอบรอบ ๆ หลังจากนั้นการตรวจสอบเงื่อนไข Delaunay จะลดลงเป็นการคำนวณระยะทาง ไปที่ศูนย์กลางของวงกลมนี้และเปรียบเทียบผลลัพธ์กับรัศมี ศูนย์กลางและรัศมี r ของวงกลมที่อธิบายรอบๆ หาได้เป็น , , , r 2 = (b 2 + c 2 - 4ad)/4a 2 โดยที่ค่า เอบีซีดีกำหนดโดยสูตร (5.3)

(5.3)

อีกวิธีในการเขียนสมการสำหรับวงกลมนี้คือ:

(5.5.)

(5.6)

จากนั้นเงื่อนไข Delaunay สำหรับ จะสำเร็จก็ต่อเมื่อสำหรับจุดสามเหลี่ยมอื่นๆ จะเป็น:

(x 0 - x C) 2 + (y 0 - y C) 2 ≥ r 2 . (5.7)

ปัจจุบันมีอัลกอริทึมมากมายสำหรับการสร้างรูปสามเหลี่ยม Delaunay อัลกอริทึมที่รู้จักกันดีจำนวนมากใช้คำจำกัดความของ Delaunay triangulation เป็นคุณลักษณะรองของการวิเคราะห์สามเหลี่ยม ดังนั้นอัลกอริทึมดังกล่าวจึงมีจุดอ่อนดังต่อไปนี้:

- อัลกอริทึมใช้ฟังก์ชันตรีโกณมิติที่คำนวณอย่างต่อเนื่องซึ่งทำให้กระบวนการช้าลงอย่างมาก

- เมื่อศึกษาความสัมพันธ์ระหว่างจุดและส่วนฐานจะมีมุมเล็ก ๆ เกิดขึ้นและเมื่อใช้ฟังก์ชันตรีโกณมิติจะมีอันตรายอย่างต่อเนื่องจากการหายไปของลำดับและการหารด้วย 0 เนื่องจากความแม่นยำที่ จำกัด ของการแสดงข้อมูลในคอมพิวเตอร์ สถานการณ์นี้ต้องการการประมวลผลเพิ่มเติมอย่างต่อเนื่อง

ผลิตภัณฑ์ซอฟต์แวร์ที่มีชื่อเสียงที่สุดสร้างรูปสามเหลี่ยม Delaunay โดยใช้ทฤษฎีบทลูกบอลเปล่าเป็นหลักการหลักในการสร้างรูปสามเหลี่ยม อัลกอริทึมมีลักษณะดังนี้:

– จุดทั้งชุดแบ่งเป็นรูปสามเหลี่ยม เช่น มีการสร้างการรวมกันของสามจุด

– สำหรับแต่ละชุดจะพบวงกลมที่ล้อมรอบและพิกัดของจุดศูนย์กลาง

- หากไม่มีจุดเดียวจากจุดที่เหลือในวงกลมของชุดค่าผสมปัจจุบัน ชุดค่าผสมนี้จะเป็นรูปสามเหลี่ยม - เป็นส่วนหนึ่งของรูปสามเหลี่ยม Delaunay

ข้อดีของอัลกอริทึมนี้รวมถึง:

– ไม่มีการใช้ฟังก์ชันตรีโกณมิติ ซึ่งไม่ทำให้กระบวนการก่อสร้างช้าลง

– การสร้างสามเหลี่ยม Delaunay โดยตรง โดยไม่มีการสร้างเบื้องต้นใดๆ

– ความเรียบง่ายของการคำนวณและการแปลงทั้งหมด

- เป็นผลให้ตาข่ายรูปสามเหลี่ยมแสดงด้วยรูปสามเหลี่ยมหลายรูป ไม่ใช่เส้นแต่ละเส้น

รูปสามเหลี่ยมที่สร้างขึ้นด้วยวิธีนี้เป็นพื้นฐานทางเรขาคณิตสำหรับการสร้างเส้นแยก

อัลกอริทึมสำหรับการสร้างรูปสามเหลี่ยม Delaunay สามารถแบ่งออกเป็นหลายกลุ่มที่แตกต่างกันในโครงสร้างของข้อมูลอินพุตที่ใช้ จำนวนการดำเนินการคำนวณ สมมติฐานเริ่มต้น ฯลฯ ลองพิจารณาบางส่วน

อัลกอริทึมการผสานเกี่ยวข้องกับการแบ่งชุดของจุดเริ่มต้นออกเป็นส่วนย่อย สร้างรูปสามเหลี่ยมบนแต่ละจุด แล้วรวมเข้าด้วยกันเป็นเครือข่ายเดียว สาระสำคัญของหนึ่งในอัลกอริทึมเหล่านี้มีดังนี้

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

การรวมสามเหลี่ยมเหล่านี้เป็นเครือข่ายเดียวทำได้โดยการสร้างเส้นฐานสองเส้น (ป 0 ป 1 และ ป 2 ป 3, ข้าว. 5.7.a) วาดวงกลมที่มีรัศมีแปรผันโดยมีศูนย์กลางอยู่ที่ค่ามัธยฐานที่ตั้งฉากกับเส้นฐาน (รูปที่ 5.7, b) ค้นหาโหนดที่ตกลงมาบนวงกลม (จุด ก, ข้าว. 5.7. c) และการสร้างรูปสามเหลี่ยมใหม่ (ป0ป1ก).ในกรณีนี้ อาจจำเป็นต้องลบรูปสามเหลี่ยมที่มีอยู่แล้ว (เช่น P0AB).

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

อัลกอริธึมแบบสองรอบให้การสร้างรูปสามเหลี่ยมบางส่วนก่อน โดยไม่สนใจเงื่อนไข Delaunay แล้วจึงสร้างใหม่ตามเงื่อนไขเหล่านี้ ตัวอย่างของการประยุกต์ใช้อัลกอริทึมแสดงในรูปที่ 5.8.

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

งานสร้างแบบจำลองพื้นผิวโดยคำนึงถึงเบรกไลน์เรียกว่า Delaunay triangulation ที่มีข้อจำกัด หากเงื่อนไขของ Delaunay เป็นที่พอใจสำหรับคู่ของสามเหลี่ยมที่อยู่ติดกันซึ่งไม่ถูกคั่นด้วยเบรกไลน์ นักวิจัยเชื่อว่ารูปสามเหลี่ยมดังกล่าวสร้างขึ้นอย่างมีประสิทธิภาพมากที่สุดโดยใช้อัลกอริทึมแบบวนซ้ำ

ชิ้นส่วนของสามเหลี่ยม Delaunay ที่มีองค์ประกอบเพิ่มเติมรวมอยู่ในนั้นแสดงในรูปที่ 5.9 โดยที่โหนด ขอบ พื้นผิว และเส้นแบ่งจะแสดงทางด้านขวา และเส้นแบ่งของภูมิประเทศ (แนวชายฝั่ง ขอบหุบเขา ฯลฯ) และจุดที่มีเครื่องหมายที่ทราบจะแสดงทางด้านซ้าย

อัลกอริทึมสำหรับการสร้างรูปสามเหลี่ยม Delaunay ถูกนำมาใช้กับการแสดงพิกัดของโหนดจริงหรือจำนวนเต็ม ซึ่งสามารถเพิ่มความเร็วและความแม่นยำของการประมวลผลได้อย่างมีนัยสำคัญ แต่ก่อให้เกิดปัญหาในการค้นหาและกำจัดโหนดที่ตรงกัน

โมเดล TIN แก้ไขได้ง่ายโดยการย้ายโหนด แทรกโหนดใหม่ ลบโหนดที่มีอยู่ เปลี่ยนตำแหน่งของขอบอย่างน้อยหนึ่งขอบ สร้างเบรกไลน์ใหม่ ฯลฯ การเปลี่ยนแปลงดังกล่าวจะส่งผลต่อกลุ่มสามเหลี่ยมเล็กๆ ที่อยู่ติดกันเสมอ ไม่จำเป็นต้องสร้างใหม่ทั้งหมด เครือข่าย และดำเนินการในโหมดออนไลน์โดยชี้เคอร์เซอร์ไปที่องค์ประกอบที่เกี่ยวข้อง .

เกี่ยวกับความแม่นยำ:

เมื่อวางคานบนองค์ประกอบนูนที่มีลักษณะพิเศษ (เช่น สันปันน้ำและทัลแวก) เราจะไม่สนใจองค์ประกอบที่เล็กกว่าระหว่างนั้น เมื่อสร้างเส้นชั้นความสูง1 ตามขอบของสามเหลี่ยมดังกล่าว จะเกิดข้อผิดพลาดขึ้น ซึ่งขึ้นอยู่กับขนาดของความไม่สม่ำเสมอของการผ่อนปรนและมุมเอียงของภูมิประเทศ ตัวอย่างเช่น ข้อผิดพลาดโดยเฉลี่ยของการสำรวจการบรรเทาไม่ควรเกิน 1/3 ของส่วนการบรรเทาที่มุมเอียงของพื้นผิวตั้งแต่ 2 ถึง 10 องศา สามารถคำนวณได้ว่าด้วยส่วนตัดขวาง 0.5 ม. ค่าจำกัดของความไม่สม่ำเสมอที่ไม่ได้รับ (นั่นคือ ความเบี่ยงเบนของพื้นผิวโลกจากเส้นตรงที่ผ่านซี่ที่อยู่ใกล้เคียง) ไม่ควรเกิน (0.5/3)*cos10 °=0.16 ม.

เพื่อความแม่นยำในการกำหนดปริมาตรของดินที่เคลื่อนย้าย พื้นที่ที่ถูกครอบครองโดยรายละเอียดการผ่อนปรนที่ไม่ได้นำมาพิจารณาก็มีความสำคัญเช่นกัน สมมติว่าในตารางขนาด 20x20 ม. ระหว่างซี่ไม้สองคู่มีกระพุ้งทรงกระบอกที่มีความสูงสูงสุด 0.15 ม. คำนวณได้ง่ายว่าการเพิกเฉยเมื่อแสดงพื้นผิวนี้ด้วยสามเหลี่ยมเพียงสองรูปจะทำให้เกิดข้อผิดพลาดประมาณ 40 ลบ.ม. ไม่มากนัก แต่สำหรับพื้นที่ 1 เฮกตาร์ซึ่งตั้งอยู่บนเนินเขาหรือส่วนบน (มักจะนูน) ของความลาดชัน คุณจะได้ดินส่วนเกิน 40 * 25 = 1,000 ลบ.ม. หากมีการใช้รั้วบ่อยขึ้นสองเท่า (นั่นคือทุกๆ 10 ม.) ข้อผิดพลาดจะลดลงสี่เท่าและลดลงเป็น 250 ลบ.ม. ต่อเฮกตาร์ ปัจจัยนี้สามารถนำมาพิจารณาล่วงหน้าได้ เนื่องจากรูปแบบที่เป็นบวกของการนูนแบบเรียบมักจะมีรูปร่างนูน และรูปแบบที่เป็นลบจะมีลักษณะเว้า หากพื้นที่ที่จะสำรวจมีข้อมูลโดยประมาณเกี่ยวกับการผ่อนปรน รัศมีความโค้งของพื้นผิวและความหนาแน่นที่ต้องการของรั้วสามารถคำนวณได้ง่ายจากค่าของเส้นชั้นความสูงหรือระดับความสูงแต่ละส่วน

ในการหาปริมาณคุณภาพของรูปสามเหลี่ยมที่สร้างขึ้น เราได้กำหนดเกณฑ์สองประเภท ได้แก่ ทอพอโลยีและเรขาคณิต

เกณฑ์ทอพอโลยีขึ้นอยู่กับเพื่อนบ้านที่ใกล้ที่สุดของจุดจากชุด ตามหลักการแล้ว จุดหนึ่งมีเพื่อนบ้าน 6 คนสำหรับภูมิภาค 2 มิติ และเพื่อนบ้าน 12 คนสำหรับภูมิภาค 3 มิติ เราได้รับการประมาณค่าทอพอโลยีโดยใช้สูตร (1) โดยที่จำนวนจุดทั้งหมดในภูมิภาคคือระดับหรือจำนวนของจุดที่อยู่ใกล้เคียงซึ่งเชื่อมต่อกับจุดภายใน

เกณฑ์ทางเรขาคณิตขึ้นอยู่กับความแตกต่างระหว่างวงกลมที่จารึกไว้และวงกลมที่ล้อมรอบรอบองค์ประกอบสามเหลี่ยมที่คำนวณได้ เราได้รับค่าประมาณทางเรขาคณิตโดยใช้สูตร (2) โดยที่จำนวนสามเหลี่ยมคือรัศมีของวงกลมที่จารึกไว้คือรัศมีของวงกลมที่ล้อมรอบ

อัลกอริทึมสำหรับการสร้างรูปสามเหลี่ยม

มีอัลกอริธึมจำนวนมากสำหรับการสร้างรูปสามเหลี่ยม พวกเขาแตกต่างกันในด้านความลำบาก ความซับซ้อนของการใช้งานบนคอมพิวเตอร์ และวิธีการก่อสร้าง คุณสามารถเรียนรู้เพิ่มเติมเกี่ยวกับอัลกอริทึมได้ในหนังสือของ A.V. สวอร์ตโซวา. ลองพิจารณาอัลกอริทึมบางอย่าง

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

ขั้นตอนที่ 1.รายการของส่วนของเส้นที่เป็นไปได้ทั้งหมดที่เชื่อมต่อคู่ของจุดต้นทางจะถูกสร้างขึ้นและจัดเรียงตามความยาวของส่วน

ขั้นตอนที่ 2เริ่มจากส่วนที่สั้นที่สุด ส่วนต่างๆ จะถูกแทรกตามลำดับในรูปสามเหลี่ยม หากส่วนไม่ตัดกับส่วนอื่นๆ ที่แทรกไว้ก่อนหน้านี้ จะถูกแทรก มิฉะนั้นจะถูกละทิ้ง

โปรดทราบว่าหากส่วนที่เป็นไปได้ทั้งหมดมีความยาวต่างกัน ผลลัพธ์ของอัลกอริทึมนี้จะไม่คลุมเครือ มิฉะนั้นจะขึ้นอยู่กับลำดับการแทรกของกลุ่มที่มีความยาวเท่ากัน

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

ขั้นตอนที่ 1.ในสามจุดเริ่มต้นแรก เราสร้างสามเหลี่ยมหนึ่งรูป

ขั้นตอนที่ 2ในลูปสำหรับจุดอื่นๆ ทั้งหมด ให้ทำตามขั้นตอนที่ 3-5

ขั้นตอนที่ 3จุดต่อไปจะถูกเพิ่มลงในโครงสร้างรูปสามเหลี่ยมที่สร้างขึ้นแล้วดังนี้ ประการแรก ประเด็นถูกแปลเป็นภาษาท้องถิ่น เช่น มีรูปสามเหลี่ยม (สร้างก่อนหน้านี้) ซึ่งจุดถัดไปอยู่ หรือหากจุดนั้นไม่อยู่ในรูปสามเหลี่ยม แสดงว่ามีรูปสามเหลี่ยมอยู่บนเส้นขอบของรูปสามเหลี่ยมที่ใกล้กับจุดถัดไปมากที่สุด

ขั้นตอนที่ 4หากจุดหนึ่งกระทบกับโหนดรูปสามเหลี่ยมที่แทรกไว้ก่อนหน้านี้ โดยปกติแล้วจุดดังกล่าวจะถูกละทิ้ง มิฉะนั้น จุดนั้นจะถูกแทรกเข้าไปในรูปสามเหลี่ยมเป็นโหนดใหม่ ยิ่งไปกว่านั้น หากจุดนั้นชนกับขอบบางส่วน มันจะแบ่งออกเป็นสองอันใหม่ และสามเหลี่ยมทั้งสองที่อยู่ติดกับขอบจะถูกแบ่งออกเป็นสองอันที่เล็กกว่าด้วย หากจุดอยู่ภายในสามเหลี่ยมใด ๆ อย่างเคร่งครัด จะแบ่งออกเป็นสามอันใหม่ ถ้าจุดนั้นอยู่นอกรูปสามเหลี่ยม แสดงว่ามีการสร้างรูปสามเหลี่ยมอย่างน้อยหนึ่งรูป

ขั้นตอนที่ 5มีการตรวจสอบท้องถิ่นของสามเหลี่ยมที่ได้รับใหม่เพื่อให้สอดคล้องกับเงื่อนไข Delaunay และดำเนินการจัดเรียงใหม่ที่จำเป็น

เมื่อสร้างรูปสามเหลี่ยมใหม่ เป็นไปได้สองสถานการณ์เมื่อจุดที่เพิ่มเข้ามานั้นอยู่ภายในรูปสามเหลี่ยมหรือด้านนอก ในกรณีแรก รูปสามเหลี่ยมใหม่จะถูกสร้างขึ้นและจำนวนของการดำเนินการที่ดำเนินการโดยอัลกอริทึมได้รับการแก้ไข ในอันที่สอง จำเป็นต้องสร้างรูปสามเหลี่ยมเพิ่มเติมนอกรูปสามเหลี่ยมปัจจุบัน และจำนวนของสามเหลี่ยมนั้นอาจเท่ากันในกรณีที่เลวร้ายที่สุด? 3. อย่างไรก็ตาม ทุกขั้นตอนของอัลกอริทึมจะไม่เพิ่มรูปสามเหลี่ยมเกินกว่านั้น โดยที่จำนวนจุดเริ่มต้นทั้งหมดคือจำนวนทั้งหมด ดังนั้นในทั้งสองกรณี เวลาทั้งหมดที่ใช้ในการสร้างรูปสามเหลี่ยมคือ

อัลกอริทึมลูกโซ่หนึ่งในอัลกอริธึมการสร้างรูปสามเหลี่ยมที่มีประสิทธิภาพชุดแรกนั้นขึ้นอยู่กับขั้นตอนการทำให้เป็นมาตรฐานของกราฟระนาบและรูปสามเหลี่ยมรูปหลายเหลี่ยมแบบโมโนโทน ความซับซ้อนของอัลกอริทึมนี้คือ จำนวนเซ็กเมนต์เริ่มต้นอยู่ที่ไหน พิจารณาอัลกอริทึมทีละขั้นตอน:

ขั้นตอนที่ 1.จากชุดของส่วนโครงสร้างเริ่มต้น เราสร้างกราฟระนาบที่เชื่อมต่อกัน (รูปที่ 4, a)

ขั้นตอนที่ 2กราฟถูกทำให้เป็นมาตรฐาน เช่น มีการเพิ่มขอบใหม่ที่ไม่ตัดกัน ดังนั้นจุดยอดแต่ละจุดของกราฟจะอยู่ติดกับจุดยอดด้านบนและด้านล่างอย่างน้อยหนึ่งจุด การทำให้เป็นมาตรฐานจะทำในสองรอบโดยใช้การกวาดแนวราบในแนวตั้ง ในการผ่านครั้งแรกจากล่างขึ้นบน เราจะพบจุดยอดทั้งหมดตามลำดับที่ไม่มีขอบนำหน้า ตัวอย่างเช่น บน (รูปที่ 4, b) นี่คือจุดยอด B การวาดเส้นแนวนอน เราพบว่าขอบที่ใกล้ที่สุดของกราฟ AD และ EF ตัดกันทางด้านซ้ายและขวา จากนั้นเราจะพบจุดยอดที่ต่ำที่สุดในรูปสี่เหลี่ยม DEHG และวาดขอบจาก B เข้าไป ในทำนองเดียวกันการผ่านครั้งที่สองจะดำเนินการจากบนลงล่าง (รูปที่ 4, c) จากขั้นตอนนี้ พื้นที่แต่ละส่วนของกราฟระนาบจะกลายเป็นรูปหลายเหลี่ยมสีเดียว

ขั้นตอนที่ 3พื้นที่กราฟแต่ละส่วนต้องแบ่งเป็นรูปสามเหลี่ยม ในการทำเช่นนี้คุณสามารถใช้อัลกอริทึมของการรวมสองรูปสามเหลี่ยมแบบไม่นูน (รูปที่ 4, d)

รูปที่ 4 รูปแบบการทำงานของอัลกอริทึมลูกโซ่สามเหลี่ยม: a) - ส่วนเริ่มต้น; b - ทางจากล่างขึ้นบนของการทำให้เป็นมาตรฐานของกราฟ c) - ทางจากบนลงล่าง; d) - รูปสามเหลี่ยมของรูปหลายเหลี่ยมสีเดียว

ในการใช้อัลกอริทึมลูกโซ่ วิธีที่ดีที่สุดคือใช้โครงสร้างข้อมูลซึ่งแสดงขอบอย่างชัดเจน เช่น "ขอบคู่" หรือ "นอต ขอบ และสามเหลี่ยม"

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

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