เปลือกนูน (Convex Hull)
เปลือกนูนของเซตของจุด
เกี่ยวกับเครื่องคำนวณนี้
เครื่องคำนวณเปลือกนูนหารูปหลายเหลี่ยมนูนที่เล็กที่สุดที่ล้อมรอบชุดจุดใน 2 มิติ โดยใช้ขั้นตอนวิธี monotone chain ของแอนดรูว์ แสดงจุดยอดที่มุมของเปลือกเรียงตามทิศทวนเข็มนาฬิกา นับจำนวนจุดที่อยู่บนเปลือกเทียบกับจุดที่อยู่ข้างใน และแสดงพื้นที่และเส้นรอบรูปที่แม่นตรง พร้อมแผนภาพการกระจายที่วาดขอบผลลัพธ์ จัดการจุดซ้ำและจุดบนเส้นตรงเดียวกันได้ถูกต้อง
วิธีหาเปลือกนูน
- ป้อนจุดเป็นคู่ x,y คั่นด้วยจุลภาค ลำดับไม่มีผล
- เครื่องคำนวณรวมจุดซ้ำและเรียงจุดจากซ้ายไปขวา
- จากนั้นกวาดจุดที่เรียงแล้วเพื่อสร้างขอบล่างและขอบบน โดยเก็บเฉพาะจุดยอดที่มุมซึ่งเส้นขอบเลี้ยวซ้าย
- อ่านจุดยอดของเปลือก พื้นที่ และเส้นรอบรูป และดูเส้นขอบที่วาดทับจุดของคุณ
ตัวอย่างที่พบบ่อย
- มุมสี่เหลี่ยม 0,0 6,0 6,4 0,4 และจุดภายใน 3,2 และ 2,1 → จุดยอดของเปลือก 4 จุด พื้นที่ 24 เส้นรอบรูป 20
- สามเหลี่ยม 0,0 4,0 0,3 → จุดยอดของเปลือก 3 จุด พื้นที่ 6 เส้นรอบรูป 12
- จุดบนเส้นตรงเดียวกัน 0,0 1,1 2,2 3,3 → เปลือกเสื่อม (ส่วนของเส้นตรง) พื้นที่ 0
- สี่เหลี่ยมจัตุรัส 0,0 4,0 4,4 0,4 และจุดยอด 2,5 → จุดยอดของเปลือก 5 จุด เพราะยอดแหลมยื่นขอบบนออกไป
คำถามที่พบบ่อย
เปลือกนูนคืออะไร?
เปลือกนูนของชุดจุดคือรูปหลายเหลี่ยมนูนที่เล็กที่สุดที่บรรจุจุดทั้งหมดไว้ เหมือนการขึงหนังยางรอบจุดที่อยู่นอกสุดแล้วปล่อยให้หดแนบ
จุดใดบ้างที่เป็นจุดยอดของเปลือก?
มีเพียงจุดมุมที่อยู่สุดขอบเท่านั้นที่อยู่บนเปลือก จุดที่อยู่ภายในรูปอย่างแท้จริง และจุดที่อยู่บนขอบของเปลือกพอดี จะไม่แสดงเป็นจุดยอด
จัดการจุดซ้ำหรือจุดบนเส้นตรงเดียวกันอย่างไร?
จุดที่เหมือนกันจะถูกรวมก่อน หากจุดทั้งหมดอยู่บนเส้นตรงเส้นเดียว เปลือกจะยุบเป็นส่วนของเส้นตรงที่มีพื้นที่เป็นศูนย์ ซึ่งเครื่องคำนวณจะแสดงว่าเป็นเปลือกเสื่อม
ต้องใช้จุดกี่จุด?
ต้องมีจุดที่แตกต่างกันและไม่อยู่บนเส้นตรงเดียวกันอย่างน้อยสามจุด จึงจะสร้างเปลือกที่มีพื้นที่เป็นบวกได้