期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

一种启发式的球面点定位策略 被引量：2

A Heuristic Strategy for Spherical Point Location
在线阅读 下载PDF
导出
摘要 提出了一种适用于球面三角形网格的启发式点定位策略.通过构造规则子分网格将原始球面网格区域划分成若干具有子分层次关系的查询小块;在进行查询前,根据查询点p 的位置找到它所在的小块作为搜索区域,从而极大地缩小了查询范围;在查询过程中,根据重心坐标所包含的启发信息,选择一条从初始搜索三角形到目标三角形的最短查询路径.分析表明,启发式点定位策略比传统算法具有更优的运算性能. A heuristic strategy is presented to solve the point location problem in spherical triangulation mesh. Firstly, a spherical mesh with regular subdivision connectivity is constructed to partition the spherical domain into some small regions. Then the region, which contains the query point p, is found according to the position of p and selected as the search area for locating p. During the point location, the barycentric coordinates are used to extract local heuristic information about the location of p so as to find the shortest path from the start triangle to the target one containing p. In comparison with traditional algorithms, it is found that the heuristic strategy has better time and space performances.
作者 吴勇 何援军 蔡鸿明
机构地区 上海交通大学计算机科学与工程系
出处 《软件学报》 EI CSCD 北大核心 2005年第11期1983-1991,共9页 Journal of Software
基金 国家高技术研究发展计划(863)~~
关键词 球面网格 点定位 启发式策略 子分网格 重心坐标 spherical mesh point location heuristic strategy subdivision mesh barycentric coordinate
分类号 TP391 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献11

  • 1Dobkin D, Lipton RJ. Multidimensional searching problems. SIAM Journal on Computing, 1976,5(2): 181-186.
  • 2Kirkpatrick DG. Optimal search in planar subdivisions. SIAM Journal on Computing, 1983,12(1):28-35.
  • 3Sundareswara R, Schrater PR. Schrater: Extensible point location algorithm. In: Proc. of the Int'l Conf. on Geometrical Modeling and Graphics. London, 2003.84-89.
  • 4Mucke E, Saias I, Zhu B. Fast randomized point location without preprocessing in two and three dimensional delaunay triangulations. In: Proc. of the 12th Annual Symp. on Computational Geometry. Philadelphia: ACM Press, 1996. 274-283.
  • 5Certain A, Popovic J, DeRose T, Duchamp T, Salesin D, Stuetzle W. Interactive multiresolution surface viewing. In: Computer Graphics, Proc. of the SIGGRAPH'96. New Orleans: ACM Press, 1996. 91-98.
  • 6Zorin D, Schroder P, Sweldens W. Interactive multiresolution mesh editing. In: Computer Graphics, Proc. of the SIGGRAPH'97.Los Angeles: ACM Press, 1997. 259-268.
  • 7Schroder P, Sweldens W. Spherical wavelets: Efficiently representing functions on the sphere. In: Computer Graphics, Proc. of the SIGGRAPH'95. Los Angeles: ACM Press, 1995. 161-172.
  • 8Labsik U, Kobbelt L, Schneider R, Seidel HP. Progressive transmission of subdivision surfaces. Computational Geometry, 2000,15(1):25-39.
  • 9Kobbelt L, Vorsatz J, Labsik U, Seidel HP. A shrink wrapping approach to remeshing polygonal surfaces. In: Computer Graphics Forum, Proc. of the EUROGRAPHICS'99. Milan, 1999. 119-130.
  • 10Andrade MVA, Barros WF, Stolfi J. An exact algorithm for point location on spherical maps. In: Proc. of the IV Brazilian Symp.on Geoinformatics--GEOINFO 2002. Minas Gerais, 2002.99-107.

同被引文献14

  • 1宋淮林.平面任意多边形面积公式的推导及应用[J].现代电子技术,1994,17(1):43-46. 被引量：6
  • 2Gumhold S, Straβer W. Real time compression of triangle mesh connectivity [ C ] //Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Orlando, 1998: 133- 140
  • 3Rossignac J. Edgebreaker: connectivity compression for triangle meshes [J]. IEEE Transactions on Visualization and Computer Graphics, 1999, 5(1): 47-61
  • 4Isenburg M. Compressing polygon mesh connectivity with degree duality prediction [ C ] //Proceedings of Graphics Interface, Calgary, 2002:161-170
  • 5Khodakovsky A, Alliez P, Desbrun M, et al. Near-optimal connectivity encoding of 2-manifold polygon meshes [J]. Graphical Models, 2002, 64(3/4): 147-168
  • 6Deering M. Geometry compression [ C ] //Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 1995 : 13-20
  • 7Taubin G, Rossignac J. Geometric compression through topological surgery [J]. ACM Transactions on Graphics, 1998, 17(2) : 84-115
  • 8Touma C, Gotsman C. Triangle mesh compression [ C ]//Proceedings of Graphics Interface, Vancouver, 1998:26-34
  • 9Karni Z, Gotsman C. Spectral compression of mesh geometry [C] //Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans, 2000:279-286
  • 10Khodakovsky A, Schroeder P, Sweldens W. Progressive geometry compression [ C ] //Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans,2000:271-278

引证文献2

二级引证文献2

软件学报
2005年 第11期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部