Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ขั้นตอนวิธีแบบห่อของขวัญ (อังกฤษ: 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". . 2: 18–21. doi:10.1016/0020-0190(73)90020-3.
แหล่งข้อมูลอื่น
- ขั้นตอนวิธีการห่อของขวัญในระดับตั้งแต่สองมิติขึ้นไป เก็บถาวร 2011-09-27 ที่ เวย์แบ็กแมชชีน
- แบบจำลองคอนเวกซ์ฮัลล์ เก็บถาวร 2007-06-09 ที่ เวย์แบ็กแมชชีน
- ข้อมูลเพิ่มเติมจากมหาวิทยาลัยเคนท์สเตท
- รหัสในภาษา C++
- http://www.chrisharrison.net/projects/convexHull/index.html
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
khntxnwithiaebbhxkhxngkhwy xngkvs Gift Wrapping Algorithm khuxwithiinthang thiichinkarkhanwnhaprawtikhntxnwithiaebbhxkhxngkhwymichuxeriykxikxyanghnungwa karedinaethwkhxngcarwis xngkvs Jarvis March ephuxepnekiyrtiaek xar ex carwis phunakhntxnwithinixxkephyaephrinpi ph s 2516 hlngcak naesnxekraehmsaeknhnungpi khntxnwithikarichkhntxnwithikarhxkhxngkhwyinkarhakhxnewkshll 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 rhsethiymjarvis 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 thasacnkwacakhrbrxbprasiththiphaphenuxngcakewlainkarhamumsahrbaetlacudepnkhakhngthi O 1 aelakarepriybethiybmumsahrbthukkhucudcaichewla O n srupwaerasamarthhacudhnungbnkhxnewkshllidphayinewla O n aelahakmicudbnkhxnewkshllepncanwn h cudaelw srupidwakaredinaethwkhxngcarwiscasamarthhacudthukcudbnkhxnewkshllidphayinewla O nh karnaipichodypktiaelw karedinaethwkhxngcarwisnncasamarththanganiderwkwaekraehmsaekn odykrnithielwthisudkhuxkrnithithukcudxyubnkhxnewkshll echn rupwngklmxangxingJarvis R A 1973 On the identification of the convex hull of a finite set of points in the plane 2 18 21 doi 10 1016 0020 0190 73 90020 3 aehlngkhxmulxunkhntxnwithikarhxkhxngkhwyinradbtngaetsxngmitikhunip ekbthawr 2011 09 27 thi ewyaebkaemchchin aebbcalxngkhxnewkshll ekbthawr 2007 06 09 thi ewyaebkaemchchin khxmulephimetimcakmhawithyalyekhnthsetth rhsinphasa C http www chrisharrison net projects convexHull index html