ขั้นตอนวิธีแบบกรวย

ขั้นตอนวิธีแบบกรวย (อังกฤษ: Cone Algorithm) เป็นขั้นตอนวิธีที่รวดเร็ว ซึ่งสามารถระบุได้อย่างแม่นยำว่าอนุภาคใดบ้างที่อยู่บนพื้นผิวที่มีลักษณะเป็นก้อนเล็กๆ ใน 3 มิติ จากการคำนวณโดยทั่วไปทางเรขาคณิต แสดงให้เห็นว่าขั้นตอนวิธีแบบนี้มีประโยชน์อย่างยิ่งกับวิทยาศาสตร์ที่ที่มีคำนวณหาพื้นที่ผิว และวิทยาศาสตร์ที่ศึกษาเกี่ยวกับเรื่องของนาโนเทคโนโลยี สำหรับกลุ่มก้อนสามมิติที่ให้มาในรูปด้านขวามือ ซึ่งประกอบด้วยชุดของอนุภาค เราจะบอกได้อย่างไรว่าอนุภาคใดบ้างอยู่บนพื้นผิว? เหมือนจะง่ายถ้ามองจากตาของมนุษย์ เกณฑ์การมองเห็นอาจถูกอธิบายได้ เช่นถ้าเรากำหนดว่า อนุภาคจะอยู่บนพื้นผิวได้ก็ต่อเมื่ออนุภาคนั้นไม่ได้ถูกล้อมรอบด้วยอนุภาคอื่นๆ ทุกทิศทาง หรือ เราจะบอกว่ามันเป็นอนุภาคพื้นผิวถ้ามันไม่ถูกฝั่งลงไปในของกลุ่มก้อนนั้น เกณฑ์เหล่านี้ทำให้เราสามารถตัดสินใจว่ามันเป็นอนุภาคพื้นผิวหรือไม่ แต่เพื่อที่จะบอกคอมพิวเตอร์ให้เก็บข้อมูลของอนุภาคที่อยู่พื้นผิว เช่นตำแหน่งของอนุภาคเหล่านั้น เราก็ใช้หลักการที่จะอธิบายเหมือนกับหลักเกณฑ์ที่กล่าวมาก่อนหน้านี้ จุดหลายจุดที่เห็นในภาพด้านขวามือนั้นจะอยู่ในอนุภาค ซึ่งอนุภาคจะติดต่อกับอาณาเขตรูปกรวย ขอบเขตรูปกรวยนี้ถูกกำหนดขนาดพื้นที่ด้วยความยาว และมุมของมัน และเราเรียกอาณาเขตรูปกรวยที่ไม่มีอนุภาคใดๆ อยู่ภายในว่า "กรวยกลวง" (hollow cone) เรากำหนดให้อนุภาคอยู่บนพื้นผิวถ้าจุดอย่างน้อยหนึ่งจุดบนอนุภาคติดต่อกับกรวยกลวง สำหรับกรวย เรามีตัวแปรที่เปลี่ยนแปลงได้ 2 ตัว คือ ความยาวของกรวย และขนาดของมุมกรวย ผลลัพธ์ที่แม่นยำหรือผลลัพธ์ที่น่าพอใจจะเกิดขึ้นได้ก็ขึ้นอยู่กับตัวแปร 2 ตัวนี้ ขั้นตอนวิธีแบบนี้สามารถปรับใช้ได้อย่างรวดเร็วกับสถานการณ์ที่มีโมเลกุลหลายโมเลกุลในโครงสร้าง หรือสถานการณ์ที่โมเลกุลนั้นมีรูอยู่ภายใน ใช้วิธีการดัชนีเซลล์เพื่อเร่งให้เห็นอนุภาคข้างเคียง ความยาวด้านข้างของเซลล์กว้างกว่าความยาวด้านข้างของกรวยเล็กน้อย ซึ่งความยาวที่แตกต่างกันนี้จะถูกสังเกตและตัดออกไปในภายหลัง และอนุภาคข้างเคียงจะถูกระบุให้อยู่ภายในระยะที่ถูกตัดออกไปนั้น ในการที่จะดูว่าอนุภาคที่เราสนใจมีกรวยกลวงหรือไม่ เราจะวนหาค่าผลรวมของอนุภาคข้างเคียง 3 อนุภาค เพื่อหาว่ามีอนุภาคข้างเคียงอื่นอยู่อีกหรือไม่ ผลรวมเชิงสเกล่าร์ของเวกเตอร์ที่เชื่อมต่อกับอนุภาคต่างๆ เหล่านี้ถูกใช้ในการพิจารณาว่าถ้าอาณาเขตรูปกรวยขยายไป 3 ช่วงอนุภาคแล้ว จะมีพื้นที่กว้างพอที่จะใส่ตัวแปร 2 ตัวหรือไม่ และมีอนุภาคอื่นอยู่ในอาณาเขตเขตรูปกรวยหรือไม่ ในการที่จะหาอนุภาคพื้นผิว ก็เพียงแค่หาอนุภาคที่มีกรวยกลวงอยู่ แม้จะมีกรวยกลวงเพียงอันเดียวก็จะถือว่าเป็นอนุภาคพื้นผิว และการวนเพื่อหาคำตอบจะสิ้นสุดลง ในทางกลับกันเพื่อที่จะหาอนุภาคภายในพื้นผิวจำเป็นต้องค้นหาทุกๆ ค่าผลรวมของอนุภาคข้างเคียง 3 อนุภาค เพื่อที่จะยืนยันว่าไม่มีกรวยกลวงอยู่จริงๆ แม้วิธีการง่ายๆ นี้จะเสร็จสมบูรณ์แต่เวลานั้นถูกใช้จนหมด ดังนั้นด้านล่างนี้จะกล่าวถึงวิธีอื่นๆ ที่ทำให้ความเร็วในการคำนวณของโปรแกรมดีขึ้นอย่างเห็นได้ชัด เพื่อจะลดเวลาการทำงานไม่ให้เวลาถูกใช้จนหมดไป การเรียกใช้ขั้นตอนวิธีแบบกรวยหลายๆ ครั้งทำให้เกิดชั้นของพื้นผิวย่อยๆ ที่แตกต่างกันหลายชั้น โปรแกรมภาษาซีนั้นเป็นโปรแกรมที่ง่ายสำหรับการวิเคราะห์ชั้นพื้นผิวย่อยเหล่านี้ ซึ่งเกิดอยู่ในก้อนสีทองรูปหกเหลี่ยม (icosahedral gold cluster) ที่ประกอบด้วยอะตอม 2,624 อะตอม รูปนี้แสดงให้เห็นถึงชั้นย่อยของพื้นผิวในก้อนหกเหลี่ยม (แต่ละอะตอมในก้อนหกเหลี่ยมนี้เป็นอะตอมสีทองเหมือนกัน แต่ถูกระบายสีที่ต่างกันตามชั้นที่พวกมันสังกัดอยู่ ) แม้ว่าภาษาซี (ซึ่งมีโครงสร้างภาษาแบบเชิงวัตถุ) จะเป็นภาษาที่เหมาะจะใช้เขียนขั้นตอนวิธีแบบนี้ แต่การโปรแกรมนั้นสามารถใช้กับโครงสร้างภาษาได้หลากหลายมากกว่าโครงสร้างแบบเชิงวัตถุอย่างเดียวการเขียนโปรแกรมควรจะสามารถใชักับข้อมูลขาเข้าและขาออกที่มีมาตรฐานตั้งแต่น้อยๆไปจนมีมาตรฐานมากๆได้ source code ของโปรแกรมควรจะอ่านง่าย และควรจะคอมเมนต์ที่เพียงพอเพื่อที่จะทำให้อ่านเข้าใจ //-------------------------- function cone--------------------------- // Check if a given particle np is in the cone region centered at particle p // with center vector of (nx,ny,nz) and cone angle theta // with cos(theta)=cosine. Cone center vector must be normalized. // Return 0 if the particle is not inside the region(s), 1 if in the cone // region, -1 if in the inverse cone region.