การแนะนำอย่างอ่อนโยนเกี่ยวกับปัญหาตัวถังนูน

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

ตัวถังนูนคืออะไร?

โครงสร้างนูนของเซตจุดถูกกำหนดให้เป็นรูปหลายเหลี่ยมนูนที่เล็กที่สุด ซึ่งล้อมรอบจุดทั้งหมดในเซต นูนหมายความว่ารูปหลายเหลี่ยมไม่มีมุมที่โค้งงอเข้าด้านใน

ขอบสีแดงบนรูปหลายเหลี่ยมด้านขวาล้อมรอบมุมที่รูปร่าง เว้า ซึ่งอยู่ตรงข้ามกับนูน

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

เพื่อแสดงถึงผลลัพธ์ของตัวเรือนูนในโค้ด เรามักจะจัดเก็บรายการจุดที่ยึดหนังยางนี้ไว้ เช่น รายการของจุดบนตัวเรือแบบนูน

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

การหาส่วนนูนของตัวเรือ

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

ในการค้นหาส่วนนูนของชุดจุด เราสามารถใช้อัลกอริธึมที่เรียกว่า "Graham Scan" ซึ่งถือว่าเป็นหนึ่งในอัลกอริธึมแรกๆ ของเรขาคณิตเชิงคำนวณ เมื่อใช้อัลกอริธึมนี้ เราจะสามารถค้นหาเซตย่อยของจุดที่อยู่บนตัวเรือนูน พร้อมกับลำดับที่จุดเหล่านี้จะพบเมื่อเคลื่อนที่ไปรอบๆ ตัวเรือนูน

อัลกอริธึมเริ่มต้นด้วยการหาจุดที่เรารู้ว่าต้องนอนอยู่บนตัวเรือนูนอย่างแน่นอน เช่น จุดที่มีพิกัด y ต่ำสุดก็ถือว่าเป็นทางเลือกที่ปลอดภัย หากมีจุดหลายจุดที่พิกัด y เดียวกัน เราจะหาจุดที่มีพิกัด x ที่ใหญ่ที่สุด (ซึ่งใช้ได้กับจุดมุมอื่นๆ ด้วย เช่น จุดต่ำสุดจุดแรก x แล้วจึงต่ำสุด y ).

ต่อไป เราจะจัดเรียงจุดอื่นๆ ตามมุมที่จุดเหล่านั้นอยู่เมื่อมองจากจุดเริ่มต้น หากจุดสองจุดอยู่ในมุมเดียวกัน จุดที่ใกล้กับจุดเริ่มต้นควรเกิดขึ้นเร็วกว่าในการเรียงลำดับ

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

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

เราเก็บคะแนนซึ่งอยู่บนตัวเรือนูนไว้บนกอง ด้วยวิธีนี้เราจะสามารถเพิ่มคะแนนได้หากเราไปถึงจุดเหล่านั้นระหว่างทางรอบๆ จุดที่จัดเรียง และลบออกหากเราพบว่าจุดเหล่านั้นสร้างมุมเว้า

(พูดอย่างเคร่งครัด เราต้องเข้าถึงสองจุดบนสุดของสแต็ก ดังนั้นเราจึงใช้ std::vector แทน แต่เราคิดว่ามันเหมือนกับสแต็กประเภทหนึ่ง เพราะเรามักจะกังวลเพียงองค์ประกอบสองอันดับแรกเท่านั้น)

เมื่อพิจารณาอาร์เรย์ของจุดที่เรียงลำดับแล้ว เราจะเพิ่มจุดลงในสแต็ก และหากในภายหลังพบว่าจุดนั้นไม่ได้เป็นของตัวเรือที่นูน เราก็จะลบมันออก

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

ไปยังจุดถัดไป เราทำสิ่งเดียวกันต่อไป: ตรวจสอบว่ามุมนั้นนูนหรือไม่ และถ้าไม่ ให้เอาจุดนั้นออก จากนั้นไปเพิ่มจุดถัดไปและทำซ้ำ

มุมนี้ที่ทำเครื่องหมายด้วยสีแดงเป็นส่วนเว้า ดังนั้นเราจึงลบจุดกึ่งกลางออกจากปึกเนื่องจากไม่สามารถเป็นส่วนหนึ่งของตัวเรือที่นูนได้

เราจะรู้ได้อย่างไรว่าสิ่งนี้จะให้คำตอบที่ถูกต้องแก่เรา?

การเขียนหลักฐานที่เข้มงวดไม่อยู่ในขอบเขตของบทความนี้ แต่ฉันสามารถเขียนแนวคิดพื้นฐานได้ อย่างไรก็ตาม ฉันขอแนะนำให้คุณดำเนินการต่อและพยายามเติมเต็มช่องว่าง!

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

(จริงๆ แล้ว คุณต้องแสดงให้เห็นด้วยว่านี่คือ รูปหลายเหลี่ยมนูนที่เล็กที่สุดเท่าที่จะเป็นไปได้ ที่เป็นไปตามเงื่อนไขเหล่านี้ แต่ที่ตามหลังค่อนข้างง่ายจากจุดมุมของรูปหลายเหลี่ยมนูนของเราซึ่งเป็นเซตย่อยของเซตดั้งเดิมของ คะแนน)

สมมติว่ามีจุด P อยู่นอกรูปหลายเหลี่ยมที่เราเพิ่งพบ

เนื่องจากทุกจุดถูกเพิ่มลงในสแต็กหนึ่งครั้ง เราจึงรู้ว่า P ถูกลบออกจากสแต็ก ณ จุดใดจุดหนึ่ง ซึ่งหมายความว่า P พร้อมด้วยจุดใกล้เคียง เรียกพวกมันว่า O และ Q ทำให้เกิดมุมเว้า

เนื่องจาก O และ Q อยู่ภายในรูปหลายเหลี่ยม (หรือบนขอบของมัน) P จึงต้องอยู่ภายในเส้นขอบเช่นกัน เนื่องจากรูปหลายเหลี่ยม นูนออกมา และมุมที่รูปแบบ O และ Q ที่มี P เป็นเว้าสัมพันธ์กับรูปหลายเหลี่ยม

ดังนั้นเราจึงพบความขัดแย้ง ซึ่งหมายความว่าจุด P ดังกล่าวไม่มีอยู่จริง

การนำไปปฏิบัติ

การใช้งานที่ให้ไว้ที่นี่มีฟังก์ชัน convex_hull ซึ่งรับ std::vector ที่มีคะแนนเป็น std::pairs ของ ints และส่งคืน std::vector อีกอันที่มีคะแนนซึ่งอยู่บนตัวถังนูน

การวิเคราะห์รันไทม์และหน่วยความจำ

การคิดถึงอัลกอริธึมความซับซ้อนในแง่ของสัญลักษณ์ Big-O มีประโยชน์เสมอ ซึ่งฉันจะไม่อธิบายในที่นี้ เพราะ Michael Olorunnisola ที่นี่ทำหน้าที่อธิบายได้ดีกว่าที่ฉันจะทำอยู่แล้ว:

การเรียงลำดับคะแนนในตอนแรกจะใช้เวลา O(n log n) แต่หลังจากนั้น ทุกขั้นตอนสามารถคำนวณได้ในเวลาคงที่ ทุกจุดจะถูกเพิ่มและลบออกจากสแต็กได้มากที่สุดหนึ่งครั้ง ซึ่งหมายความว่ารันไทม์ที่แย่ที่สุดจะอยู่ใน O(n log n)

การใช้งานหน่วยความจำซึ่งอยู่ใน O(n) ในขณะนี้สามารถปรับให้เหมาะสมได้โดยการขจัดความจำเป็นในการใช้สแต็กและดำเนินการโดยตรงบนอาร์เรย์อินพุต เราสามารถย้ายจุดที่วางอยู่บนตัวถังนูนไปยังจุดเริ่มต้นของอาร์เรย์อินพุตและจัดเรียงตามลำดับที่ถูกต้อง และจุดอื่นๆ จะถูกย้ายไปยังส่วนที่เหลือของอาร์เรย์ ฟังก์ชันสามารถส่งคืนตัวแปรจำนวนเต็มเพียงตัวเดียวซึ่งแสดงถึงจำนวนจุดในอาร์เรย์ที่อยู่บนตัวเรือนูน แน่นอนว่าสิ่งนี้มีข้อเสียตรงที่ฟังก์ชันจะมีความซับซ้อนมากขึ้น ดังนั้นฉันจึงขอแนะนำไม่ให้ทำเช่นนี้ เว้นแต่ว่าคุณกำลังเขียนโค้ดสำหรับระบบฝังตัวหรือมีความกังวลเกี่ยวกับหน่วยความจำที่มีข้อจำกัดในทำนองเดียวกัน สำหรับสถานการณ์ส่วนใหญ่ การแลกเปลี่ยนความน่าจะเป็นของข้อบกพร่อง/การบันทึกหน่วยความจำนั้นไม่คุ้มค่า

อัลกอริทึมอื่นๆ

อีกทางเลือกหนึ่งสำหรับ Graham Scan คือ "อัลกอริทึมของ Chan" ซึ่งใช้แนวคิดเดียวกันอย่างมีประสิทธิผล แต่นำไปปฏิบัติได้ง่ายกว่า อันดับแรกควรทำความเข้าใจว่า Graham Scan ทำงานอย่างไร

หากคุณรู้สึกเพ้อฝันจริงๆ และต้องการจัดการกับปัญหาในแบบสามมิติ ลองดูอัลกอริทึมของ Preparata และ Hong ที่นำมาใช้ในรายงานปี 1977 เรื่อง “Convex Hulls of Finite Sets of Points in Two and Three Dimensions”