在 C 中寻找多维点的凸包

• 下载源代码 - 5.6 KB

引言

求解给定点集的凸包是某些工程和计算机应用中的一个中等难度问题。例如，在三维图形中至关重要的 Delaunay 网格的求解就必须用到凸包。因此，本文将重点探讨这一主题，并开发一个用 C 语言解决上述问题的库。之所以选用 C 语言，是因为其在基本平台上的易实现性。

所提供库的一个重要特性是它能够处理二维、三维及更高维度的点。之前的一些凸包代码只能处理二维或三维点，而本库可以处理更高维度的点。

该库利用 Quickhull 算法来寻找凸包，该算法已在该代码中完全实现。值得注意的是，为了解决这个问题，已经开发了一系列算法，其中 Quickhull 算法最为流行且性能更优。

通过包含头文件，用户可以轻松地在自己的模块中使用该库，这是该代码的另一大优点。需要强调的是，点集的坐标通过 CSV 文件导入代码，而结果（面）则通过其他 CSV 文件导出，这将在本文的其余部分进行详细解释。

背景

本节将介绍本文用到的一些基本概念和背景知识。首先是凸包，它是包含给定点集的最小凸空间。事实上，求解凸包就是确定包含作为输入给出的点集的最小凸空间的问题。最小凸空间通过一组面来表示。下图将解释这些定义，以帮助更好地理解。

如前所述，所提供的代码利用了 Quickhull 算法，该算法直接来自此链接，可能对算法的更多细节有所帮助。

这篇论文提出了求解由 D 维表示的点集凸包的 Quickhull 算法，如下图所示。（请注意，算法直接摘自该论文，未作任何修改）

此外，还需要一个矩阵库来推导结果，其中实现了一些基本的矩阵代数运算。为此，使用了以下矩阵库

• C 语言矩阵库

现在，将在下一节介绍所提供的库。

凸包库

首先，应该注意的是，该凸包库使用了 C 语言的 `struct`，如下面的代码块所示。

struct convexhull{
	Mat* facets;
	Mat* neighbors_indices;
	Mat* outpoints_indices;
	Mat* points;	
	Mat* center;
	int dim;
};

在上述 `struct` 中，`points` 是包含原始给定点的矩阵，`center` 是这些点的中心，`dim` 是点的维度。

此外，`facets`、`neighbors_indices` 和outpoints_indices分别是面、它们相邻面的索引，以及每个面外部点的索引，这些最终由代码获得。事实上，这些矩阵是代码的输出，可以用来显示获得的凸包。矩阵 `facets` 显示了最终凸包的面，`neighbors_indices` 显示了位于每个面邻域的面索引（第 i 行包含第 i 个面的邻面），而outpoints_indices包含位于每个面外部的点索引（第 i 行包含位于第 i 个面外部的点的索引）。根据凸包算法，当所有面都没有外部点时，算法终止。因此，此矩阵在算法结束时将为空。

输入点通过 CSV 文件导入，该文件包含所有点的坐标，如下所示。

0.1138,-1.2119
0.9299,2.1966
-2.3492,3.0224
2.001,0.91613
-3.0714,1.374
-4.1366,3.381
-2.6511,-3.9353
1.6579,0.59524
-2.1934,-1.7031
4.6641,2.8957

事实上，每一行包含一个特定点的坐标。因此，为了供代码使用，输入点应设置为如上模板。该代码能够导出最终的面矩阵，该矩阵表示给定点的凸包。面在 CSV 文件中给出，该文件将在下一节介绍。

所提供库的主函数是 `convh()`，如下所示。

convexhull* convh(Mat* points){
	int dim=points->col;
	int Np=points->row;
	convexhull* cvh=(convexhull*)malloc(sizeof(convexhull));
	cvh->points=points;cvh->dim=dim;	
	init(cvh);	
	while(1==1){				
		int i=1;
		while(i<=cvh->facets->row&&cvh->outpoints_indices->entries[(i-1)*Np]==0){
			i++;
			continue;
		}		
		if(i>cvh->facets->row){
			break;
		}
		int fp=furthestpoint(cvh,i);				
		Mat* local_facets=newmat(1,0,0);
		Mat* boundary_facets=newmat(1,0,0);
		int Nf1=cvh->facets->row;
		localsearch(cvh,local_facets,boundary_facets,i,0,fp);		
		updatenewfacets(cvh,local_facets,boundary_facets,Nf1);									
		freemat(local_facets);
		freemat(boundary_facets);		
	}
	return cvh;
}

正如所见，`convh()` 函数接收原始点并获得包含结果的凸包结构。假设 `file1.txt` 是包含点的 CSV 文件。那么，上述函数可以简单地按如下方式调用。

int _tmain(int argc, _TCHAR* argv[])
{
	Mat* V=readmat("file1.txt");
	showmat(V);
	convexhull* cvh=convh(V);
	writemat("file2.txt",cvh->facets);
	writemat("file3.txt",cvh->neighbors_indices);
	writemat("file4.txt",cvh->outpoints_indices);
	getchar();
	return 0;
}

接下来，将展示两个示例，展示了在两个二维和三维问题中应用上述代码的结果。首先，考虑一组二维点，它们通过下图直观展示。

而获得的凸包在下图给出。

现在，对三维点重复上述示例，给定点如下。

上述点的凸包由代码按如下方式获得。

如可见，代码正确地获得了二维和三维点的凸包。必须强调的是，该代码能够用于更高维度的点，这些点在此处无法直观展示。

Using the Code

通过包含以下头文件，可以轻松使用开发的库。

//
# include "MatLib.h"
# include "convexhull.h"
//

关注点

本文实现了 Quickhull 算法来求解多维点集的凸包。代码是用 C 语言实现的，可以在基本平台上使用。

历史

• 2020 年 10 月 30 日：初始版本