ระบบจินตทัศน์อัลกอริทึมของปัญหาทางด้านเรขาคณิตเชิงคำนวณ

Abstract

วิทยานิพนธ์ฉบับนี้ นำเสนอการออกแบบและการพัฒนาระบบจินตทัศน์อัลกอริทึม สำหรับปัญหาเรขาคณิตเชิงคำนวณในสองมิติสองปัญหาคือปัญหาเปลือกนูน และปัญหาการค้นหาในพิสัย ระบบนี้ได้รับการพัฒนาให้ใช้งานกับระบบ AVis ซึ่งเป็นระบบบริหารจินตทัศน์อัลกอริทึมที่ทำงานบนสภาพปฏิบัติการวินโดวส์ บทจินตทัศน์หนึ่งๆ ประกอบด้วยสี่กลุ่มขององค์ประกอบ คือ ส่วนอัลกอริทึม ส่วนสร้างข้อมูล ส่วนแสดงผล และส่วนแปลงคำสั่ง ระบบนี้มีส่วนอัลกอริทึมหกส่วน เพื่อการจินตทัศน์ปัญหาเปลือกนูน ได้แก่ อัลกอริทึมแบบห่อของขวัญของ Javis อัลกอริทึมแบบกราดตรวจของ Graham อัลกอริทึมแบบค่อยๆ เพิ่มจุด อัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ อัลกอริทึมการหาเปลือกนูนแบบเร็ว อัลกอริทึมแบบกำจัด และส่วนอัลกอริทึมอีกสี่ส่วนสำหรับปัญหาการค้นหาในพิสัย ได้แก่ การค้นหาแบบลำดับ การค้นหาด้วยวิธีกริด การค้นหาโดยใช้ต้นไม้สองมิติ การค้นหาโดยใช้ต้นไม้สองมิติที่มีแกนที่ใช้เป็นคีย์เป็นตัวเลขสุ่ม และการค้นหาโดยใช้ต้นไม้มัธยฐาน ข้อมูลขาเข้าของอัลกอริทึมถูกสร้างทั้งแบบสุ่ม แบบสร้างขึ้นเอง และแบบอ่านจากแฟ้มข้อมูลโดยใช้ส่วนสร้างข้อมูล ระบบมีส่วนแสดงผลสองส่วน คือ การแสดงจุดบนระนาบ และการแสดงกราฟเส้น เพื่อการจินตทัศน์อัลกอริทึมการหาเปลือกนูน และมีส่วนแสดงผลอีกส่วนที่แสดงจุดและต้นไม้ เพื่อการจินตทัศน์อัลกอริทึมการค้นหาในพิสัย นอกจากนี้ยังมีส่วนแปลงคำสั่งอีกจำนวนหนึ่งที่ทำงานหน้าที่รับเหตุการณ์จากส่วนอัลกอริทึมเพื่อแปลงเป็นคำสั่งการสร้างภาพของส่วนแสดงผล ระบบนี้เหมาะสำหรับใช้เพื่อการศึกษาพฤติกรรมของอัลกอริทึมต่างๆ ข้างต้น เมื่อมีการเปลี่ยนแปลงลักษณะของข้อมูลขาเข้า และเป็นระบบที่ได้รับการพัฒนา เพื่อเป็นต้นแบบในการพัฒนาการจินตทัศน์ปัญหาเรขาคณิตเชิงคำนวณอื่นๆ ต่อไป