fbpx
วิกิพีเดีย

ขั้นตอนวิธีแบบห่อของขวัญ

ขั้นตอนวิธีแบบห่อของขวัญ (อังกฤษ: Gift Wrapping Algorithm) คือวิธีในทาง เรขาคณิตเชิงคำนวณ ที่ใช้ในการคำนวณหา คอนเวกซ์ฮัลล์

ประวัติ

ขั้นตอนวิธีแบบห่อของขวัญมีชื่อเรียกอีกอย่างหนึ่งว่า การเดินแถวของจาร์วิส (อังกฤษ: Jarvis' March) เพื่อเป็นเกียรติแก่ อาร์.เอ. จาร์วิส ผู้นำขั้นตอนวิธีนี้ออกเผยแพร่ในปี พ.ศ. 2516 (หลังจาก โรนัลด์ เกรแฮม นำเสนอเกรแฮมสแกนหนึ่งปี)

ขั้นตอนวิธี

 
การใช้ขั้นตอนวิธีการห่อของขวัญในการหาคอนเวกซ์ฮัลล์

เริ่มจากให้ i = 0 และให้ p0 คือจุดสุดขีดจุดหนึ่ง ซึ่งทราบแน่นอนว่าอยู่บนคอนเวกซ์ฮัลล์ เช่น จุดบนสุด จากนั้น เลือกจุด pi+1 โดย pi+1 คือจุดที่ให้มุมกว้างที่สุดเทียบกับ Pi (อาจเป็นทิศทวนเข็มนาฬิกาหรือตามเข็มนาฬิกาก็ได้) ทำซ้ำเช่นนี้ไปเรื่อยๆ จนกว่าจะได้ ph = p0 คือวนกลับมาจนครบจุดเริ่มต้นนั่นเอง ([1])

รหัสเทียม

jarvis(S) // รับ S ที่เป็นเซทของจุด pointOnHull = จุดสุดขีดจุดหนึ่ง // ตั้งค่า p0 ด้วยจุดสุดขีดจุดหนึ่ง i = 0 // เริ่ม i = 0 repeat P[i] = pointOnHull // เพิ่มค่า pi ลงไปในอาเรย์ของคำตอบ P ช่องที่ i endpoint = S[0] // ตั้งค่าเริ่มต้นสำหรับการหาจุดต่อไปบนคอนเวกซ์ฮัลล์ for j from 1 to |S|-1 // ตรวจสอบทุกจุด if (pointOnHull.angle(S[j]) > pointOnHull.angle(endpoint)) endpoint = S[j] // ถ้าหากมุมของจุดใหม่กว้างกว่าเทียบกับจุดเดิมที่เลือกไปในรอบก่อน ให้เปลี่ยนจุดที่เลือกใหม่ i = i+1 pointOnHull = endpoint // ตั้งค่าจุด pi+1 ให้เป็นจุดหลักสำหรับรอบหน้า until endpoint == P[0] // ทำซ้ำจนกว่าจะครบรอบ 

ประสิทธิภาพ

เนื่องจากเวลาในการหามุมสำหรับแต่ละจุดเป็นค่าคงที่ (O(1)) และการเปรียบเทียบมุมสำหรับทุกคู่จุดจะใช้เวลา O(n) สรุปว่าเราสามารถหาจุดๆหนึ่งบนคอนเวกซ์ฮัลล์ได้ภายในเวลา O(n) และหากมีจุดบนคอนเวกซ์ฮัลล์เป็นจำนวน h จุดแล้ว สรุปได้ว่าการเดินแถวของจาร์วิสจะสามารถหาจุดทุกๆจุดบนคอนเวกซ์ฮัลล์ได้ภายในเวลา O(nh)

การนำไปใช้

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

อ้างอิง

  • Jarvis, R. A. (1973). "On the identification of the convex hull of a finite set of points in the plane". Information Processing Letters. 2: 18–21. doi:10.1016/0020-0190(73)90020-3.

แหล่งข้อมูลอื่น

นตอนว, แบบห, อของขว, งกฤษ, gift, wrapping, algorithm, อว, ในทาง, เรขาคณ, ตเช, งคำนวณ, ใช, ในการคำนวณหา, คอนเวกซ, ลล, เน, อหา, ประว, นตอนว, รห, สเท, ยม, ประส, ทธ, ภาพ, การนำไปใช, างอ, แหล, งข, อม, ลอ, นประว, แก, ไขม, อเร, ยกอ, กอย, างหน, งว, การเด, นแถวของจาร, . khntxnwithiaebbhxkhxngkhwy xngkvs Gift Wrapping Algorithm khuxwithiinthang erkhakhnitechingkhanwn thiichinkarkhanwnha khxnewkshll enuxha 1 prawti 2 khntxnwithi 3 rhsethiym 4 prasiththiphaph 5 karnaipich 6 xangxing 7 aehlngkhxmulxunprawti aekikhkhntxnwithiaebbhxkhxngkhwymichuxeriykxikxyanghnungwa karedinaethwkhxngcarwis xngkvs Jarvis March ephuxepnekiyrtiaek xar ex carwis phunakhntxnwithinixxkephyaephrinpi ph s 2516 hlngcak ornld ekraehm naesnxekraehmsaeknhnungpi khntxnwithi aekikh karichkhntxnwithikarhxkhxngkhwyinkarhakhxnewkshll erimcakih i 0 aelaih p0 khuxcudsudkhidcudhnung sungthrabaennxnwaxyubnkhxnewkshll echn cudbnsud caknn eluxkcud pi 1 ody pi 1 khuxcudthiihmumkwangthisudethiybkb Pi xacepnthisthwnekhmnalikahruxtamekhmnalikakid thasaechnniiperuxy cnkwacaid ph p0 khuxwnklbmacnkhrbcuderimtnnnexng 1 rhsethiym aekikhjarvis S rb S thiepnesthkhxngcud pointOnHull cudsudkhidcudhnung tngkha p0 dwycudsudkhidcudhnung i 0 erim i 0 repeat P i pointOnHull ephimkha pi lngipinxaerykhxngkhatxb P chxngthi i endpoint S 0 tngkhaerimtnsahrbkarhacudtxipbnkhxnewkshll for j from 1 to S 1 trwcsxbthukcud if pointOnHull angle S j gt pointOnHull angle endpoint endpoint S j thahakmumkhxngcudihmkwangkwaethiybkbcudedimthieluxkipinrxbkxn ihepliyncudthieluxkihm i i 1 pointOnHull endpoint tngkhacud pi 1 ihepncudhlksahrbrxbhna until endpoint P 0 thasacnkwacakhrbrxbprasiththiphaph aekikhenuxngcakewlainkarhamumsahrbaetlacudepnkhakhngthi O 1 aelakarepriybethiybmumsahrbthukkhucudcaichewla O n srupwaerasamarthhacudhnungbnkhxnewkshllidphayinewla O n aelahakmicudbnkhxnewkshllepncanwn h cudaelw srupidwakaredinaethwkhxngcarwiscasamarthhacudthukcudbnkhxnewkshllidphayinewla O nh karnaipich aekikhodypktiaelw karedinaethwkhxngcarwisnncasamarththanganiderwkwaekraehmsaekn odykrnithielwthisudkhuxkrnithithukcudxyubnkhxnewkshll echn rupwngklmxangxing aekikhJarvis R A 1973 On the identification of the convex hull of a finite set of points in the plane Information Processing Letters 2 18 21 doi 10 1016 0020 0190 73 90020 3 aehlngkhxmulxun aekikhkhntxnwithikarhxkhxngkhwyinradbtngaetsxngmitikhunip Archived 2011 09 27 thi ewyaebkaemchchin aebbcalxngkhxnewkshll khxmulephimetimcakmhawithyalyekhnthsetth rhsinphasa C http www chrisharrison net projects convexHull index html ekhathungcak https th wikipedia org w index php title khntxnwithiaebbhxkhxngkhwy amp oldid 9617485, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

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