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

 (redpenguin101.github.io)
2 คะแนน โดย GN⁺ 2025-02-10 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Fortune’s Algorithm สามารถสร้างไดอะแกรมโวโรนอยได้ในเวลา O(n log n) แต่การนำไปใช้งานจริงค่อนข้างซับซ้อน ดังนั้นหากไม่ได้เป็นกรณีที่ต้องสร้างไดอะแกรมขนาดใหญ่ซ้ำ ๆ บ่อยครั้ง การใช้วิธี O(n²) หรือใช้ไลบรารีมักจะใช้งานได้จริงมากกว่า
  • ไดอะแกรมโวโรนอยแบ่งระนาบออกเป็นบริเวณที่ใกล้กับ site แต่ละจุดมากที่สุด โดยเส้นขอบเกิดจากจุดที่อยู่ห่างจากสอง site เท่ากัน
  • อัลกอริทึมจะคงสถานะของ sweep line ที่เคลื่อนจากซ้ายไปขวา และ beachline ซึ่งเป็นแนวหน้าของส่วนโค้งพาราโบลา แล้วประมวลผลเฉพาะ site event และ circle event
  • site event จะแทรกส่วนโค้งใหม่ แบ่งส่วนโค้งเดิม และสร้าง incomplete edge ส่วน circle event จะลบส่วนโค้งตรงกลาง พร้อมทำให้ Voronoi Vertex และ half edge สมบูรณ์
  • ในการติดตั้งใช้งานจริง ต้องจัดการทั้ง event queue, beachline, แผนที่ของ incomplete edge และ DCEL ไปพร้อมกัน อีกทั้งการลบ circle event ที่ใช้ไม่ได้แล้วและการเก็บกวาด edge ที่เหลือยังเพิ่มความซับซ้อนอย่างมาก

ความยากของการติดตั้งใช้งานและขอบเขตการนำไปใช้

  • Fortune’s Algorithm เป็นอัลกอริทึมสำหรับสร้างไดอะแกรมโวโรนอยในเวลา O(n log n)
  • หากเป้าหมายคือการใช้งานจริง ควรประเมินขนาดงานที่ต้องการก่อนมากกว่าจะรีบลงมือเขียนเองทันที
    • ถ้าไม่ได้ต้องสร้างไดอะแกรมขนาดใหญ่หลายชุดต่อวินาที การใช้วิธี O(n²) อาจเป็นตัวเลือกที่ง่ายกว่า
    • ทางเลือกที่ใช้งานได้จริงยิ่งกว่าคือใช้ ไลบรารี ที่มีอยู่แล้ว
  • แม้ผลลัพธ์การทำงานของอัลกอริทึมจะดูน่าสนใจในเชิงภาพ แต่กระบวนการติดตั้งใช้งานจริงนั้นค่อนข้างยากและชวนท้อพอสมควร

แนวคิดพื้นฐานของไดอะแกรมโวโรนอย

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

sweep line, beachline, event

  • Fortune’s Algorithm ใช้เส้นแนวตั้งที่เคลื่อนจากซ้ายไปขวา เรียกว่า sweep line
  • เมื่อ sweep line พบ site จะเกิดส่วนโค้งพาราโบลาที่มี site นั้นเป็นโฟกัส และเมื่อ sweep line เคลื่อนออกห่าง ส่วนโค้งจะใหญ่ขึ้น
  • จุดที่ส่วนโค้งจากคนละ site สองเส้นมาพบกันเป็นจุดที่ห่างจากสอง site เท่ากัน จึงกลายเป็นขอบเขตของเซลล์
  • เมื่อขอบเขตสองเส้นมาพบกัน จะเกิดจุดยอดของไดอะแกรม
  • แนวหน้าของส่วนโค้งที่ยังทำงานอยู่เรียกว่า beachline
  • การติดตั้งใช้งานจริงจะไม่เลื่อน sweep line ทีละพิกเซล แต่จะประมวลผลเฉพาะจุดเฉพาะที่คำนวณได้ซึ่งเรียกว่า event
    • site event: นิยามจากพิกัดของ site ที่รู้ล่วงหน้า และเมื่อประมวลผลจะมีการเพิ่มส่วนโค้งใหม่ลงใน beachline
    • circle event: นิยามจากส่วนโค้งสามเส้นบน beachline และเมื่อประมวลผลจะมีการลบส่วนโค้งหนึ่งเส้น พร้อมสร้าง Voronoi Vertex และ half edge

การหาขอบเขตด้วยพาราโบลา

  • ในอัลกอริทึมนี้ พาราโบลาไม่ได้ถูกมองในรูปแบบทั่วไปอย่าง y = ax^2 + bx + c แต่พิจารณาด้วย locus definition
  • พาราโบลาถูกนิยามด้วย focus point หนึ่งจุดและ directrix หนึ่งเส้น
    • focus point คือ site
    • directrix คือ sweep line
  • จุดตัดของพาราโบลาสองเส้นที่ใช้ sweep line เดียวกันเป็น directrix จะอยู่ห่างจากสอง site เท่ากัน
  • ดังนั้นเมื่อหาจุดตัดของพาราโบลาสองเส้นได้ ก็จะหาตำแหน่งของ equiedge ระหว่างสอง site ได้
  • มีการใช้ทั้ง pseudocode สำหรับคำนวณพิกัด x ของพาราโบลา และตัวอย่างที่แสดงว่าจุดตัดของพาราโบลาสองเส้นเคลื่อนที่ไปตามขอบเขตอย่างไรเมื่อ sweep line เปลี่ยนตำแหน่ง

การแทน beachline และการจัดการ site event

  • ส่วนโค้งแต่ละเส้นใน beachline สามารถแทนได้ด้วยพิกัดของ site ที่เกี่ยวข้องเพียงอย่างเดียว
    • sweep line เป็นค่าที่ใช้ร่วมกันกับทุกส่วนโค้ง
    • ในการติดตั้งใช้งานจริง ส่วนโค้งจึงถูกจัดการเป็น พิกัด 2D แทนการสร้างเป็นอ็อบเจ็กต์แยกต่างหาก
  • beachline สามารถแทนเป็นลำดับของจุดแบบง่าย ๆ ได้
    • ตัวอย่าง: [arc1, arc2], [arc1, arc2, arc3]
    • ส่วนโค้งจาก site เดียวกันสามารถปรากฏหลายครั้งบน beachline ได้
    • ตัวอย่าง: [arc1, arc3, arc1, arc2]
  • เมื่อเกิด site event จะต้องหาส่วนโค้งบน beachline ที่ถูกตัดโดยเส้นที่ลากไปทางซ้ายจาก site ใหม่ แล้วให้ส่วนโค้งใหม่ แยก ส่วนโค้งนั้น
  • หาก site ใหม่ L ไปแบ่ง j ใน beachline เดิม [.., i, j, k, ..] โครงสร้างจะกลายเป็น [.., i, j, L, j, k, ..]
  • site จะถูกใส่ในคิวตามลำดับพิกัด x และทุกครั้งที่ประมวลผล จะมีการอัปเดต beachline และ candidate ของ event

circle event และ circumcircle

  • หากใน beachline ที่เป็น [.., i, j, k, ..] มีสถานการณ์ที่ขอบเขตสองเส้นมาบรรจบกัน ส่วนโค้งตรงกลาง j จะหายไป
  • ในกรณีนี้จะมี circumcircle ที่ผ่านทั้งสาม site และจุดศูนย์กลางของวงกลมจะอยู่ห่างจากทั้งสาม site เท่ากัน
  • จุดศูนย์กลางของ circumcircle จะกลายเป็น Voronoi Vertex
  • circle event จะถูกวางใน event queue โดยอิงจาก circle point ซึ่งเป็นจุดปลายด้านขวาของวงกลม
  • หากมี site ใหม่ถูกพบภายในวงกลมก่อนที่ sweep line จะถึง circle point, circle event เดิมจะใช้ไม่ได้
    • เพราะ site ใหม่จะเข้าไปแบ่งส่วนโค้งตรงกลางก่อน ทำให้ชุดของสามส่วนโค้งเดิมไม่คงอยู่ต่อไป
    • triple เดิม i, j, k จะหายไป และต้องตรวจสอบ triple ใหม่อย่าง i, j, L, L, j, k

incomplete edge และ half edge

  • incomplete edge คือเส้นที่ปลายด้านหนึ่งถูกกำหนดแล้ว แต่อีกปลายหนึ่งยังนิยามด้วยจุดตัดของส่วนโค้งพาราโบลาสองเส้น
  • เมื่อมีการแทรกส่วนโค้งใหม่จาก site event จะเกิด incomplete edge สองเส้น
    • จุดตรึงคือพิกัดที่ส่วนโค้งใหม่มาพบกับ beachline เดิม
    • หากส่วนโค้งใหม่ j ไปแบ่งส่วนโค้งเดิม i จะเกิด edge ที่สอดคล้องกับจุดตัด [i, j], [j, i]
  • เมื่อ incomplete edge สองเส้นชนกันใน circle event จุดชนจะกลายเป็น Voronoi Vertex
  • incomplete edge เดิมจะสมบูรณ์เป็น half edge ที่จุดนี้ และจะมีการสร้าง incomplete edge ใหม่ขึ้นระหว่างส่วนโค้งสองเส้นที่กลายเป็นเพื่อนบ้านกันใหม่

เฉพาะวงกลมทวนเข็มนาฬิกาเท่านั้นที่เป็น circle event

  • เมื่อ beachline เป็น [i, j, k, j, i] ทั้ง ijk และ kji อาจสร้างวงกลมได้ แต่ไม่ได้หมายความว่าทั้งสองจะเป็น circle event ที่ใช้ได้
  • กรณีที่ส่วนโค้งตรงกลางหายไปจะเกิดขึ้นเฉพาะด้านที่ขอบเขตบรรจบเข้าหากันจริงเท่านั้น
  • ในโปรแกรม จะตัดสิน orientation ของสามจุดด้วย determinant
    • หาก determinant เป็นลบ จะเป็นทิศทางทวนเข็มนาฬิกาและนับเป็น circle event
    • หาก determinant เป็นบวก จะเป็นทิศทางตามเข็มนาฬิกาและไม่เป็น circle event
    • หาก determinant เป็น 0 แสดงว่าสามจุดอยู่บนเส้นตรงเดียวกัน จึงไม่มีวงกลม

ลำดับการทำงานของอัลกอริทึมทั้งหมด

  • เรียงลำดับ site นำเข้าตามพิกัด x แล้วใส่ลงคิวเป็น site event
  • ดึง event ถัดไปจากคิวออกมาประมวลผลจนกว่าคิวจะว่าง
  • การประมวลผล site event:
    • ลบ circle event ที่ยังเหลืออยู่ล่วงหน้าซึ่ง site ใหม่เข้าไปอยู่ภายในวงกลม
    • หา arc บน beachline ที่ site ใหม่จะเข้าไปแบ่ง
    • แทรกส่วนโค้งใหม่เพื่อแบ่งส่วนโค้งเดิม
    • เพิ่ม incomplete edge สองเส้น
    • ตรวจสอบว่า triple ที่เกิดขึ้นใหม่สามารถสร้าง circle event ได้หรือไม่
  • การประมวลผล circle event:
    • เพิ่มจุดศูนย์กลางของ circumcircle เป็น Voronoi Vertex
    • ลบส่วนโค้งตรงกลางออกจาก beachline
    • ลบ circle event ในอนาคตที่กลายเป็นใช้ไม่ได้เพราะส่วนโค้งนี้ถูกลบออก
    • ตรวจสอบ triple ของส่วนโค้งที่กลายเป็นเพื่อนบ้านกันใหม่ แล้วเพิ่ม circle event หากมี
  • เมื่อคิวว่าง ให้ยืด incomplete edge ที่เหลือไปจนถึงขอบเขตของไดอะแกรม และสร้าง Voronoi Vertex ที่จุดตัดกับขอบเขต

โครงสร้างข้อมูลของเวอร์ชันติดตั้งใช้งานด้วย Odin

  • ตัวอย่างการติดตั้งใช้งานเขียนด้วย Odin ซึ่งเป็นภาษาอีกทางเลือกหนึ่งของ C
  • โค้ดทั้งหมดอยู่ในรีโพซิทอรี RedPenguin101/voronoi
  • ชนิดข้อมูลพื้นฐาน:
    • V2: จุด 2D ในรูปแบบ [2]int
    • PointPair: คู่ของ V2 สองค่า
    • Event: โครงสร้าง {site: bool, a, b, c: V2}
  • ความหมายของ Event จะแตกต่างกันตามชนิด
    • ใน site event, a คือพิกัดของ site ส่วน b, c จะไม่ถูกใช้
    • ใน circle event, a, b, c คือส่วนโค้งสามเส้นบน beachline ที่สร้าง event นั้น
  • โครงสร้าง Fortune จัดการสถานะต่อไปนี้
    • beachline: อาร์เรย์ของ V2
    • queue: อาร์เรย์ของ Event
    • incomplete_edges: แมป PointPair -> V2
    • vd: DCEL สำหรับเก็บ Voronoi Diagram

ส่วนที่ละไว้หรือทำให้ง่ายลงในการติดตั้งใช้งาน

  • แม้ beachline จะถูกแทนด้วยเวกเตอร์ แต่หากต้องการประสิทธิภาพสูงขึ้น binary tree จะเหมาะสมกว่า
  • event queue ตามแนวคิดควรเป็น priority queue แต่ในตัวอย่างนี้ใช้วิธีแทรกลงอาร์เรย์แบบเรียงลำดับ
  • การทำให้ circle event ใช้ไม่ได้ถูกจัดการด้วยการไล่ตรวจ event ในอนาคตทีละตัว และยังมี TODO ว่าควรหาวิธีที่เร็วกว่า
  • clean_beachline_edges คือขั้นตอนตัดส่วนโค้งที่ไม่จำเป็นออกจากปลายทั้งสองด้านของ beachline
  • ในการติดตั้งใช้งานมีการจัดการกรณียกเว้น เช่น site ที่มีพิกัด x เท่ากัน, กรณี circle point ตรงกับ site, และการชนกันของ reference point
  • ขั้นตอนสุดท้ายหลังคิวว่าง ซึ่งต้องเก็บกวาด incomplete edge ที่เหลือ, half edge ที่ไม่มี twin, และ vertex ต่าง ๆ ถูกกล่าวถึงเพียงในระดับการคำนวณทางคณิตศาสตร์อย่างง่าย

การเก็บไดอะแกรมโวโรนอยด้วย DCEL

  • โดยทั่วไปไดอะแกรมโวโรนอยจะถูกเก็บด้วย Doubly Connected Edge List (DCEL)
  • DCEL เป็นโครงสร้างข้อมูลที่ช่วยให้จัดการ cell-complex ซึ่งประกอบด้วย vertex และ edge ได้สะดวก
  • แม้จะเป็นการแทนข้อมูลแบบยึด edge เป็นศูนย์กลาง แต่ก็เก็บข้อมูลของ vertex และ face ไว้ด้วย
  • edge ปกติไม่มีทิศทาง แต่ใน DCEL จะเก็บ edge แต่ละเส้นเป็น half edge สองเส้นที่มีทิศทางตรงข้ามกัน
  • vertex ที่เก็บใน DCEL ของไดอะแกรมโวโรนอยไม่ใช่ site แต่เป็น Voronoi Vertex
  • ปลายทางของ edge E สามารถหาได้จาก E.twin.origin และ face ด้านขวาหาได้จาก E.twin.left

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-02-10
ความคิดเห็นจาก Hacker News

  • เมื่อก่อนเคยทำ implementation ด้วย ClojureScript ที่แสดงภาพเคลื่อนไหวของการทำงานของอัลกอริทึม Fortune: https://voronoi.ajwerner.net/#/app-diagrams
    เป็นอัลกอริทึมที่สวยงามมาก
    แต่หลังจากโปรเจ็กต์นั้นก็เริ่มไม่ค่อยชอบ อัลกอริทึม Fortune เท่าไร เพราะมีปัญหาเรื่องเสถียรภาพเชิงตัวเลขของ floating point
    ถ้าจุดต่าง ๆ อยู่บนเส้นตรงเดียวกัน หรือเกือบจะอยู่บนเส้นตรงเดียวกันในระดับ floating point ก็อาจพังได้
    ถ้าจำไม่ผิด ในจุดนี้ delaunator ดีกว่า: https://github.com/mapbox/delaunator

    • แอนิเมชันนี้ดีที่สุดเท่าที่เคยเห็นมา
      เห็นลิงก์ implementation “old” อยู่ในหน้าที่อ้างอิง เลยสงสัยว่าเวอร์ชันแอนิเมชันปัจจุบันมีโอกาสจะเปิดเป็น โอเพนซอร์ส ไหม

  • เมื่อหลายปีก่อนเคยทำ ภาพแสดงผลแบบ 3D นี้ไว้: https://x.com/KangarooPhysics/status/1253336959755251716

  • มี implementation ภาษา JavaScript ของ Raymond Hill ผู้มีชื่อเสียงจาก uBlock Origin: https://github.com/gorhill/Javascript-Voronoi
    ตรงนี้ลองปรับแต่งให้องค์ประกอบขยับได้เล็กน้อย: https://animations.adgent.com/voronoi.html

    • แอนิเมชันนี้ทำให้นึกถึงสไตล์ของ A Scanner Darkly (2006)
      สงสัยว่าน่าจะเอาวิดีโอเป็นอินพุตแล้วป้อนเข้าอัลกอริทึมที่แสดงผลแบบ Voronoi ได้ไหม
      ถ้าถึงขั้นนั้นแล้ว ตามนิยามเคร่งครัดมันอาจไม่ใช่ Voronoi diagram ก็ได้ แต่ก็น่าจะดูเท่มาก

  • D3.js มี implementation ใหม่: https://github.com/d3/d3-delaunay
    ด้านล่างของหน้านั้นมีคำอธิบายเกี่ยวกับ sweep algorithm ที่ใช้ และรายการ implementation ภาษาอื่นนอกเหนือจาก JavaScript
    d3-voronoi เดิมกำลังจะเลิกใช้ แต่ยังดูได้ที่นี่: https://github.com/d3/d3-voronoi

  • ถ้าไม่ได้สนใจเส้นขอบ และแค่อยากระบายแต่ละบริเวณเป็นคนละสี ก็ใช้ flood fill แบบดัดแปลงที่เริ่มจาก seed point ได้
    แค่ใส่พิกเซลลงในสแตกเมื่อระยะของสีนั้นสั้นกว่าสีที่ระบายพิกเซลนั้นไว้อยู่แล้วเท่านั้น

    • สร้างฉาก 3D จาก กรวยตั้งฉาก คนละสี โดยให้ยอดของแต่ละกรวยอยู่ที่แต่ละจุดบนระนาบ 2D และให้แกนตั้งฉากกับระนาบ
      ถ้าเรนเดอร์เป็นภาพฉายแบบออร์โธกราฟิก 2D จากด้านบนยอดกรวย z-buffer จะเก็บพิกเซลของยอดที่ใกล้ที่สุดไว้
      อาจทำด้วยเชดเดอร์ก็ได้ แต่เดโมกรวย 3D แบบคลาสสิกนั้นเข้าใจและทำตามได้ง่ายมาก

  • น่าสนใจที่ D3 ย้ายจากอัลกอริทึม Fortune ไปใช้ https://mapbox.github.io/delaunator/
    เหตุผลคือ “มันเร็วกว่า d3-voronoi 5~10 เท่า ในการสร้าง Delaunay triangulation หรือ Voronoi diagram, มีความทนทานเชิงตัวเลขมากกว่า, มี Canvas rendering ในตัว, รองรับการเดินกราฟ Delaunay และมีการปรับปรุงอื่น ๆ อีกหลายอย่าง”

    • ถ้า D3 มองว่า delaunator เหมาะที่สุดสำหรับเอฟเฟกต์แบบนี้ ตอนนี้ข้ออ้างที่จะยังไม่เพิ่มมันเข้าไปในไลบรารี canvas ของฉัน ก็คงเหลือแค่นิสัยผัดวันประกันพรุ่งตามธรรมชาติเท่านั้น
      โค้ดที่ใช้คำนวณไทล์อยู่ตอนนี้เรียกได้ว่าไร้เดียงสาจนน่าเจ็บปวด
      การพูดคุยใหม่: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120

  • บทความนี้ทำให้ฉันไปค้นดูว่าเดี๋ยวนี้ Steve อยู่ที่ไหน
    เคยรู้จักกันเมื่อหลายสิบปีก่อน

  • บทความที่เกี่ยวข้องและน่าอ่าน: https://news.ycombinator.com/item?id=37998923 - การสร้าง Voronoi diagram และ Delaunay triangulation ใน O(n log n) ด้วยอัลกอริทึม Fortune (2020)
    ในบทความก่อนหน้าและการพูดคุยมีสรุปสั้น ๆ ของอัลกอริทึมอื่น ๆ ด้วย
    ส่วนตัวแล้วฉันยังคงชอบ Jump Flooding Algorithm มากที่สุด: https://en.wikipedia.org/wiki/Jump_flooding_algorithm