【摘要】 根据逆向工程中散乱数据点规模越来越大的趋势,为缩小剖分时搜寻和遍历数据点的空间范围,提高算法效率,提出了一种大规模散乱数据的空间划分方法及相应的数据结构和编码方案。同时,提出了外连剖分和内连剖分的概念,给出了基于局部增量网格扩张的3维散乱数据点的空间直接三角剖分算法。该算法的总体计算复杂度为O(N),与三角剖分的典型算法相比,有效降低了其时间复杂度,提高了剖分后网格的质量。更多还原

【Abstract】 In order to deal with the trend of increasing large scattered data points set in reverse engineering,a space partition strategy with its corresponding data structure and encoding method was proposed to improve the triangulating and search efficiency.At the same time,the concepts of inner-connection and outer-connection were put forward and the direct triangulation algorithm from 3D scattered points based on the local incremental mesh expansion method was provided.The computational complexity of this algorithm was O(N).Compared to the typical triangulation algorithms,it has significantly reduced its time complexity and improved the mesh quality.更多还原