hanyeah

问题描述：有n个多边形，已知每个多边形的顶点（可以为任意多个），如果两个多边形至少有一个坐标相同的顶点，我们认为两个多边形是连接的，；现在要把这些多边形分组，相互连通的多边形分为一组，如何实现。

有空得学习一下图论，书到用时方恨少。

自己想了想，先实现了一个，有空再找理论。

结合之前学过的Floyd算法。

直接上代码，思路比较简单，有空再加注释。

<script>
function Point(x,y){
	this.x=x;
	this.y=y;
}

function distance(p1,p2){
	var dx=p1.x-p2.x;
	var dy=p1.y-p2.y;
	return Math.sqrt(dx*dx,dy*dy);
}

var p1=new Point(1,1);
var p2=new Point(10,1);
var p3=new Point(10,10);
var p4=new Point(10,20);
var p5=new Point(1,10);
var p6=new Point(1,20);
var p7=new Point(1,0);

var shape01=[p1,p2];
var shape02=[p1,p3];
var shape03=[p3];

var shape06=[p5,p6];
var shape05=[p5];

var shape04=[p7,p4];
var shape07=[p4];

var shapeArr=[shape01,shape02,shape03,shape04,shape05,shape06,shape07];
var len=shapeArr.length;

var arr=[];
for(var i=0;i<len;i++){
	arr[i]=[];
	for(var j=0;j<len;j++){
		arr[i][j]=isConnect(shapeArr[i],shapeArr[j]);
	}
}

shuchu(arr);

var arr2=[];
for(i=0;i<len;i++)
{
    arr2[i]=[];
    for(j=0;j<len;j++){
    	arr2[i][j]=false;
    }
}
//k在最外层，别写反了。
for(k=0;k<len;k++)
{
    for(i=0;i<len;i++)
    {
    	for(j=0;j<len;j++){
    		if(arr[i][k]&&arr[k][j]){
    			arr2[i][j]=true;
    		}
    	}
    }
}

shuchu(arr2);

var id=0;
var j=0;
var arr3=[];
for(i=0;i<len;i++){
	if(arr3[i]>=1){
		continue;
	}
	id++;
	for(j=i;j<len;j++){
		if(arr2[i][j]){
			arr3[j]=id;
		}
	}
}

console.log(arr3.join("\t"));

function shuchu(arr){
	var out=[];
	for(var i=0;i<arr.length;i++){
		out.push(arr[i].join("\t"));
	}
	console.log(out.join("\n"));
}

function isConnect(shape01,shape02){
	var len01=shape01.length;
	var len02=shape02.length;
	for(var i=0;i<len01;i++){
		var p1=shape01[i];
		for(var j=0;j<len02;j++){
			var p2=shape02[j];
			if(p1.x==p2.x&&p1.y==p2.y){
				return true;
			}
		}
	}
	return false;
}

</script>

输出结果：

前3个是一组，第4个和第7个是一组，第5个和第6个是一组。结果正确。