计算二维点集边界：凹多边形与凸多边形识别

资源摘要信息: "本资源主要涉及计算机图形学和计算几何中的点集边界提取问题，特别是对于二维点集中凸多边形边界和凹多边形边界的计算。在这个上下文中，凹多边形指的是其至少有一个内角大于180度的多边形，与之相对的凸多边形所有内角都小于180度。点集边界计算是许多算法的基石，包括图像处理、计算机视觉、机器人路径规划等领域。 具体来说，资源描述提到需要实现两个类：一个是凸多边形边界类，另一个是凹多边形边界类。这意味着我们需要分别处理两种不同的几何结构，并且为每种结构提供算法以提取和表示它们的边界。在计算机图形学中，点集边界提取是一个基础问题，它涉及到点集的最外层轮廓的识别和提取。 在算法实现方面，可能采用的算法包括但不限于： 1. 凸包算法（如Graham扫描法或Jarvis步进法）：这些算法可以用来计算点集的凸包，即完全包含点集的最小凸多边形。凸包的边是点集中的一部分，构成一个凸多边形边界。 2. 凹多边形边界计算（如分割和合并法或Delaunay三角剖分）：计算凹多边形边界较为复杂，需要通过特定的算法来检测凹点，并将凸多边形分割成多个凸子区域，然后对每个子区域构建凸包，最后将这些凸包合并成凹多边形边界。 从标签来看，资源涉及到的关键概念包括： - 凹多边形：一个多边形，其至少有一个内角大于180度。 - 凹边形：凹多边形的边。 - 点集：一组离散的点。 - 边界：点集的最外层轮廓，可以是凸多边形也可以是凹多边形。 - 边界点：构成点集边界的那些点。 在提供的压缩包子文件的文件名称列表中，tubao.cpp可能是一个C++源代码文件，其中包含上述提到的类的实现。而***.txt则可能是一个文本文件，它可能包含了资源的下载链接或其他文档信息，指向中国的一个软件下载网站PUDN。 总结来说，这个资源是一个涉及二维点集边界提取问题的编程资源，特别是对于凸多边形和凹多边形边界的实现。它可能包含相关的算法实现以及可能的测试数据或辅助信息。"