fbpx
วิกิพีเดีย

ขั้นตอนวิธีของฟอร์จูน

ตุลาคม 27, 2021

ขั้นตอนวิธีของฟอร์จูน คือขั้นตอนวิธีแบบเส้นกวาด (sweep line algorithm) ที่ใช้สำหรับสร้างแผนภาพโวโรนอย จากเซตของจุดบนระนาบ โดยใช้เวลา ซึ่งคิดค้นขึ้นโดย Steven Fortune ในปี 1986

ประวัติ

ในอดีตหลายปีที่ผ่านมาได้มีผู้ที่คิดค้นขั้นตอนวิธีสำหรับการสร้างแผนโวโรนอยโดยใช้เวลาในการคำนวณเป็น   ในเวลาต่อมา ได้มีผู้คิดค้นขั้นตอนวิธีที่รวดเร็วกว่า โดยใช้เวลาในการคำนวณเป็น   โดยขั้นตอนวิธีดังกล่าว คิดโดยพื้นฐานของขั้นตอนวิธีแบบแบ่งแยกและเอาชนะ (divide and conquer) แต่วิธีการนี้ มีความซับซ้อนมาก และยากที่จะทำความเข้าใจ ด้วยเหตุนี้ ภายหลัง Steven Fortune จึงได้คิดค้นวิธีเส้นกวาดนี้ขึ้นมาเพื่อแก้ปัญหาดังกล่าว โดยยังคงใช้เวลาในการคำนวณเท่าเดิม คือ  

หลักการทำงานของขั้นตอนวิธีเส้นกวาด

วิธีการนี้จะมีสองส่วนที่ต้องสนใจคือเส้นกวาด (sweep line) และเส้นคลื่นทะเล (beach line) แผนภาพโวโรนอยจะค่อยๆถูกสร้างขึ้น ตามแนวเส้นกวาด ที่กวาดไซท์ต่างๆ ไป จากบนลงล่าง โดยจะค่อยๆ พิจารณาทีละไซท์ ตามที่เส้นกวาด กวาดไปพบ นั่นคือ ทำการพิจารณาไซท์ต่างๆ ที่อยู่ด้านบนของเส้นกวาดก่อน ส่วนไซท์ที่อยู่หลังเส้นกวาด จะยังไม่นำมาพิจารณา

ส่วนเส้นคลื่นทะเลนั้นจะมีลักษณะเป็นเส้นโค้ง คอยไล่ตามเส้นกวาด โดยจะมีลักษณะคล้ายกับส่วนหนึ่งของเส้นโค้งพาราโบล่า แต่ละไซท์จะมีเส้นคลื่นทะเลเป็นของตนเอง โดยจากตำแหน่งใดๆ บนเส้นคลื่นทะเลนั้น จะมีระยะห่างระหว่างจุดนั้นถึงไซท์ของมัน และ จากจุดนั้นถึงเส้นกวาด เป็นระยะทางเท่าๆ กัน

อีกหนึ่งจุดที่สำคัญคือจุดหยุด (break point) คือ ตำแหน่งที่เกิดจากการส่วนโค้ง (arc) ของสองเส้นคลื่นทะเลมาบรรจบกัน อยู่บนเส้นเชื่อมโวโรนอย (voronoi edge) โดยมันจะเลื่อนตามเส้นเชื่อมลงมาเรื่อยๆ ตามที่เส้นคลื่นทะเลเลื่อนลงมา ซึ่งจุดนี้เป็นจุดที่มีระยะห่าง จากจุดถึงไซท์ที่เส้นคลื่นทะเลมาบรรจบกัน และ จากจุดถึงเส้นกวาด เท่ากัน

ลักษณะการเคลื่อนตัวของทั้งสองเส้น เพื่อสร้างแผนภาพจะเป็นดังนี้

เหตุการณ์สำคัญ

ระหว่างการเคลื่อนที่ของทั้งสามจุดนี้ จะมีเหตุการณ์สำคัญ(significant event) ที่ทำให้เกิดการเปลี่ยนแปลงของโครงสร้าง และการเปลี่ยนแปลงของลักษณะของเส้นคลื่นทะเล ที่ต้องพิจารณาด้วย คือ

  • สถานะของเส้นกวาด - ตำแหน่งปัจจุบันของเส้นกวาด (พิกัด y) ซึ่งเป็นตัวกำหนดเส้นคลื่นทะเล
  • เหตุการณ์การพบไซท์ - เส้นกวาดเคลื่อนที่จนพบไซท์ ทำให้เกิดการแทรกเส้นโค้งเข้ามาที่เส้นคลื่นทะเลเดิม ทำให้เส้นคลื่นทะเลเดิมถูกแยกเป็นสองส่วน ดังภาพ
  • เหตุการณ์การเกิด vertex (circle events) - เมื่อความยาวของเส้นโค้งพาราโบล่าหดจนเหลือ 0 (เส้นโค้งหายไป) จะเกิด voronoi vertex ที่จุดศูนย์กลางของวงกลมที่มีเส้นรอบวงสัมผัสไซท์ รอบตัว 3 ไซท์ และ เส้นกวาด

การเก็บสถานะของแผนภาพโวโรนอย เส้นกวาด และ เส้นคลื่นทะเล

  • สถานะของแผนภาพโวโรนอย ใช้ Doubly linked list (D) ทำให้เราสามารถสำรวจ ส่วน เซลล์ และ vertices ของแผนภาพได้
  • สถานะของเส้นคลื่นทะเล

ใช้ Balanced Binary Tree (T) • โนดภายในต้นไม้ แสดงถึงจุดหยุดระหว่างสองเส้นโค้งคลื่นทะเล • ใบของต้นไม้แสดงถึงเส้นโค้ง โดยเส้นโค้งถูกแสดงจากไซท์ของตนเอง

  • สถานะของเส้นกวาด ใช้ Priority event queue (Q)

ขั้นตอนวิธี

  1. กำหนดค่าเริ่มต้น
  • Event queue Q ß เหตุการณ์การพบ site ทุกเหตุการณ์
  • Binary search tree T ß Æ
  • Doubly linked list D ß Æ

2. While Q not Æ,

  • Remove event (e) from Q with largest y-coordinate
  • ลบเหตุการณ์ที่มีค่าพิกัด y สูงสุด ออกจากคิว
  • HandleEvent(e, T, D)

การจัดการกับเหตุการณ์ต่างๆ

การจัดการกับเหตุการณ์การพบ site

  1. ค้นหาตำแหน่งของเส้นโค้งที่อยู่เหนือ site ใหม่ที่พบ
  2. ลบเส้นโค้งโดยแทนที่ใบ(เส้นโค้งนั้น) ด้วยต้นไม้ย่อยที่แสดงถึงเส้นโค้งเส้นใหม่ และจุดหยุดจุดใหม่ที่เกิดขึ้น
  3. เพิ่มข้อมูลสอง half-edge ใหม่ที่ได้ ใน doubly linked list
  4. ตรวจสอบเหตุการณ์การเกิด vertex ทำการเพิ่มเข้าไปใน event queue หากพบเหตุการณ์

การจัดการกับเหตุการณ์การเกิด vertex

  1. เพิ่ม vertex ใน doubly linked list
  2. ลบเส้นโค้งที่หายไป
  3. เพิ่มข้อมูลเส้นเชื่อม ใหม่ที่เกิด ลงใน doubly linked list
  4. ตรวจสอบไซท์ เพื่อดูการเกิดเหตุการณ์

วิเคราะห์ประสิทธิภาพเชิงเวลา

การจัดการกับเหตุการณ์การพบ site

  1. ค้นหาตำแหน่งของเส้นโค้งที่อยู่เหนือ site ใหม่ที่พบ
  2. ลบเส้นโค้งโดยแทนที่ใบ(เส้นโค้งนั้น) ด้วยต้นไม้ย่อยที่แสดงถึงเส้นโค้งเส้นใหม่ และจุดหยุดจุดใหม่ที่เกิดขึ้น
  3. เพิ่มข้อมูลสอง half-edge ใหม่ที่ได้ ใน doubly linked list
  4. ตรวจสอบเหตุการณ์การเกิด vertex ทำการเพิ่มเข้าไปใน event queue หากพบเหตุการณ์จะได้
  5. O(logn)
  6. O(1)
  7. O(1)
  8. O(1)

การจัดการกับเหตุการณ์การเกิด vertex

  1. เพิ่ม vertex ใน doubly linked list
  2. ลบเส้นโค้งที่หายไป
  3. เพิ่มข้อมูลเส้นเชื่อมใหม่ที่เกิด ลงใน doubly linked list
  4. ตรวจสอบไซท์ เพื่อดูการเกิดเหตุการณ์จะได้
  5. O(logn)
  6. O(1)
  7. O(1)
  8. O(1)

สรุป

แต่ละ site ใหม่ จะทำให้เกิดเส้นโค้งใหม่ได้มากสุด สองเส้น

  • เส้นคลื่นทะเลสามารถมีเส้นโค้งได้มากสุด 2n-1 เส้น
  • มากสุด   สำหรับ site และ เหตุการณ์การเกิด vertex ในคิว
  • การจัดการทำเหตุการณืทั้งสองแบบใช้เวลา  

ดังนั้น เวลาทั้งหมดที่ใช้ คือ  

รหัสเทียม

let * (z) be the transformation * (z) = (zx,zy + d(z)), where d(z) is a parabola with minimum at z let T be the "beach line" let Rp be the region covered by site p. let Cpq be the boundary ray between sites p and q. let p1,p2,...,pm be the sites with minimal y-coordinate, ordered by x-coordinate create initial vertical boundary rays while not IsEmpty(Q) do p ← DeleteMin(Q) case p of p is a site in * (V): find the occurrence of a region * (Rq) in T containing p,  bracketed by Crq on the left and Cqs on the right create new boundary rays and with bases p replace * (Rq) with in T delete from Q any intersection between Crq and Cqs insert into Q any intersection between Crq and insert into Q any intersection between and Cqs p is a Voronoi vertex in * (V): let p be the intersection of Cqr on the left and Crs on the right let Cuq be the left neighbor of Cqr and  let Csv be the right neighbor of Crs in T create a new boundary ray if qy = sy,  or create if p is right of the higher of q and s,  otherwise create replace Cqr, * (Rr),Crs with newly created Cqs in T delete from Q any intersection between Cuq and Cqr delete from Q any intersection between Crs and Csv insert into Q any intersection between Cuq and Cqs insert into Q any intersection between Cqs and Csv record p as the summit of Cqr and Crs and the base of Cqs output the boundary segments Cqr and Crs endcase endwhile output the remaining boundary rays in T

อ้างอิง

  1. http://www.donhavey.com/blog/tutorials/tutorial-7-voronoi-diagrams 2012-04-03 ที่ เวย์แบ็กแมชชีน
  2. http://nms.csail.mit.edu/~aklmiu/6.838/L7.pdf
  3. http://en.wikipedia.org/wiki/Fortune%27s_algorithm
  4. http://en.wikipedia.org/wiki/Voronoi_diagram
  5. http://www.skynet.ie/~sos/mapviewer/docs/Voronoi_Diagram_Notes_1.pdf 2012-02-07 ที่ เวย์แบ็กแมชชีน
  6. http://www.diku.dk/hjemmesider/studerende/duff/Fortune/ 2014-12-27 ที่ เวย์แบ็กแมชชีน

ตุลาคม 27, 2021
นตอนว, ของฟอร, บทความน, ได, บแจ, งให, ปร, บปร, งหลายข, กร, ณาช, วยปร, บปร, งบทความ, หร, ออภ, ปรายป, ญหาท, หน, าอภ, ปราย, บทความน, องการพ, จน, กษร, อาจเป, นด, านการใช, ภาษา, การสะกด, ไวยากรณ, ปแบบการเข, ยน, หร, อการแปลจากภาษาอ, อข, นตอนว, แบบเส, นกวาด, sweep, l. bthkhwamniidrbaecngihprbprunghlaykhx krunachwyprbprungbthkhwam hruxxphipraypyhathihnaxphipray bthkhwamnitxngkarphisucnxksr xacepndankarichphasa karsakd iwyakrn rupaebbkarekhiyn hruxkaraeplcakphasaxunkhntxnwithikhxngfxrcun khuxkhntxnwithiaebbesnkwad sweep line algorithm thiichsahrbsrangaephnphaphowornxy cakestkhxngcudbnranab odyichewla O n l o g n displaystyle O n log n sungkhidkhnkhunody Steven Fortune inpi 1986 enuxha 1 prawti 2 hlkkarthangankhxngkhntxnwithiesnkwad 3 ehtukarnsakhy 4 karekbsthanakhxngaephnphaphowornxy esnkwad aela esnkhlunthael 5 khntxnwithi 6 karcdkarkbehtukarntang 6 1 karcdkarkbehtukarnkarphb site 6 2 karcdkarkbehtukarnkarekid vertex 7 wiekhraahprasiththiphaphechingewla 7 1 karcdkarkbehtukarnkarphb site 7 2 karcdkarkbehtukarnkarekid vertex 8 srup 9 rhsethiym 10 xangxingprawti aekikhinxdithlaypithiphanmaidmiphuthikhidkhnkhntxnwithisahrbkarsrangaephnowornxyodyichewlainkarkhanwnepn O n 2 displaystyle O n 2 inewlatxma idmiphukhidkhnkhntxnwithithirwderwkwa odyichewlainkarkhanwnepn O n l o g n displaystyle O n log n odykhntxnwithidngklaw khidodyphunthankhxngkhntxnwithiaebbaebngaeykaelaexachna divide and conquer aetwithikarni mikhwamsbsxnmak aelayakthicathakhwamekhaic dwyehtuni phayhlng Steven Fortune cungidkhidkhnwithiesnkwadnikhunmaephuxaekpyhadngklaw odyyngkhngichewlainkarkhanwnethaedim khux O n l o g n displaystyle O n log n hlkkarthangankhxngkhntxnwithiesnkwad aekikhwithikarnicamisxngswnthitxngsnickhuxesnkwad sweep line aelaesnkhlunthael beach line aephnphaphowornxycakhxythuksrangkhun tamaenwesnkwad thikwadisthtang ip cakbnlnglang odycakhxy phicarnathilaisth tamthiesnkwad kwadipphb nnkhux thakarphicarnaisthtang thixyudanbnkhxngesnkwadkxn swnisththixyuhlngesnkwad cayngimnamaphicarnaswnesnkhlunthaelnncamilksnaepnesnokhng khxyiltamesnkwad odycamilksnakhlaykbswnhnungkhxngesnokhngpharaobla aetlaisthcamiesnkhlunthaelepnkhxngtnexng odycaktaaehnngid bnesnkhlunthaelnn camirayahangrahwangcudnnthungisthkhxngmn aela cakcudnnthungesnkwad epnrayathangetha knxikhnungcudthisakhykhuxcudhyud break point khux taaehnngthiekidcakkarswnokhng arc khxngsxngesnkhlunthaelmabrrcbkn xyubnesnechuxmowornxy voronoi edge odymncaeluxntamesnechuxmlngmaeruxy tamthiesnkhlunthaeleluxnlngma sungcudniepncudthimirayahang cakcudthungisththiesnkhlunthaelmabrrcbkn aela cakcudthungesnkwad ethaknlksnakarekhluxntwkhxngthngsxngesn ephuxsrangaephnphaphcaepndngniehtukarnsakhy aekikhrahwangkarekhluxnthikhxngthngsamcudni camiehtukarnsakhy significant event thithaihekidkarepliynaeplngkhxngokhrngsrang aelakarepliynaeplngkhxnglksnakhxngesnkhlunthael thitxngphicarnadwy khux sthanakhxngesnkwad taaehnngpccubnkhxngesnkwad phikd y sungepntwkahndesnkhlunthael ehtukarnkarphbisth esnkwadekhluxnthicnphbisth thaihekidkaraethrkesnokhngekhamathiesnkhlunthaeledim thaihesnkhlunthaeledimthukaeykepnsxngswn dngphaphehtukarnkarekid vertex circle events emuxkhwamyawkhxngesnokhngpharaoblahdcnehlux 0 esnokhnghayip caekid voronoi vertex thicudsunyklangkhxngwngklmthimiesnrxbwngsmphsisth rxbtw 3 isth aela esnkwadkarekbsthanakhxngaephnphaphowornxy esnkwad aela esnkhlunthael aekikhsthanakhxngaephnphaphowornxy ich Doubly linked list D thaiherasamarthsarwc swn esll aela vertices khxngaephnphaphidsthanakhxngesnkhlunthaelich Balanced Binary Tree T ondphayintnim aesdngthungcudhyudrahwangsxngesnokhngkhlunthael ibkhxngtnimaesdngthungesnokhng odyesnokhngthukaesdngcakisthkhxngtnexng sthanakhxngesnkwad ich Priority event queue Q khntxnwithi aekikhkahndkhaerimtnEvent queue Q ss ehtukarnkarphb site thukehtukarn Binary search tree T ss AE Doubly linked list D ss AE2 While Q not AE Remove event e from Q with largest y coordinate lbehtukarnthimikhaphikd y sungsud xxkcakkhiw HandleEvent e T D karcdkarkbehtukarntang aekikhkarcdkarkbehtukarnkarphb site aekikh khnhataaehnngkhxngesnokhngthixyuehnux site ihmthiphb lbesnokhngodyaethnthiib esnokhngnn dwytnimyxythiaesdngthungesnokhngesnihm aelacudhyudcudihmthiekidkhun ephimkhxmulsxng half edge ihmthiid in doubly linked list trwcsxbehtukarnkarekid vertex thakarephimekhaipin event queue hakphbehtukarnkarcdkarkbehtukarnkarekid vertex aekikh ephim vertex in doubly linked list lbesnokhngthihayip ephimkhxmulesnechuxm ihmthiekid lngin doubly linked list trwcsxbisth ephuxdukarekidehtukarnwiekhraahprasiththiphaphechingewla aekikhkarcdkarkbehtukarnkarphb site aekikh khnhataaehnngkhxngesnokhngthixyuehnux site ihmthiphb lbesnokhngodyaethnthiib esnokhngnn dwytnimyxythiaesdngthungesnokhngesnihm aelacudhyudcudihmthiekidkhun ephimkhxmulsxng half edge ihmthiid in doubly linked list trwcsxbehtukarnkarekid vertex thakarephimekhaipin event queue hakphbehtukarncaid O logn O 1 O 1 O 1 karcdkarkbehtukarnkarekid vertex aekikh ephim vertex in doubly linked list lbesnokhngthihayip ephimkhxmulesnechuxmihmthiekid lngin doubly linked list trwcsxbisth ephuxdukarekidehtukarncaid O logn O 1 O 1 O 1 srup aekikhaetla site ihm cathaihekidesnokhngihmidmaksud sxngesn esnkhlunthaelsamarthmiesnokhngidmaksud 2n 1 esn maksud O n displaystyle O n sahrb site aela ehtukarnkarekid vertex inkhiw karcdkarthaehtukarnuthngsxngaebbichewla O l o g n displaystyle O log n dngnn ewlathnghmdthiich khux O n l o g n displaystyle O n log n rhsethiym aekikhlet z be the transformation z zx zy d z where d z is a parabola with minimum at z let T be the beach line let Rp be the region covered by site p let Cpq be the boundary ray between sites p and q let p1 p2 pm be the sites with minimal y coordinate ordered by x coordinate create initial vertical boundary rays while not IsEmpty Q do p DeleteMin Q case p of p is a site in V find the occurrence of a region Rq in T containing p bracketed by Crq on the left and Cqs on the right create new boundary rays and with bases p replace Rq with in T delete from Q any intersection between Crq and Cqs insert into Q any intersection between Crq and insert into Q any intersection between and Cqs p is a Voronoi vertex in V let p be the intersection of Cqr on the left and Crs on the right let Cuq be the left neighbor of Cqr and let Csv be the right neighbor of Crs in T create a new boundary ray if qy sy or create if p is right of the higher of q and s otherwise create replace Cqr Rr Crs with newly created Cqs in T delete from Q any intersection between Cuq and Cqr delete from Q any intersection between Crs and Csv insert into Q any intersection between Cuq and Cqs insert into Q any intersection between Cqs and Csv record p as the summit of Cqr and Crs and the base of Cqs output the boundary segments Cqr and Crs endcase endwhile output the remaining boundary rays in Txangxing aekikhhttp www donhavey com blog tutorials tutorial 7 voronoi diagrams Archived 2012 04 03 thi ewyaebkaemchchin http nms csail mit edu aklmiu 6 838 L7 pdf http en wikipedia org wiki Fortune 27s algorithm http en wikipedia org wiki Voronoi diagram http www skynet ie sos mapviewer docs Voronoi Diagram Notes 1 pdf Archived 2012 02 07 thi ewyaebkaemchchin http www diku dk hjemmesider studerende duff Fortune Archived 2014 12 27 thi ewyaebkaemchchin ekhathungcak https th wikipedia org w index php title khntxnwithikhxngfxrcun amp oldid 9617467, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม