Chulalongkorn University Theses and Dissertations (Chula ETD)

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

Other Title (Parallel Title in Other Language of ETD)

Algorithm visualization for computational geometry problems

Year (A.D.)

1997

Document Type

Thesis

First Advisor

สมชาย ประสิทธิ์จูตระกูล

Faculty/College

Graduate School (บัณฑิตวิทยาลัย)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.1997.780

Abstract

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

Other Abstract (Other language abstract of ETD)

This thesis presents a design and development of an algorithm visualization for two 2D computational geometry problems; convex hull and range search problems. The system was developed to be used in AVis, an algorithm visualization management running on MS Windows operating environment. Each visualization session consists of four classes of components; algorithms, data generators, views and converters. There are six algorithm components for visualizing the convex hull problem; Javis's march, Graham's scan incremental, divide-and-conquer, quick hull, and "throw-away" algorithms, and the other four algorithm components for the range search problem; brute force, grid method, 2D tree, 2D tree with randomized discriminator, and median tree algorithms. Input data can be randomly generated, manually created, or read from a data file using a data generator component. Two views, point-in-the-plane and line graph views, are provided for visualizing the convex hull algorithms, and another point-and-tree view are used for the range search algorithms. In addition, there are a number of converters used for converting events from the algorithm components to graphic commands in the view components. The system is well suited for studying behaviours of the algorithms when varying input parameters and was developed as a prototype for further development in visualizing more computational geometry problems.

Link to Full Text

Share

COinS