如何寻找C语言中多维点的凸包?

开课吧小一2021-04-02 16:37

介绍

在一些工程和计算机应用中,寻找一些给定点的凸壳是一个中间问题。例如,必须用凸壳来寻找一些点的Delaunay网格,这在三维图形中是非常需要的。因此,本文主要针对这一课题,用C语言开发了一个用于解决上述问题的库。由于C语言的适用性可以在基本平台上实现,因此利用了C语言。

所提供的库的一个最重要的特性是它能够用于二维、三维和更高维的点。以往的一些凸壳代码案例只能用于二维或三维点,而提供的库可以用于更高的点。

该库利用快速壳算法来寻找凸壳,在该代码中已经完全实现。需要注意的是,为解决这个问题,开发了一组算法,其中,快速壳算法比较流行,也比较好。

所提供的代码可以很容易地通过在你的模块中包含头文件来使用,这是该代码的另一个优点。必须强调的是,点的坐标是通过CSV文件导入到代码中的,结果(面)是由其他CSV文件导出的,这一点在本文其他部分完全可以解释。

如何寻找C语言中多维点的凸包

背景

本节介绍了本文中用到的一些基础知识和背景。首先是凸壳,即包含给定点的最小凸空间。实际上,寻找凸壳就是确定包含点的最小凸空间的问题,而这些点是作为问题的输入而给定的。最小的凸空间是通过一组面来表示的。下一张图解释这些定义,以便更好地理解。

如何寻找C语言中多维点的凸包

前面说过,在提供的代码中利用了快速壳算法,直接从这个链接中给出,可能对算法的更多细节有帮助。

本文提出了以下快速壳算法,用于寻找一些点的凸壳,其维度为d,由下一幅图呈现。(请注意,该算法是直接给出的论文,没有任何修改)。

如何寻找C语言中多维点的凸包

此外,还需要一个矩阵库来推导出结果,并在其中实现一些基本的矩阵代数运算。为此,我们利用了以下矩阵库。

- C语言矩阵库

现在,提供的库在下一节介绍。

凸包库

首先,需要注意的是,在下面的代码块中给出的凸壳库使用了一个C结构。

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

在上面的结构中,points是一个包括主要给定点的矩阵,center是这些点的中心,dim是点的维度。

此外,facets、neighbors_indices和outpoints_indices分别是代码最终得到的面、它们的邻面指数和每个面的外点指数。实际上,这些矩阵是代码的输出,可以用来显示得到的凸壳。矩阵facets显示了最终凸壳的面,neighbors_indices呈现了位于每个面附近的面的指数(第i行包含第i个面的邻面),outpoints_indices包含了位于每个面外的点的指数(第i行包含第i个面外的点的指数)。根据凸壳算法,当所有的面没有任何外部点时,算法就会终止。因此,在算法结束时,这个矩阵将是空的。

输入的点通过CSV文件导入,该文件包含所有点的坐标,如下面给出的。

CSV
Copy Code
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()。

C
Copy Code
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文件。那么,上述函数可以简单地调用,如这里给出的。

C++
Copy Code
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;
}

下面,介绍两个例子,说明在两个二维和三维问题中应用上述代码的结果。首先,考虑一组二维点,通过下图直观地呈现出来。

如何寻找C语言中多维点的凸包

并且,得到的凸壳在下图中给出。

如何寻找C语言中多维点的凸包

现在,对3D点重复上述例子,给定点如下。

如何寻找C语言中多维点的凸包

由代码可得上述各点的凸壳如下。

如何寻找C语言中多维点的凸包

可以看出,该代码正确地获得了二维和三维点的凸壳。必须强调的是,该代码能够用于更高维度的点,在此无法直观显示。

使用代码

通过包含以下头文件,可以方便地使用所开发的库。

C++
Copy Code
//
# include "MatLib.h"
# include "convexhull.h"
//

兴趣点

文章实现了寻找多维点的凸壳的快速算法。代码用C语言实现,可以在基本平台上使用。更多C/C++教程,尽在开课吧C/C++教程频道。

有用
分享
全部评论快来秀出你的观点
登录 后可发表观点…
发表
暂无评论,快来抢沙发!
算法刷题核心能力提升营