การสร้างแผนภาพโวโรนอยด้วยอัลกอริทึมของ Fortune

การสร้างแผนภาพโวโรนอย

• แผนภาพโวโรนอยคืออะไร?

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

• อัลกอริทึมของ Fortune

  • อัลกอริทึมของ Fortune เป็นวิธีสร้างแผนภาพโดยใช้เส้นที่ 'กวาด' จากซ้ายไปขวาบนระนาบ
  • เมื่อเส้นกวาดเจอ site จะเกิด 'bubble' (ส่วนโค้งพาราโบลา) รอบจุดนั้น และ bubble จะใหญ่ขึ้นเมื่อเส้นกวาดเคลื่อนห่างออกไป
  • เมื่อส่วนโค้งของสอง site ชนกัน จุดชนกันนั้นจะกลายเป็นขอบเขตของเซลล์
  • ขอบเขตของ bubble ที่ยังทำงานอยู่ทั้งหมดเรียกว่า 'beachline'

• คำอธิบายคำศัพท์

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

• เส้นสัมผัสพาราโบลา

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

• กลับมาที่ beachline

  • beachline คือ 'ขอบเขต' ของส่วนโค้งทั้งหมด ณ ตำแหน่งหนึ่งของเส้นกวาด
  • ส่วนโค้งแต่ละส่วนสามารถแทนได้ด้วยจุดโฟกัสของ site
  • beachline สามารถแทนได้ด้วยลำดับของจุดอย่างง่าย

• ส่วนโค้งใหม่จะเกิดขึ้นเมื่อเส้นกวาดพบ site ใหม่

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

• ขอบเขตที่ตัดกันและวงกลมล้อมรอบ

  • เมื่อมีสาม site อยู่บนเส้นรอบวงเดียวกัน จุดศูนย์กลางของวงกลมจะอยู่ห่างจากทั้งสามจุดเท่ากัน
  • จุดศูนย์กลางของวงกลมล้อมรอบจะกลายเป็นจุดยอดโวโรนอย

• ขอบเขตที่ยังไม่สมบูรณ์

  • ขอบเขตที่ยังไม่สมบูรณ์มีปลายด้านหนึ่งเป็นจุดคงที่ และอีกด้านเป็นจุดตัดของส่วนโค้งสองส่วน
  • เมื่อขอบเขตที่ยังไม่สมบูรณ์สองเส้นชนกัน จะเกิดจุดยอดโวโรนอย และขอบเขตที่ยังไม่สมบูรณ์จะถูกแปลงเป็น half-edge

• มีเพียงวงกลมแบบทวนเข็มนาฬิกาเท่านั้นที่สร้างเหตุการณ์วงกลม

  • จะเกิดเหตุการณ์วงกลมก็ต่อเมื่อส่วนโค้งสามส่วนถูกอ่านในทิศทางทวนเข็มนาฬิกาเท่านั้น

• สรุป

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