流形学习：从欧氏距离到测地距离的算法实现

"该项目是燕山大学学生完成的算法设计，主要涉及流形的概念，通过将数据点连接成邻接图来近似流形，并使用最短路径计算测地距离，从而将三维空间点映射到二维平面上。项目中采用了迪杰斯特拉算法求解最短路径，并进行了可视化展示。" 在算法三级项目---流形中，学生主要实现了以下几个关键知识点： 1. 流形概念：流形是一种数学对象，它可以局部看起来像欧几里得空间，即使在全球尺度上并不如此。在这个项目中，流形被用来模拟三维空间中的复杂几何形状。 2. 邻接Graph构建：为了近似流形，数据点被组织成一个邻接图。每个点与其他点通过边相连，这些边代表了点之间的“邻近”关系。这种结构使得可以在图上计算最短路径，进而求得测地距离。 3. 测地距离：在流形上，测地距离是从一点到另一点沿着表面的最短路径。在实际操作中，这通常通过计算图上的最短路径来近似实现。在这个项目中，迪杰斯特拉算法被用来找到从一个特定点（如原点（0,0,0））到所有其他点的最短路径。 4. 点集合构造：为了构建曲面，学生在XY平面上选择一系列点，然后在Z轴方向上为每个XY平面上的点随机选取多个点。这样得到的点集合在三维空间中构成了一个曲面。 5. 欧氏距离与测地距离：在项目中，首先计算所有点对的欧氏距离，然后设置一个阈值（小邻域值e），大于这个阈值的距离被视为无穷大，确保图是连通的。这有助于确保每个点都能通过一系列连续的边到达其他点。 6. 二维映射：通过测地线距离，将三维空间中的点映射到二维平面上。使用公式ki=sqrt(li*li-zi*zi)，其中li是点间的测地线距离，zi和ki分别是原三维点和映射到二维平面上的点的坐标。 7. 可视化：为了更好地理解映射过程，项目还包含了将三维空间中的点用颜色表示，并显示它们在二维平面上的位置，提供了直观的图形展示。 8. 程序结构：程序代码使用C++编写，包括GL/glut库用于图形渲染，math库进行数学计算，time库处理时间，stdlib和stdio库用于内存管理和输入输出。程序中定义了点的结构体，以及边表节点的权值数据类型。 此项目对于理解和实践流形学习、图形理论以及最短路径算法具有实际意义，对于学习计算机图形学和数据可视化的学生来说，是一个很好的参考实例。