两张代数曲面之间Hausdorff距离的计算
Computing the Hausdorff Distance between Two Algebraic Surfaces
DOI: 10.12677/CSA.2013.39070, PDF, HTML,    国家自然科学基金支持
作者: 寿华好, 黄永明, 顾凯丽：浙江工业大学理学院，杭州；缪永伟：浙江工业大学计算机科学与技术学院，杭州；王丽萍：浙江工业大学经贸管理学院，杭州
关键词: Hausdorff距离；代数曲面；区间算术；细分算法；Hausdorff Distance; Algebraic Surface; Interval Arithmetic; Subdivision Algorithm
摘要: 基于细分算法和区间算术，本文提出一种计算代数曲面间的Hausdorff距离的新算法。该算法在计算出Hausdorff距离近似值的同时能给出误差值。在理论上讲，只要设置的体素大小足够小，就可以使得计算出的Hausdorff距离近似值与精确值之间的误差达到任意小。但具体计算的时候,如果精度要求较高则时间成本会变得很高。
Abstract: An algorithm for computing the approximate Hausdorff distance as well as its error value between two algebraic surfaces is proposed based on dividing and conquering subdivision technique and interval arithmetic. Theoretically, as long as the size of the voxels is small enough, the computed approximate Hausdorff distance can reach any precision, however, the CPU time used may be overwhelming.
文章引用：寿华好, 黄永明, 顾凯丽, 缪永伟, 王丽萍. 两张代数曲面之间Hausdorff距离的计算[J]. 计算机科学与应用, 2013, 3(9): 407-410. http://dx.doi.org/10.12677/CSA.2013.39070

参考文献

[1] Kim, Y.-J., Oh, Y.-T., Yoon, S.-H., et al. (2013) Efficient Hausdorff distance computation for freeform geometric models in close proximity. Computer Aided Design, 45, 270-276.
[2] Rucklidge, W. (1996) Efficient visual recognition using the Hausdorff distance. Lecture Notes in Computer Science, 1173, 1- 161.
[3] Atallah, M. (1983) A linear time algorithm for the Hausdorff distance between convex polygons. Information Processing Let- ters, 17, 207-209.
[4] Barton, M., Hanniel, I., Elber, G., et al. (2010) Precise Hausdorff distance computation between polygonal meshes. Computer Aided Geometric Design, 27, 580-591.
[5] Tang, M., Lee, M. and Kim, Y.-J. (2009) Interactive Hausdorff distance computation for general polygonal models. ACM Tran- sactions on Graphics, 28, 1-9.
[6] Kim, Y.-J., Oh, Y.-T., Yoon, S.-H., et al. (2010) Precise Haus- dorff distance computation for planar freeform curves using biarcs and depth buffer. The Visual Computer, 26, 1007-1016.
[7] Bai, Y.-B., Yong, J.-H., Liu, C.-Y., et al. (2011) Polyline ap- proach for approximating the Hausdorff distance between two planar free-form curves. Computer Aided Design, 43, 687-698.
[8] Chen, X.-D., Ma, W., Xu, G., et al. (2010) Computing the Haus- dorff distance between two B-spline curves. Computer Aided Design, 42, 1197-1206.
[9] Hanniel, I., Krishnamurthy, A. and McMains, S. (2012) Com- puting the Hausdorff distance between NURBS surfaces using numerical iteration on the GPU. Graphical Models, 74, 255-264.
[10] Jüttler, B. (2000) Bounding the Hausdorff distance of implicitly defined and/or parametric curves. Mathematical Methods in CAGD, 1-10.
[11] Li, Q.-D. and Tian, J. (2009) 2D piecewise algebraic splines for implicit modeling. ACM Transactions on Graphics, 28, 1-13.
[12] Shou, H.-H., Lin, H.-W., Ralph, M., et al. (2003) Modified af- fine arithmetic is more accurate than centered interval arithmetic or affine arithmetic. Lecture Notes in Computer Science, 2768, 355-365.