基于Delaunay三角网的CBDT聚类算法研究

聚类分析是空间数据挖掘的重要方法之一.Delaunay三角网具有良好的空间邻近特性,应用于空间聚类分析具有独特的优势,提出了一种基于Delaunay三角网的聚类算法--CBDT算法,该算法采用了将Delaunay三角剖分得到的三角形划分为小三角形、狭长三角形和大三角形的聚类模型,通过一定规则分别以小三角形、狭长三角形为基准进行扩展从而实现聚类.CBDT算法相对于AUTOCLUST算法能识别密度渐变的簇,而且计算量要比AUTOCLUST小得多.经实验验证,证明了该算法的有效性.     

点云的形状与曲线重建算法

针对平面无序带噪点云的曲线重建问题,给出了点云形状的定义并提出了构造点云形状的算法.该算法基于Delaunay三角剖分,在构造好点云的Delaunay三角剖分后对三角剖分进行细化,使得在点云中的点周围形成空间上的局部均匀采样;基于集合论中的基本概念定义点云中内点、外点和边界点,并且明确地定义了点云的形状,根据Delaunay三角剖分细化时,选择不同的参数得到不同层次的点云的形状;选择合适的参数得到相应形状后,通过薄化过程得到具有流形结构的曲线.实验结果表明,采用文中算法得到的重建曲线很好地反映了点云的形状,验证了该算法的有效性.     

基于最优凸壳技术的Delaunay三角剖分算法

提出了一种基于最优凸壳技术的Delaunay三角剖分算法。该算法对离散点进行扫描线方式排序，利用最优凸壳技术进行凸壳的生成和三角网联结，最后利用有向边的拓扑结构进行三角网优化。该算法不但避免了所有的交点测试，而且使得新加入点与凸壳边的平均比较次数不大于4，从而实现了高效的三角剖分。     

球面凸类图形Delaunay三角剖分再分算法及其收敛性分析

在计算曲面Ricci Flow时,会因为三角网格中存在过小的角而出现不收敛的情况。针对这种不收敛的问题,提出一种提高最小角角度的球面凸类图形Delaunay三角剖分再分算法。首先,给出球面凸类图形Delaunay三角剖分再分算法。它的核心操作有两个：1）如果某条Delaunay劣弧被"侵占",通过添加Delaunay劣弧中点分割Delaunay劣弧;2）如果存在"瘦"球面三角形,通过添加球面三角形外接球面小圆圆心分解球面三角形。然后,利用局部特征尺度探索出所提算法的收敛条件并给出输出顶点的一个上界公式。根据实验输出的网格验证,所提算法网格生成的球面三角形没有狭小的角,适合用来计算Ricci Flow。     

带特征线约束的Delaunay三角剖分最优算法的研究及实现

为了提高特征线约束的Delaunay三角剖分的速度和功率,从两个方面进行改进;一是生成无约束的Delaunay三角网时,采用进行剖分算法;二是在约束线上插入点时,应用取三角形外接圆与特征线交点的方法。并行剖分算法具有较好的加速性能;“交点”插入算法考虑了特征线的影响域及Delaunay三角形规则的边界条件,在满足全局Delaunay三角剖分的前提下,使插入的点最少,对原有的网格影响最小。     

Delaunay三角剖分算法优化的实现

文章分析Delaunay三角剖分算法各种优缺点,提出了具体的优化思想。详细介绍了Delaunay三角剖分算法优化的设计步骤及实现的具体流程。通过VisualStudio．Net中的C＋＋编程验证了算法的有效性,并对该算法的时间复杂度进行了分析。     

基于Delaunay三角剖分的半径补偿新算法

合理的半径补偿算法能有效提高逆向工程的最终精度.在分析了现有半径补偿算法及其相应优缺点的基础上,针对三角网格法,通过Delaunay三角剖分思想的引入,提出了一种基于Delaunay三角剖分的半径补偿新算法,并对其中三角剖分的优化准则、边界点的处理等关键技术进行了详细的阐述,最后以增压器叶轮为例,实现了叶轮叶面测量数据的半径补偿.     

平面散乱点集约束Delaunay三角形剖分切割算法

文章提出了一种基于切割的平面散乱点集约束Delaunay三角剖分算法。该算法的基本思路是首先对平面散乱点集作约束最大空圆凸多边形剖分,然后对多边形的内部再作约束Delaunay三角形剖分。文章还证明了平面散乱点集的约束最大空圆凸多边形剖分是唯一的以及约束Delaunay三角剖分的不唯一性仅仅体现在约束最大空圆凸多边形的内部。使用约束最大空圆凸多边形的概念消除了由于“退化”现象（三个以上的点共圆）带来的算法上的潜在错误。     

通用点线面集Delaunay三角剖分与动态编辑

总结并提出了一种通用点线面集Delaunay三角剖分与动态编辑的统一算法。可以实现离散点的Delaunay三角剖分,约束线、面的Delaunay三角剖分,任意多边形内带特征约束(包括点、线、面)的三角剖分,一般Delaunay三角剖分的外边界都是其离散点集的凸包,且内岛屿一般没有挖掉,本算法实现了Delaunay三角剖分时内、外边界的保界处理。     

任意多边形Delaunay三角剖分改进算法

本文重点研究任意多边形的Delaunay三角剖分,研究发现现有常用任意多边形Delaunay三角剖分存在执行效率低、候选节点可能出现"位置违约"错误等缺陷,根据候选节点与当前边夹角的大小关系,本文提出一种基于有向边的任意多边形Delaunay三角剖分改进算法,该算法具有执行效率高,避免了现有常用算法中可能出现"位置违约"的错误,完善了原算法的健壮性.     

An adaptive spatial clustering algorithm based on delaunay triangulation

In this paper, an adaptive spatial clustering algorithm based on Delaunay triangulation (ASCDT for short) is proposed. The ASCDT algorithm employs both statistical features of the edges of Delaunay triangulation and a novel spatial proximity definition based upon Delaunay triangulation to detect spatial clusters. Normally, this algorithm can automatically discover clusters of complicated shapes, and non-homogeneous densities in a spatial database, without the need to set parameters or prior knowledge. The user can also modify the parameter to fit with special applications. In addition, the algorithm is robust to noise. Experiments on both simulated and real-world spatial databases (i.e. an earthquake dataset in China) are utilized to demonstrate the effectiveness and advantages of the ASCDT algorithm.     

一种改进的基于Delaunay三角网的聚类算法

Mundur等提出了一种基于Delaunay三角网的聚类算法,并将其应用于视频帧的多维特征数据的聚类以生成视频摘要,取得了较好的效果。但是,该算法计算量太大,导致效率不高。为提高该算法的效率,以适合于对大数据集的处理,提出了一种改进的基于Delaunay三角网的聚类算法。通过在典型数据集上的实验,提出了一种新的确定全局聚类阈值的方法,使得计算量大为减少。实验结果表明,该算法无需用户提供聚类参数,也能得到良好的聚类结果,因此能够实现聚类过程自动化;并且计算速度更快,效率更高,适合于大数据集的处理。     

基于Delaunay四面体剖分的网格分割算法

为了构建有意义曲面分片,提出一种基于Delaunay四面体剖分的网格分割算法.首先根据Delaunay四面体剖分得到多边形网格内部的四面体,求出每个面上反映网格内部信息的Delaunay体距离;然后对Delaunay体距离进行平滑处理,再对网格上面的Delaunay体距离进行聚类,用高斯混合模型对Delaunay体距离作柱状图的拟合,利用期望最大化算法来快速求得拟合结果;最后结合图切分技术,同时考虑聚类的结果、分割区域的边界平滑和视觉认知中的最小规则,得到最终的网格分割结果.实验结果表明,采用文中算法可以有效地实现有意义的网格分割.     

平面域上离散点的三角化实现

简单回顾了生成Delaunay三角网的分治算法，逐点插入法，三角网生长法等三类主流算法，提出了一种基于逐点插入思想的快速，有效的分区逐点插入三角化算法，实现了平面域上离散数据点的三角化，网络的优化是在网格生成过程中完成的，生成的网格符合Delaunay准。     

基于改进高斯核度量和KPCA的数据聚类新方法

大多数超椭球聚类（hyper-ellipsoidal clustering,HEC）算法都使用马氏距离作为距离度量,已经证明在该条件下划分聚类的代价函数是常量,导致HEC无法实现椭球聚类.本文说明了使用改进高斯核的HEC算法可以解释为寻找体积和密度都紧凑的椭球分簇,并提出了一种实用HEC算法-K-HEC,该算法能够有效地处理椭球形、不同大小和不同密度的分簇.为实现更复杂形状数据集的聚类,使用定义在核特征空间的椭球来改进K-HEC算法的能力,提出了EK-HEC算法.仿真实验证明所提出算法在聚类结果和性能上均优于K-means算法、模糊C-means算法、GMM-EM算法和基于最小体积椭球（minimum-volume ellipsoids,MVE）的马氏HEC算法,从而证明了本文算法的可行性和有效性.     

Dynamic hierarchical triangulation of a clustered data stream

This paper presents a novel approach to handle large amounts of geometric data. A data stream clustering is used to reduce the amount of data and build a hierarchy of clusters. The data stream concept allows for the processing of very large data sets. The cluster hierarchy is then used in a dynamic triangulation to create a multiresolution model. It allows for the interactive selection of a different level of detail in various parts of the data.A method for removal multiple points from Delaunay triangulation is proposed. It is significantly faster than the traditional approach. The clustering and the triangulation are supplemented by an elliptical metric to handle data with anisotropic properties.Compared to the closest competitive method by Isenburg et al., the presented algorithm requires only a single pass over the data and offers a high flexibility. These advantages culminate in a long running time. The method was tested on several large digital elevation maps. The clustering phase can take up to a few hours. Once the cluster hierarchy is built, the terrains can be efficiently manipulated in real time.     

Isotropic Surface Remeshing Using Constrained Centroidal Delaunay Mesh

We develop a novel isotropic remeshing method based on constrained centroidal Delaunay mesh (CCDM), a generalization of centroidal patch triangulation from 2D to mesh surface. Our method starts with resampling an input mesh with a vertex distribution according to a user‐defined density function. The initial remeshing result is then progressively optimized by alternatively recovering the Delaunay mesh and moving each vertex to the centroid of its 1‐ring neighborhood. The key to making such simple iterations work is an efficient optimization framework that combines both local and global optimization methods. Our method is parameterization‐free, thus avoiding the metric distortion introduced by parameterization, and generating more well‐shaped triangles. Our method guarantees that the topology of surface is preserved without requiring geodesic information. We conduct various experiments to demonstrate the simplicity, efficacy, and robustness of the presented method.     

Delaunay三角剖分在离群点检测中的应用

在传统的基于[K]近邻的算法中,需要为算法设置邻居参数[k]的值,只有具备相关的先验知识才能确定合适的参数值。为了减少参数对于离群点检测的影响,提出了一种无需参数的基于Delaunay三角剖分的离群点检测算法。Delaunay三角剖分是数值分析以及图形学中的重要基础理论,它的构建无需任何参数,在三角剖分图中的每个数据对象与它空间上相邻的点都存在边直接相连,因此可以形成一种有效的邻居关系。算法首先通过Delaunay三角剖分形成每个点的空间邻居集合,然后根据每个点与它们空间邻居之间的分布特征,计算它们的离群程度,根据离群程度的大小判断该点是否为离群点。通过实验与相关的算法比较,算法具有更好的效果。     

CHSMST: a clustering algorithm based on hyper surface and minimum spanning tree

As data mining having attracted a significant amount of research attention, many clustering algorithms have been proposed in the past decades. However, most of existing clustering methods have high computational time or are not suitable for discovering clusters with non-convex shape. In this paper, an efficient clustering algorithm CHSMST is proposed, which is based on clustering based on hyper surface (CHS) and minimum spanning tree. In the first step, CHSMST applies CHS to obtain initial clusters immediately. Thereafter, minimum spanning tree is introduced to handle locally dense data which is hard for CHS to deal with. The experiments show that CHSMST can discover clusters with arbitrary shape. Moreover, CHSMST is insensitive to the order of input samples and the run time of the algorithm increases moderately as the scale of dataset becomes large.     

基于密度和层次的快速聚类算法在数据挖掘中的设计及实现

本论文在对各种算法深入分析的基础上,尤其在对基于密度的聚类算法he基于层次的聚类算法深入研究的基础上,提出了一种全新的基于密度和层次的快速聚类算法。该算法保持了基于密度聚类算法发现任意形状簇的优点,而且具有近似线性的时间复杂性,因此该算法适合对大规模数据的挖掘。理论分析和实验结果也证明了基于密度和层次的聚类算法具有处理任意形状簇的聚类、对噪音数据不敏感的特点,并且其执行效率明显高于传统的DBSCAN算法。