选择最优路径非递归算法

我就是我 2022-05-26 09:56 138阅读 0赞

int selectshortpath(Mat& MatIn,vector<Point>& pts,int x,int y, int x1,int y1)
    {	 
    	//minx,miny------>minx,maxy---->maxx,maxy
    	/*vector<Point>ptshighlight;
    	neighbourpointsInRect2(MatIn,x,y,x1,y1,ptshighlight); 
    	for(int i=0;i<ptshighlight.size()-1;i++){
    		_selectshortpath(pts,ptshighlight[i].x,ptshighlight[i].y,ptshighlight[i+1].x,ptshighlight[i+1].y);
    	}*/	 
    	int minx,miny;
    	int maxx,maxy;
    	minx=min(x,x1);
    	miny=min(y,y1);
    	maxx=max(x,x1);
    	maxy=max(y,y1);
    
    	Rect rc(miny,minx,maxy-miny+1,maxx-minx+1);	 
    	//PrintMat2(MatIn,minx,miny,maxx-minx+1,maxy-miny+1);
    	Mat subMat=MatIn(rc).clone();
    
    	typedef struct _pointorder{
    		int x;
    		int y;
    		int order;
    		_pointorder(int a,int b,int c){
    			x=a;
    			y=b;
    			order=c;
    		};
    		_pointorder(){			
    		};
    	}PTO;
    	vector<vector<PTO>> lines;
    	vector<PTO>pathpts;	
    
    	PTO ptnow;
    	
    	int DIR[8][2]={/*{-1,-1},{-1,0},{-1,1},{0,-1},*/{0,1},/*{1,-1},*/{1,0},{1,1}}; 	
    
    	pathpts.push_back(PTO(x-minx,y-miny,0));
    	int flagx=x1>x?1:-1;
    	int flagy=y1>y?1:-1;
    
    		while(pathpts.size())
    		{		
    _do1:
    			ptnow=pathpts.back();
    			for(int iNum=ptnow.order;iNum<3;iNum++)  
    			{  
    				int iCurPosX=ptnow.x+DIR[iNum][0]*flagx;  
    				int iCurPosY=ptnow.y+DIR[iNum][1]*flagy;  
    				if(iCurPosX>=0 && iCurPosX<=(subMat.rows-1) && iCurPosY>=0 && iCurPosY<=(subMat.cols-1))  
    				{ 
    						if(iCurPosX==x1-minx&&iCurPosY==y1-miny)
    						{
    							lines.push_back(pathpts);
    							goto _do2;							 
    						}
    						else if(subMat.at<uchar>(iCurPosX,iCurPosY)==0 )//生长条件，自己调整  
    						{  
    							 pathpts.push_back(PTO(iCurPosX,iCurPosY,0));	
    							 goto _do1;
    							/* break;*/
    						} 
    				}  
    			}
    _do2:
    			pathpts.pop_back();
    			if(pathpts.size()){
    							ptnow=pathpts.back();
    							pathpts.pop_back();
    							ptnow.order++;
    							pathpts.push_back(ptnow);
    			}
    		}
    
    	if(lines.size()==0)return 0;
    	int smalllength=BIGINT;
    	int smallindex=0;
    	for(int i=0;i<lines.size();i++){
    		if(smalllength>lines[i].size()){
    			smalllength=lines[i].size();
    			smallindex=i;
    		}
    	}
    	
    	for(int i=0;i<lines[smallindex].size();i++){
    		pts.push_back(Point(lines[smallindex][i].x+minx,lines[smallindex][i].y+miny));
    	}
    	return 1;
    	/*for(int i=0;i<subMat.rows;i++){
    		for(int j=0;j<subMat.cols;j++){
    		}
    	}*/
    	//findlines(subMat.clone(),ptss,2);
    	//if(ptss.size()){
    	//	for(int i=0;i<ptss.size();i++){
    	//		 if(ptInptv(ptss[i],x-minx,y-miny)&&ptInptv(ptss[i],x1-minx,y1-miny))return ; 
    	//	}		
    	//}
    	//_selectshortpath( pts,  x,  y,   x1,  y1);
    }

在两个点之间选择一个最优路径连接，但是不能和现在已有的线段相交

本文是想解决这个问题

为什么不能和原有的曲线相交呢，因为如果相交就破坏了原来有的轮廓