Figure 1: A triangulation (top) and

Figure 1: A triangulation (top) and its corresponding representations with quad-edge and triangular data structures. Each quad-edge and each triangle contains six pointers.
It is difficult to ascertain with certainty why the triangular data structure is superior in time as well as space, but one can make educated inferences. When a program makes structural changes to a triangulation, the amount of time used depends in part on the number of pointers that have to be read and written. This amount is smaller for the triangular data structure; more of the connectivity information is implicit in each triangle. Caching is improved by the fact that fewer structures are accessed. (For large triangulations, any two adjoining quad-edges or triangles are unlikely to lie in the same cache line.)

Because the triangle-based divide-and-conquer algorithm proved to be fastest, it is worth exploring in some depth. At first glance, the algorithm and data structure seem incompatible. The divide-and-conquer algorithm recursively halves the input vertices until they are partitioned into subsets of two or three vertices each. Each subset is easily triangulated (yielding an edge, two collinear edges, or a triangle), and the triangulations are merged together to form larger ones. If one uses a degenerate triangle to represent an isolated edge, the resulting code is clumsy because of the need to handle special cases. One might partition the input into subsets of three to five vertices, but this does not help if the points in a subset are collinear.

To preserve the elegance of Guibas and Stolfi's presentation of the divide-and-conquer algorithm, each triangulation is surrounded with a layer of ``ghost'' triangles, one triangle per convex hull edge. The ghost triangles are connected to each other in a ring about a ``vertex at infinity'' (really just a null pointer). A single edge is represented by two ghost triangles, as illustrated in Figure 2.

ผลลัพธ์ (ไทย) 1:

รูปที่ 1: ระบบสามสกุล (บน) และนำเสนอที่สอดคล้องกับโครงสร้างข้อมูล ขอบรูปสี่เหลี่ยม และสามเหลี่ยม แต่ละขอบรูปสี่เหลี่ยมและสามเหลี่ยมแต่ละประกอบด้วย 6 ตัวชี้เป็นการยากที่จะตรวจ ด้วยแน่นอนทำไมโครงสร้างข้อมูลที่สามเป็นห้องในเวลาและพื้นที่ แต่หนึ่งสามารถทำให้ศึกษา inferences เมื่อโปรแกรมทำการเปลี่ยนแปลงโครงสร้างเป็นระบบสามสกุลเงิน ระยะเวลาที่ใช้ขึ้นอยู่ส่วนหนึ่งกับจำนวนของตัวชี้ที่จะสามารถอ่าน และเขียน ยอดเงินนี้มีขนาดเล็กโครงสร้างข้อมูลที่สาม เพิ่มเติมข้อมูลการเชื่อมต่อคือความนัยในสามเหลี่ยมแต่ละ แคปรับความจริงที่ว่า มีการเข้าถึงโครงสร้างน้อย (สำหรับขนาดใหญ่ triangulations ใด ๆ สองติดขอบรูปสี่เหลี่ยมหรือสามเหลี่ยมได้น่าจะอยู่ในบรรทัดเดียวกันแคช)เนื่องจากการใช้รูปสามเหลี่ยมแบ่ง และพิชิตอัลกอริทึมพิสูจน์ให้เร็วที่สุด มันเที่ยวลึกบางอย่าง อย่างรวดเร็วก่อน โครงสร้างข้อมูลและอัลกอริทึมดูเหมือนเข้ากันไม่ได้ Recursively อัลกอริทึมการแบ่ง และพิชิต halves จุดยอดนำเข้าจนกว่าพวกเขาจะแบ่งออกเป็นชุดย่อยของสอง หรือสามจุดยอดแต่ละ ได้รับแต่ละชุดย่อย (ผลผลิตขอบ ขอบสอง collinear หรือรูปสามเหลี่ยม), และ triangulations ที่มีผสานกันเพื่อคนใหญ่ ถ้าใช้สามเหลี่ยม degenerate ถึงขอบแยก รหัสผลลัพธ์ได้ป้ำ ๆ เนื่องจากจำเป็นในการจัดการกรณี หนึ่งอาจแบ่งพาร์ติชันข้อมูลป้อนเข้าเป็นชุดย่อยของจุดยอดสามถึงห้า แต่นี้ช่วยถ้าจุดในเซตย่อย collinearเพื่อรักษาความงดงามของงานนำเสนอของ Stolfi และ Guibas ของอัลกอริทึมการแบ่ง และพิชิต สามแต่ละถูกล้อมรอบ ด้วยชั้นของ ''ผี '' สามเหลี่ยม สามเหลี่ยมหนึ่งต่อขอบนูนฮัลล์ สามเหลี่ยมผีจะเชื่อมต่อถึงกันในวงแหวนเกี่ยวกับ ''จุดยอดที่อินฟินิตี้ '' (แค่ตัวชี้ null) ด้วย ขอบเดียวจะแทน ด้วยสามเหลี่ยมผีสอง ดังที่แสดงในรูปที่ 2

ผลลัพธ์ (ไทย) 2:

รูปที่ 1: สมการ (บน) และการแสดงที่สอดคล้องกับรูปสี่เหลี่ยมที่ทันสมัยและโครงสร้างข้อมูลเป็นรูปสามเหลี่ยม แต่ละรูปสี่เหลี่ยมที่ทันสมัยและแต่ละรูปสามเหลี่ยมมีหกตัวชี้.
มันเป็นเรื่องยากที่จะตรวจสอบด้วยความมั่นใจว่าทำไมโครงสร้างข้อมูลเป็นรูปสามเหลี่ยมที่เหนือกว่าในเวลาเช่นเดียวกับพื้นที่ แต่อย่างหนึ่งที่สามารถทำให้การหาข้อสรุปการศึกษา เมื่อโปรแกรมทำให้เกิดการเปลี่ยนแปลงโครงสร้างสม, ระยะเวลาที่ใช้ขึ้นอยู่ในส่วนที่เกี่ยวกับจำนวนของตัวชี้ที่จะต้องมีการอ่านและเขียน เงินจำนวนนี้มีขนาดเล็กสำหรับโครงสร้างข้อมูลสามเหลี่ยม; เพิ่มเติมข้อมูลการเชื่อมต่อเป็นนัยในแต่ละรูปสามเหลี่ยม แคชจะดีขึ้นโดยความจริงที่ว่าโครงสร้างน้อยมีการเข้าถึง (สำหรับ triangulations ขนาดใหญ่สองขอบรูปสี่เหลี่ยมหรือสามเหลี่ยมที่อยู่ติดกันไม่น่าจะอยู่ในสายเดียวกันแคช.) เพราะขั้นตอนวิธีการหารและพิชิตสามเหลี่ยมตามพิสูจน์แล้วว่าเป็นที่เร็วที่สุดมันเป็นมูลค่าการสำรวจในเชิงลึกบางส่วน ได้อย่างรวดเร็วก่อนขั้นตอนวิธีและโครงสร้างข้อมูลที่ดูเหมือนเข้ากันไม่ได้ ขั้นตอนวิธีการหารและพิชิตซ้ำครึ่งจุดป้อนข้อมูลจนกว่าพวกเขาจะแบ่งออกเป็นส่วนย่อยของสองหรือสามจุดในแต่ละ ส่วนย่อยแต่ละอย่างง่ายดายดัก (ผลผลิตขอบสองขอบ collinear หรือสามเหลี่ยม) และ triangulations จะรวมกันในรูปแบบที่ใหญ่กว่า หากหนึ่งใช้รูปสามเหลี่ยมเลวจะเป็นตัวแทนของขอบที่แยกรหัสที่เกิดเป็นเงอะงะเพราะความจำเป็นที่จะจัดการกับกรณีพิเศษ หนึ่งอาจแบ่งพาร์ติชันใส่ลงในส่วนย่อยของ 3-5 จุด แต่นี้ไม่ได้ช่วยถ้าคะแนนในเซตมี collinear. เพื่อรักษาความสง่างามของ Guibas และการนำเสนอ Stolfi ของขั้นตอนวิธีการหารและพิชิต, สมการแต่ละรายล้อมไปด้วย ชั้นของ `` ผี '' สามเหลี่ยมหนึ่งรูปสามเหลี่ยมต่อเรือขอบนูน สามเหลี่ยมผีมีการเชื่อมต่อกับแต่ละอื่น ๆ ในเวทีเกี่ยวกับ `` จุดสุดยอดที่อินฟินิตี้ '' (จริงๆเพียงแค่ชี้โมฆะ) ขอบเดียวเป็นตัวแทนจากรูปสามเหลี่ยมสองรูปผีดังแสดงในรูปที่ 2

ผลลัพธ์ (ไทย) 3:

รูปที่ 1 : สามเส้า ( ด้านบน ) และตัวแทนที่เกี่ยวข้องกับขอบรูปสี่เหลี่ยมและโครงสร้างข้อมูลแบบสามเหลี่ยม แต่ละคนและแต่ละรูปสี่เหลี่ยมขอบสามเหลี่ยมมีหกตัวชี้ .
มันเป็นเรื่องยากที่จะวินิจฉัย แน่นอน ทำไมโครงสร้างข้อมูลสามเหลี่ยมเหนือในเวลาเช่นเดียวกับพื้นที่ แต่หนึ่งสามารถทำให้การศึกษาอ้างอิง . เมื่อโปรแกรมที่ทำให้การเปลี่ยนแปลงโครงสร้างเป็นสามเหลี่ยม ,ปริมาณของเวลาที่ใช้ขึ้นอยู่กับในส่วนที่เกี่ยวกับจำนวนของตัวชี้ที่ต้องอ่านและเขียน จํานวนนี้มีขนาดเล็กสำหรับโครงสร้างข้อมูลแบบสามเหลี่ยม เพิ่มเติมข้อมูลการเชื่อมต่อระบบ ในแต่ละสามเหลี่ยม แคชที่ดีขึ้น โดยความจริงที่น้อยกว่าโครงสร้างจะเข้าถึงได้ ( triangulations ขนาดใหญ่สองที่อยู่ติดกันหรือรูปสี่เหลี่ยมขอบสามเหลี่ยมไม่น่าจะโกหกในบรรทัดแคชเหมือนกัน )

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

เพื่อรักษาความสง่างามของ guibas stolfi และการนำเสนอของการแบ่งและพิชิตเส้นทางแต่ละรูปสามเหลี่ยมล้อมรอบด้วยชั้นของ ' ' ผี ' ' สามเหลี่ยมหนึ่งในสามเหลี่ยมนูนฮัลล์ ต่อขอบ ผีสามเหลี่ยมที่เชื่อมต่อกับแต่ละอื่น ๆในเวทีเรื่อง ' ' จุดสุดยอดที่ไม่มีที่สิ้นสุด " ( จริงๆแค่ตัวชี้ null ) ขอบเดียวจะแสดงโดยสองผีสามเหลี่ยม ตามที่แสดงในรูปที่ 2