本論文採用Delaunay三角切割法製作二維和三維網格產生器，目的在製作前端處理部份，並將節點資料提供給數值計算，以得到較佳的結果。
此程式於視窗環境下執行。在此容易操作的環境下，使用者可以製作複雜的電路﹝含挖洞結構﹞，並且可以加些限制﹝例如：每邊的最大長度、三角形不得小於的角度﹞以達到細切的目的。二維結構直接於此環境下顯示結果，三維結構使用Matlab軟體顯示。

In this thesis, we adopt Delaunay triangulation method to design a two and three dimensional mesh generator. Our goal is to produce node data in the pre-processor and we wish to get better result from numerical calculation.
Our program is easy to manipulate in Windows environment. User can design complex circuit (include digging hole) and refine the area by adding some constraints on edge size and minimum angle. We directly display the two dimensional structure on our Windows environment and use Matlab tool to display the three dimensional structure.

ABSTRACT(Chinese)………………………………………………………….i
ABSTRACT(English).……………………………………………………….ii
ACKNOWLEDGEMENTS…………………………………………………………iii
TABLE OF CONTENTS………………………………………………………..iv
LIST OF FIGURES.………………………………………………………….vi
LIST OF TABLE……………………………………………………………viii
CHAPTER 1 Introduction……………………………………………………1
1.1 Introduction……………………………………………………………1
1.2Organization of This Thesis…………………………………………5
CHAPTER 2 Traditional Delaunay Triangulation………………………6
2.1 Outline of The Delaunay Method……………………………….8
2.2 General Initial Mesh Method……………………………………10
2.3 General Mesh Refinement…………………………………………13
CHAPTER 3 Efficient Delaunay Method………………………………….15
3.1 Flowchart of Delaunay Triangulation Method……………….15
3.2 Divide and Conquer Method………………………………………17
3.3 Ruppert’s Delaunay Refinement Algorithm………………….24
3.4 Three Dimensional Structure……………………...………….28
3.5 Dig Hole…………………………………………………………….30
CHAPTER 4 Interface Development……………………………………….31
4.1 Input Parameters in Graphic User Interface Environment.31
4.2 Output File Format……………………………………………….42
CHAPTER 5 Conclusion………………………………………………………47
REFERENCE…………………………………………………………………….48
APPENDIX………………………………………………………………………50

[1] E. B. Becker, G. F. Carey and J. T. Oden, Finite Elements An Introduction Volume I, Prentice Hall, 1981.
[2] P. G. Ciarlet and J. L. Lions, Automatic Mesh Generation Application to Finite Element Methods, Wiley Editorial Offices, 1991.
[3] S. Ratnajeevan H. Hoole, Computer-Aided Analysis and Design of Electromagnetic Devices, Elsevier, 1989.
[4] F. P. Preparata and M. L. Shamos, Computational Geometry An Introduction, Springer-Verlag, 1985.
[5] D. T. Lee and B. J. Schachter, “Two Algorithms for Constructing a Delaunay Triangulation,” Internal Journal of Computer and Information Sciences, vol 3,pp.219-242, 1980.
[6] Y. Lu and W. W. Dai, ”A Number Stable Algorithm for Constructing Constrained Delaunay Triangulation and Application to Multichip Module Layout,” International Conference on Circuits and Systems, June 1991.
[7] J. F. Lee and R. D. Romanus, ”Automatic Mesh Generation Using a Modified Delaunay Tessellation,” IEEE Antennas and Propagation Magazine, Vol. 39, No. 1, February 1997.
[8] Rex A. Dwyer, “A Faster Divide-and-Conquer Algorithm for Constructing Delaunay Triangulations,” Algorithmica, vol. 2,no. 2,pp. 137-151,1987.
[9] J. R. Shewchuk, ”Triangle:Engineering a 2D Quality Mesh Generator and Delaunay Triangulator,” First Workshop on Applied Computational Geometry, pp. 124-133, ACM, May 1996.
[10] J. Ruppert, “A Delaunay Refinement Mesh Generation,” Journal of Algorithms, vol.18 no. 3, pp.548-585, May 1995.
[11] L. P. Chew, “Constrained Delaunay Triangulation,” Algorithmica, vol.4, pp.97-108, 1989.
[12] J. S. Young, “Adjacency for Grid Generation and Grid Adaptation in Delaunay Traingulation,” Comput. Methods Appl. Mech. Engrg., vol. 150, pp. 57-64, 1997.
[13] Y. C. Zhang, J. J. Yin and L. Luo, “ A Two-dimensional Mesh Generator with Boundary Conditions Generation,” Computers & Structures, vol. 46, no. 1, pp. 175-181, 1993.
[14] J. C. Tipper, “Fortran Programs to Construct the Planar Voronoi Diagram,” Computers & Geosciences, vol. 17, no. 5, pp. 597-632, 1991.
[15] T. Lambert, “An Optimal Algorithm for Realizing a Delaunay Triangulation,” Information Processing Letters, vol. 62, pp. 245-250, 1997.
[16] P. Su, R. L. S. Drysdale, “A Comparison of Sequential Delaunay Triangulation Algorithms,” Computational Geometry, vol. 7, pp. 361-385, 1997.