Quickhullเป็นวิธีการคำนวณส่วนนูนของเซตจุดจำกัดใน ปริภูมิ nมิติ โดยใช้ แนวทาง แบ่งและพิชิตคล้ายกับquicksortซึ่งเป็นที่มาของชื่อ ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดสำหรับปริภูมิ 2 มิติและ 3 มิติคือแต่เมื่อความแม่นยำของอินพุตถูกจำกัดไว้ที่บิต ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดคาดว่าจะเป็นโดยที่คือจำนวนจุดอินพุตและคือจำนวนจุดที่ประมวลผล (สูงสุด) ^{[ 1 ]}${\displaystyle O(n^{2})}$${\displaystyle O(\log n)}$${\displaystyle O(n\log r)}$${\displaystyle n}$${\displaystyle r}$${\displaystyle n}$

N-dimensional Quickhull ถูกคิดค้นขึ้นในปี 1996 โดย C. Bradford Barber, David P. Dobkinและ Hannu Huhdanpaa ^{[ 1 ]}มันเป็นส่วนขยายของอัลกอริทึม Quickhull แบบระนาบของ Jonathan Scott Greenfield ในปี 1990 แม้ว่าผู้เขียนในปี 1996 จะไม่รู้จักวิธีการของเขา^{[ 2 ]}แต่ Barber และคณะอธิบายว่าเป็นรูปแบบเชิงกำหนดของอัลกอริทึมของ Clarkson และ Shor ในปี 1989 ^{[ 1 ]}

อัลกอริทึม 2 มิติสามารถแบ่งออกเป็นขั้นตอนต่อไปนี้: ^{[ 2 ]}

1. จงหาจุดที่มีพิกัด x ต่ำสุดและสูงสุด เนื่องจากจุดเหล่านี้จะเป็นส่วนหนึ่งของขอบนูนเสมอ หากมีจุดหลายจุดที่มีค่า x ต่ำสุด/สูงสุดเท่ากัน ให้ใช้จุดที่มีค่า y ต่ำสุด/สูงสุด ตามลำดับ
2. ใช้เส้นตรงที่ลากผ่านจุดสองจุดนั้นแบ่งเซตออกเป็นสองเซตย่อย ซึ่งจะถูกประมวลผลแบบเรียกซ้ำ ต่อไปเราจะอธิบายวิธีการหาบริเวณของตัวเรือที่อยู่เหนือเส้นตรง ส่วนของตัวเรือที่อยู่ใต้เส้นตรงสามารถหาได้ในทำนองเดียวกัน
3. จงหาจุดที่อยู่เหนือเส้นตรงซึ่งมีระยะห่างจากเส้นตรงมากที่สุด จุดนี้จะก่อให้เกิดรูปสามเหลี่ยมกับจุดสองจุดบนเส้นตรง
4. จุดที่อยู่ภายในสามเหลี่ยมนั้นไม่สามารถเป็นส่วนหนึ่งของรูปทรงนูนได้ ดังนั้นจึงสามารถละเลยได้ในขั้นตอนต่อไป
5. ทำซ้ำขั้นตอนสองขั้นตอนก่อนหน้าแบบเรียกซ้ำบนเส้นสองเส้นที่เกิดจากด้านใหม่สองด้านของสามเหลี่ยม
6. ดำเนินการต่อไปจนกว่าจะไม่มีจุดเหลืออยู่ การเรียกซ้ำจะสิ้นสุดลง และจุดที่เลือกไว้จะประกอบกันเป็นรูปทรงนูน (convex hull)

ปัญหาจะซับซ้อนมากขึ้นในกรณีมิติที่สูงกว่า เนื่องจากตัวเรือสร้างจากเหลี่ยมมุมจำนวนมาก โครงสร้างข้อมูลจำเป็นต้องคำนึงถึงสิ่งนั้นและบันทึกเส้น/ระนาบ/ไฮเปอร์เพลน (สัน) ที่ใช้ร่วมกันโดยเหลี่ยมมุมที่อยู่ติดกันด้วย สำหรับ มิติ d : ^{[ 1 ]}

1. เลือกจุดd + 1 จุดจากเซตที่ไม่แชร์ระนาบหรือไฮเปอร์เพลนซึ่งจะสร้างโครงร่างเริ่มต้นที่มีเหลี่ยมมุมFs[ ]
2. สำหรับแต่ละFในFs[]ให้ค้นหาจุดที่ยังไม่ได้กำหนดทั้งหมดที่อยู่ "เหนือ" F นั้น กล่าวคือ ชี้ออกไปจากจุดศูนย์กลางของโครงร่าง และกำหนดจุดเหล่านั้นให้กับเซต "ภายนอก" FOที่เกี่ยวข้องกับF นั้นอัลกอริทึมนี้รักษาคุณสมบัติคงที่ที่ว่าทุกจุดที่ยังไม่ได้ถูกเพิ่มเข้าไปในโครงร่าง แต่มีศักยภาพที่จะเป็นจุดยอดของโครงร่างนั้น จะถูกกำหนดให้กับเซตภายนอกเพียงเซตเดียวเท่านั้น
3. สำหรับแต่ละF ที่มี FOที่ไม่ว่างเปล่า:
   1. หาจุดpในFO ที่มีระยะห่างจาก Fมากที่สุดแล้วเพิ่มจุด p นั้นเข้าไปในโครงสร้างรูปทรงครึ่งวงกลม (hull) โปรดทราบว่าpไม่จำเป็นต้องเป็นจุดยอดของโครงสร้างรูปทรงครึ่งวงกลมสุดท้ายเสมอไป เพราะอาจถูกลบออกในภายหลังได้
   2. สร้างเซตที่มองเห็นได้Vและกำหนดค่าเริ่มต้นเป็นFขยายVไปในทุกทิศทางสำหรับระนาบข้างเคียงFvจนกว่าจะไม่มีระนาบใดมองเห็นได้จากp อีกต่อ ไป การที่ Fvมองเห็นได้จากpหมายความว่าpอยู่เหนือFv
   3. ขอบเขตของVจะก่อให้เกิดแนวสันขอบฟ้าHขึ้น มา
   4. ให้Fnew[]เป็นเซตของเหลี่ยมมุมที่สร้างขึ้นจากpและสันทั้งหมดในH
   5. ยกเลิกการกำหนดจุดทั้งหมดในเซตภายนอกของเหลี่ยมมุมในVสำหรับแต่ละเหลี่ยมมุมใหม่ในFnew[]ให้ดำเนินการขั้นตอน (2) โดยพิจารณาเฉพาะจุดที่ยังไม่ได้กำหนดใหม่เหล่านี้เพื่อเริ่มต้นเซตภายนอก โปรดทราบว่าทุกจุดที่ยังคงไม่ได้กำหนดเมื่อสิ้นสุดกระบวนการนี้จะอยู่ภายในขอบเขตปัจจุบัน
   6. ลบ facet ภายในในV ออก จากFs[]เพิ่ม facet ใหม่ในFnew[]ลงในFs[]และดำเนินการวนซ้ำต่อไป

อินพุต = เซต S ของจุด n จุด สมมติว่ามีจุดอย่างน้อย 2 จุดในชุดจุด S ที่ป้อนเข้ามา ฟังก์ชัน QuickHull( S ) คือ// ค้นหาขอบนูนจากเซต S ของจุด n จุด Convex Hull := {} หาจุดซ้ายสุดและขวาสุด สมมติว่าเป็น A และ B แล้วบวก A และ B เข้ากับรูปทรงนูน ส่วน AB แบ่งจุดที่เหลือ ( n − 2) จุดออกเป็น 2 กลุ่มS1และS2 โดยที่S1คือจุดในSที่อยู่ทางด้านขวาของเส้นตรงที่กำหนดทิศทางจากAไปB และS2เป็นจุดในSที่อยู่ทางด้านขวาของเส้นตรงที่กำหนดทิศทางจากBไปยังA FindHull( S1 , A , B ) FindHull( S2 , B , A ) เอาต์พุต := นูน ฟังก์ชันสิ้นสุดฟังก์ชัน FindHull( Sk , P , Q ) คือ// ค้นหาจุดบนขอบนูนจากเซตจุด Sk // ที่อยู่ทางด้านขวาของเส้นตรงที่กำหนดทิศทางจาก P ไปยัง Q ถ้าSkไม่มีจุดให้ส่งคืนค่าว่าง จากเซตจุดที่กำหนดในSkให้หาจุดที่อยู่ไกลที่สุด สมมติว่าเป็นจุดCจากส่วนของเส้นตรงPQ เพิ่มจุดCลงในขอบนูน ณ ตำแหน่งระหว่างPและQ จุดสามจุดP , QและCแบ่งจุดที่เหลือของSkออกเป็น 3 เซตย่อย: S0 , S1และS2 โดยที่S0คือจุดที่อยู่ภายในสามเหลี่ยม PCQ และS1คือจุดที่อยู่ทางด้านขวาของเส้นตรงที่กำหนดทิศทางS1 เป็นจุดที่ อยู่ทางด้านขวาของเส้นตรงที่กำหนดทิศทาง จากCไปยังQ FindHull( S1 , P , C ) FindHull( S2 , C , Q ) end function

รหัสเทียมที่ออกแบบมาสำหรับกรณี 3 มิติโดยเฉพาะมีให้จาก Jordan Smith ซึ่งรวมถึงกลยุทธ์ "จุดสูงสุด" ที่คล้ายกันสำหรับการเลือกโครงร่างเริ่มต้น หากจุดสูงสุดเหล่านี้เสื่อมสภาพกลุ่มจุด ทั้งหมด ก็จะเสื่อมสภาพเช่นกัน^{[ 3 ]}

• อัลกอริทึม Convex hull

• การนำ QuickHull ไปใช้งาน (GDC 2014) – การนำเสนออัลกอริทึมพร้อมรายละเอียดการใช้งานในรูปแบบ 3 มิติ