臺灣博碩士論文加值系統

良好的幾何限制(Geometric Constraint)條件可以有效減少設計變更所花費的時間，所以對幾何物件自動設定適當的幾何限制條件，是近來電腦輔助幾何設計(CAGD)發展的趨勢之一。
在本文中，研究者擴充幾何限制求變動圓相切之問題，擴充能處理的幾何物件，將貝氏曲線(Bezier Curve)納入考量，以解決二個主要的問題，第一部份是求變動圓(變動圓心和變動半徑)同時和三個不同的幾何物件(線、圓或貝氏曲線)相切之問題；第二部份則是擴充實體合併問題(Cluster Merge Problem)。
針對第一部份的問題，由於貝氏曲線並無隱函式，造成求解的困難度，所以本文先在Volume Space中建構貝氏曲線的Cyclographic Maps，之後在Volume Space中找出三個不同的幾何物件(線、圓或貝氏曲線)之Cyclographic Maps相交之交點(Voxel)並轉換至Geometric Space中，最後利用數值方法(如牛頓法)來重新定義變動圓之圓心(x, y)和半徑z同時和三個不同的幾何物件(線、圓或貝氏曲線)相切。
針對第二部份的問題，我們擴充實體合併問題(Cluster Merge Problem) ，將原本僅處理線或圓的幾何物件，擴充至能處理貝氏曲線，先將二個實體(rigid)做連接，在連接過程中允許其中一個實體做平移或旋轉，之後在Volume Space中找出經平移或旋轉後二個實體(rigid)的Cyclographic Maps相交之交點(Voxel)並轉換至Geometric Space中，最後利用數值方法(如牛頓法)來重新定義變動圓之圓心(x, y)和半徑z同時與二個實體中個別含著二個幾何物件(點、線、圓或貝氏曲線)相切之解。

Informally, a geometric constraint problem consists of a (finite) set of geometric objects and a (finite) set of constraints between them. The geometric objects are drawn from a fixed universe such as point, lines, circles and conics in the plane. The constraints are logical constraints such as incidence, tangency, perpendicularity, etc., or metric constraints such as distance or angle.
There are two problems we want to solve in this work. The first problem is to find the variable radius circle tangents to 3 geometric objects, such as point, line, circle, and Bezier curve. The second problem is to solve the cluster merge problem whose geometric objects are point, circle, line, and Bezier Curve.
For solving first problem, the cyclographic for the geometric objects (points, circle, line, and Bezier curve) has to be surveyed. Based on the fact that the cyclographic maps of Bezier curve have no implicit form, the approximation for the maps should be constructed. After we construct the cyclographic maps for 3 geometric objects, and find their intersection points (x,y,z), we find the variable radius circle centered at (x,y) with radius z, tangent to those 3 geometric objects.
For the second problem, we extend the cluster merge problem to the problem containing Bezier curve as the basic geometric objects. There are two constraints between the variable radius circle and each of the rigid geometric objects. We find the intersection points for 2 fixed geometric objects and 2 translational/rotational geometric objects. Next, we convert the voxel location (in volume space) back to point location (in geometric space). Finally we refine the variable radius circle centered at (x,y) with radius z, tangent to each of the rigid geometric objects.

誌謝 i
摘要 iii
Abstract iv
目錄 v
表目錄 vi
圖目錄 vii
1. 緒論 1
2. 文獻探討 3
2.1 幾何限制相關之研究 3
2.1.1 Planner Constraint Solving 3
2.1.2 Spatial Constraint Solving 4
2.2 實體合併問題(Cluster Merge Problem) 5
2.2.1 Cyclographic Maps 5
2.2.2 平移與旋轉的實體合併問題 7
2.2.3 限制幾何物件至變動圓圓心距離的實體合併問題 9
2.3 Bresenham’s Algorithm 11
2.3.1 利用Bresenham’s Algorithm繪製直線 11
2.3.2 利用Bresenham’s Algorithm繪製圓與楕圓 12
3. 變動圓相切問題之擴充 13
3.1　　建置貝氏曲線的Cyclographic Maps 13
3.2　　變動圓同時和三個不同的幾何物件相切問題之擴充 16
3.3　　求變動圓同時和三個不同的幾何物件相切之方法 17
3.4　　擴充實體合併問題 19
3.5　　求實體合併問題之方法 20
4. 變動圓相切問題之實作 22
4.1 求變動圓同時與三個不同的幾何物件相切 23
4.1.1 範例一： The LCB Problem 24
4.1.2 範例二： The BBB Problem 25
4.2 平移的實體合併問題 26
4.2.1 範例一： L(L1,L2,B3,B4) 26
4.2.2 範例二： L(B1,C2,B3,L4) 28
4.3 旋轉的實體合併問題 29
4.3.1 範例一： C(C1,C2,B3,B4) 30
4.3.2 範例二： C(B1,B2,B3,B4) 31
5. 結論 34
參考文獻 35

[1] Christoph M. Hoffmann, Ching-Shoei Chiang, “Variable-Radius Circles in Cluster Merging, Part I：Translational Clusters,” CAD, 34, pp. 787-797, 9, 2002.
[2] Christoph M. Hoffmann, Ching-Shoei Chiang, “Variable-Radius Circles in Cluster Merging, Part II：Rotational Clusters,” CAD,34 ,pp. 799-805, 9, 2002.
[3] Ching-Shoei Chiang, Robert Joan-Arinyo, “Revisiting Variable Radius Circles in Constructive Geometric Constraint Solving”, CAGD, 21, pp. 371-399, 4, 2004.
[4] William E.Wright, “Rendering: Parallelization of Bresenham's Line and Circle Algorithms”, IEEE Computer Graphics and Application, 10, pp. 60-67, 1990.
[5] Bouma, W., Fodos, I., Hoffman, C.M., Cai, J. and Paige, R. “A Geometric Constraint Solver,” CAD, Vol. 27(6), pp. 487-501, 1995.
[6] Fudos I., “Constraint Solving for Computer Aided Design”, Ph.D. thesis, Department of Computer Science, Purdue University, 1995.
[7] Hoffmann C.M., Vermeer P, “Geometric constraint solving in and “, Computing in Euclidean Geometry, World Scientific Publishing, pp. 266-298, 1995
[8] Joan-Arinyo, R., Soto, A., “A Correct Rule-Based Geometric Constraint Solver”, Computer and Graphics, 21(5), pp. 599-609, 1997.
[9] Fudos I, Hoffmann C.M., “Constraint-Based Parametric Conics for CAD”, CAD, 28(2), pp. 91-100, 1996.
[10] Hoffmann C.M., Peters J., “Geometric Constraints for CAGD”, Mathematical Methods for Curves and Surfaces, Vanderbilt University Press, pp. 237-254, 1995.
[11] Muirhead, F.R., “On the number and nature of the solutions of the Apollonius contact problem,” Proceedings of the Edinburgh Mathematical Society, 14, pp. 135-147, 2002.
[12] Bruen, A., Fisher, J.C., Wilker, J.B., “Apollonius by Inversion” Mathematics Magazine, Vol.56, No.2, 1983.
[13] Pottmann, H., Wallner J., Computational Line Geometry, pp. 327-425, Springer 2001.
[14] Allner, J., Krasauskas, R., Pottmann, H., “Error propogation in geometric constructions”, CAD, Vol. 32, No. 11, p631-641, 2000.
[15] Cassino Durand, C.M. Hoffmann, “A systematic framework for solving geometric constraints analytically”, J. Symbolic Computation, Vol. 30, pp. 493-519, 2000.
[16] Muller E, Krames L., “Vorlesungen Uber Darstellende Geometric II: Die Zyklographie”, Deuticke, Leipzig und Wien, 1929.
[17] Hoffmann C.M., George Vanecek, Jr, “Fundamental Techniques for Geometric and Solid Modeling”, Leondes, C.T., Advances in Control and Dynamics, Academic Press, 1991.
[18] Bresenhams, J.E., “Algorithm for computer control of a digital plottor”, IBM Syst. J., 4(1), pp. 25-30, 1965.
[19] X-W Liu, K Cheng, “Three-dimensional extension of Bresenham’s algorithm and its application in straight-line interpolation”, SC02401, 2002.
[20] R.T. Farouki, T.Sakkalis, “Pythagorean hodographs”, International Business Machines Corporation, 1990.
[21] Joan-Arinyo, R., Soto-Riera, A., “Combining constructive and equational geometric constraint solving techniques”, ACM Trans. Graph. 18(1), pp.35-55, 1999.
[22] F. S. HILL, JR., Computer Graphics, pp. 83-85, Prentice-Hall, 2001.
[23] John Kennedy, “A Fast Bresenham Type Algorithm For Drawing Circle”. CA 90405. Dept. of Mathematics, FL: Santa Monica College., 1994.
[24] John Kennedy, “A Fast Bresenham Type Algorithm For Drawing Ellipse”. CA 90405. Dept. of Mathematics, FL: Santa Monica College., 1994.