แผนภาพโวโรนอย

จากวิกิพีเดีย สารานุกรมเสรี

แผนภาพโวโรนอย (อังกฤษ: voronoi diagram) เป็นหนึ่งในโครงสร้างที่สำคัญที่ใช้ในการคำนวณเชิงเรขาคณิต โดยแผนภาพนี้ใช้ทำการบันทึกข้อมูลว่าอะไรอยู่ใกล้กับอะไร

คำจำกัดความ[แก้]

ให้ P = \{p_1, p_2, ..., p_n\} เป็นเซตของจุดที่สนใจ (sites) n จุด ในระนาบ แผนภาพโวโรนอยของ P คือ การแบ่งส่วนระนาบออกเป็นเซลล์ V(pi) จำนวน n เซลล์ (1 เซลล์ ต่อ 1 site) จุด q คือ จุดที่อยู่ในเซลล์ ซึ่งมีความสัมพันธ์กับ site pi โดยที่ p_i \in P กล่าวคือ V(p_i) = \{ q : |p_{i}q| < |p_{j}q| , j \neq i \}

สมบัติของแผนภาพโวโรนอย[แก้]

250px 250px

  • เส้นเชื่อมโวโรนอย (voronoi edge) : แต่ละจุดบนเส้นเชื่อมของ แผนภาพโวโรนอย คือ จุดที่มีระยะห่างระหว่างไซท์สองไซท์ (pi, pj) ที่อยู่ติดกันเป็นระยะเท่ากัน และ ณ จุดนั้นเป็นจุดศูนย์กลางของวงกลมซึ่งมี pi และ pj สัมผัสอยู่ที่เส้นวง และไม่มีไซท์อื่นๆ อยู่ภายในวงนั้นๆ
  • voronoi vertex : จุดที่เกิดจากการที่ เซลล์สามเซลล์มาบรรจบกัน ซึ่งจาก voronoi vertex นั้น จะมีระยะห่างจากไซท์ทั้งสาม เป็นระยะเท่าๆ กัน และ ณ จุดนั้น เป็นจุดศูนย์กลางของวงกลมซึ่งเส้น
  • รอบวงลากผ่านไซท์เหล่านั้นพอดี และไม่มีไซท์อื่นๆ อยู่ภายในวงนั้นๆ
  • ดีกรี (degree) : หากเราสร้างแผนภาพให้แต่ละ vertex ไม่มีไซ์ในเส้นวง เป็น 4 ไซท์ จะได้ว่า ทุกจุดยอด มีดีกรีเท่ากับ 3
  • ขนาด (size) : ให้ n คือ จำนวน sites ทั้งหมด และ แผนภาพโวโรนอยเป็นพลาน่ากราฟที่มีหน้า n หน้าจะได้ว่า จำนวน voronoi vertex ทั้งหมดมีจำนวน 2n – 5 จุดยอด และ จำนวนเส้นเชื่อมโวโรนอยทั้งหมด มีจำนวน 3n – 6 เส้นเชื่อม

ตัวอย่างของแผนภาพโวโรนอย[แก้]

  • 1 site

22px

  • 2 site

100px

  • sites ที่อยู่ในแนวเดียวกัน จัดรูปเป็นชุดของเส้นคู่ขนาน

200px

อ้างอิง[แก้]

  1. http://nms.csail.mit.edu/~aklmiu/6.838/
  2. http://www.skynet.ie/~sos/mapviewer/docs/Voronoi_Diagram_Notes_1.pdf