PSLG คืออะไร?
Planar Straight-Line Graph (PSLG) = Embedding ของ Planar Graph ใน Plane ที่ Edges เป็น Straight Line Segments
Fáry's Theorem (1948): ทุก Planar Graph มี Embedding แบบนี้
ใน Computational Geometry เรียกว่า Planar Subdivisions (สมมติ Polygonal) โดยไม่มี Vertices Degree 1 → PSLG กำหนด Subdivision ของ Plane เป็น Polygonal Regions และ Vice Versa
Special Cases
- Triangulations: Polygon Triangulation, Point Set Triangulation
- Point Set Triangulations = Maximal PSLGs (เพิ่ม Straight Edges ไปไม่ได้อีกแล้วโดยไม่เสีย Planarity)
- Delaunay Triangulations: Metric + Topological Properties สำคัญทั้งคู่
Representations (3 โครงสร้างข้อมูลหลัก)
| Data Structure | ลักษณะ | ข้อดี/ข้อเสีย |
|---|---|---|
| Winged-Edge | เก่าที่สุด Edge References ไม่เก็บ Direction Directions รอบ Face ไม่ Consistent | Manipulate ซับซ้อน ต้อง Case Distinctions มาก |
| Halfedge (DCEL) | เก็บทั้ง 2 Orientations ของ Edge + Link อย่างถูกต้อง | Operations เรียบง่าย Storage Scheme ชัดเจน |
| Quadedge | เก็บ Planar Subdivision + Dual พร้อมกัน Records = Edge Records (4 ต่อ Edge) | รองรับ Non-orientable, Simplified Form ใช้กับ PSLG ได้ดี |
สรุป
PSLG = Foundation ของ Computational Geometry เลือก Representation ตาม Use Case: Halfedge = มาตรฐานทั่วไป, Quadedge = ต้องการ Dual, Winged-Edge = Legacy
