点集图形在许多课题中都有涉及,例如,特殊空间的点、数字照片中的像素、银河中的星球和空间数据等。并且,点集图形集重建是图形重建领域的一个非常重要的内容。假设平面中有一系列离散的点,这些点仅凭我们的视觉系统是无法感知其所要表达的具体形状的。本文研究的主要内容就是如何由这些离散的点重建出一个我们能够识别的具体图形。为了重建出一个具体的图形,要从这个图形的凸包开始,一步步将这个图形的凸包进行凹化,这样就能够使更多的点回到边界上,从而能够更加接近点集所要表达的真实的图形。当一个点集是一列不含边界的离散点的时候,需要建立这个点集的一个凸包边界。本文利用的是Delaunay三角剖分的方法。显然,一个点集的凸包边界,就是这个点集经过Delaunay三角剖分之后形成的三角网的一个子集。所以,只要确定介值并删去多余的边即可得到这个点集的凸包。除此之外,本文还设计了一个有适当半径的圆,通过这个圆与点集中的两点形成的弦来确定这个点集的凸包。当输入的点集带有边界时,就需要对这个点集的边界进行检测。本文主要用到的算法是合并算法,分离算法和独立算法。当一个点集的凸包被构建完成后,就要对这个点集的凸包进行凹化处理。在进行凹化处理的时候,需要删去已知的边并利用这条边的两端点和点集内一点建立两条新的边。这就需要在每一步都选取适当的边和适当的点。在选择时,本文将已有的就近选择标准、最长边选择标准、等角选择标准结合起来,得到一个新的选择标准。最后文章给出这个算法的停止条件,如果满足条件,则算法停止,如果不满足,算法将循环进行。