testdlg.cpp

DGCL （An Efficient Density and Grid Based Clustering Algorithm for Large Spatial Database）的实现代码

							}
							if(pGrid[i+1][j].used == true && pGrid[i+1][j].groupID != 0)  //3
							{
								if(nMaxDens < pGrid[i+1][j].density)
								{
									nMaxDens = pGrid[i+1][j].density;
									nGroupID = pGrid[i+1][j].groupID;
								}
							}
							if(pGrid[i][j+1].used == true && pGrid[i][j+1].groupID != 0)  //4
							{
								if(nMaxDens < pGrid[i][j+1].density)
								{
									nMaxDens = pGrid[i][j+1].density;
									nGroupID = pGrid[i][j+1].groupID;
								}
							}
							if(pGrid[i+1][j+1].used == true && pGrid[i+1][j+1].groupID != 0) //5
							{
								if(nMaxDens < pGrid[i+1][j+1].density)
								{
									nMaxDens = pGrid[i+1][j+1].density;
									nGroupID = pGrid[i+1][j+1].groupID;
								}
							}
							
							//分配groupID给未分配的cell
							pGrid[i][j].groupID = nGroupID;
							//							if(pGrid[i][j-1].groupID == 0)
							pGrid[i][j-1].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i+1][j-1].groupID == 0)
							pGrid[i+1][j-1].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i+1][j].groupID == 0)
							pGrid[i+1][j].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i][j+1].groupID == 0)
							pGrid[i][j+1].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i+1][j+1].groupID == 0)
							pGrid[i+1][j+1].groupID = pGrid[i][j].groupID;
						}
						break;
						
					case 5:  //check 3 neighbors
						while(true){
							if(pGrid[i-1][j-1].used == true)  //1
							{
								if(pGrid[i-1][j-1].groupID ==0) nUsedTab = true;
								else {
									nUsedTab = false;
									break;
								}
							}
							if(pGrid[i][j-1].used == true)  //2
							{
								if(pGrid[i][j-1].groupID == 0) nUsedTab = true;
								else{
									nUsedTab = false;
									break;
								}
							}
							if(pGrid[i-1][j].used == true)  //3
							{
								if(pGrid[i-1][j].groupID == 0) nUsedTab = true;
								else{
									nUsedTab = false;
									break;
								}
							}
							
							break;
						}//end while
						
						if(pGrid[i][j].groupID == 0 && nUsedTab == true)
						{
							pGrid[i][j].groupID = ++nGroupNum;
							pGrid[i-1][j-1].groupID = pGrid[i][j].groupID;
							pGrid[i][j-1].groupID = pGrid[i][j].groupID;
							pGrid[i-1][j].groupID = pGrid[i][j].groupID;
						}else{
							if(pGrid[i-1][j-1].used == true && pGrid[i-1][j-1].groupID != 0) //1
							{
								nMaxDens = pGrid[i-1][j-1].density;
								nGroupID = pGrid[i-1][j-1].groupID;
							}
							if(pGrid[i][j-1].used == true && pGrid[i][j-1].groupID != 0)  //2
							{
								if(nMaxDens < pGrid[i][j-1].density)
								{
									nMaxDens = pGrid[i][j-1].density;
									nGroupID = pGrid[i][j-1].groupID;
								}
							}
							if(pGrid[i-1][j].used == true && pGrid[i-1][j].groupID != 0)  //3
							{
								if(nMaxDens < pGrid[i-1][j].density)
								{
									nMaxDens = pGrid[i-1][j].density;
									nGroupID = pGrid[i-1][j].groupID;
								}
							}
							
							//分配groupID给未分配的cell
							pGrid[i][j].groupID = nGroupID;
							//							if(pGrid[i-1][j-1].groupID == 0)
							pGrid[i-1][j-1].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i][j-1].groupID == 0)
							pGrid[i][j-1].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i-1][j].groupID == 0)
							pGrid[i-1][j].groupID = pGrid[i][j].groupID;
							
						}
						break;
						
					case 6:  //3 neighbors
						while(true){
							if(pGrid[i-1][j].used == true)  //1
							{
								if(pGrid[i-1][j].groupID ==0) nUsedTab = true;
								else {
									nUsedTab = false;
									break;
								}
							}
							if(pGrid[i-1][j+1].used == true)  //2
							{
								if(pGrid[i-1][j+1].groupID == 0) nUsedTab = true;
								else{
									nUsedTab = false;
									break;
								}
							}
							if(pGrid[i][j+1].used == true)  //3
							{
								if(pGrid[i][j+1].groupID == 0) nUsedTab = true;
								else{
									nUsedTab = false;
									break;
								}
							}
							
							break;
						}//end while
						
						if(pGrid[i][j].groupID == 0 && nUsedTab == true)
						{
							pGrid[i][j].groupID = ++nGroupNum;
							pGrid[i-1][j].groupID = pGrid[i][j].groupID;
							pGrid[i-1][j+1].groupID = pGrid[i][j].groupID;
							pGrid[i][j+1].groupID = pGrid[i][j].groupID;
						}else{
							if(pGrid[i-1][j].used == true && pGrid[i-1][j].groupID != 0) //1
							{
								nMaxDens = pGrid[i-1][j].density;
								nGroupID = pGrid[i-1][j].groupID;
							}
							if(pGrid[i-1][j+1].used == true && pGrid[i-1][j+1].groupID != 0)  //2
							{
								if(nMaxDens < pGrid[i-1][j+1].density)
								{
									nMaxDens = pGrid[i-1][j+1].density;
									nGroupID = pGrid[i-1][j+1].groupID;
								}
							}
							if(pGrid[i][j+1].used == true && pGrid[i][j+1].groupID != 0)  //3
							{
								if(nMaxDens < pGrid[i][j+1].density)
								{
									nMaxDens = pGrid[i][j+1].density;
									nGroupID = pGrid[i][j+1].groupID;
								}
							}
							
							//分配groupID给未分配的cell
							pGrid[i][j].groupID = nGroupID;
							//							if(pGrid[i-1][j].groupID == 0)
							pGrid[i-1][j].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i-1][j+1].groupID == 0)
							pGrid[i-1][j+1].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i][j+1].groupID == 0)
							pGrid[i][j+1].groupID = pGrid[i][j].groupID;
						}
						break;
						
					case 9:  //check 3 neighbors
						while(true){
							if(pGrid[i][j-1].used == true)  //1
							{
								if(pGrid[i][j-1].groupID ==0) nUsedTab = true;
								else {
									nUsedTab = false;
									break;
								}
							}
							if(pGrid[i+1][j-1].used == true)  //2
							{
								if(pGrid[i+1][j-1].groupID == 0) nUsedTab = true;
								else{
									nUsedTab = false;
									break;
								}
							}
							if(pGrid[i+1][j].used == true)  //3
							{
								if(pGrid[i+1][j].groupID == 0) nUsedTab = true;
								else{
									nUsedTab = false;
									break;
								}
							}
							
							break;
						}//end while
						
						if(pGrid[i][j].groupID == 0 && nUsedTab == true)
						{
							pGrid[i][j].groupID = ++nGroupNum;
							pGrid[i][j-1].groupID = pGrid[i][j].groupID;
							pGrid[i+1][j-1].groupID = pGrid[i][j].groupID;
							pGrid[i+1][j].groupID = pGrid[i][j].groupID;
						}else{
							if(pGrid[i][j-1].used == true && pGrid[i][j-1].groupID != 0) //1
							{
								nMaxDens = pGrid[i][j-1].density;
								nGroupID = pGrid[i][j-1].groupID;
							}
							if(pGrid[i+1][j-1].used == true && pGrid[i+1][j-1].groupID != 0)  //2
							{
								if(nMaxDens < pGrid[i+1][j-1].density)
								{
									nMaxDens = pGrid[i+1][j-1].density;
									nGroupID = pGrid[i+1][j-1].groupID;
								}
							}
							if(pGrid[i+1][j].used == true && pGrid[i+1][j].groupID != 0)  //3
							{
								if(nMaxDens < pGrid[i+1][j].density)
								{
									nMaxDens = pGrid[i+1][j].density;
									nGroupID = pGrid[i+1][j].groupID;
								}
							}
							
							//分配groupID给未分配的cell
							pGrid[i][j].groupID = nGroupID;
							//							if(pGrid[i][j-1].groupID == 0)
							pGrid[i][j-1].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i+1][j-1].groupID == 0)
							pGrid[i+1][j-1].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i+1][j].groupID == 0)
							pGrid[i+1][j].groupID = pGrid[i][j].groupID;
						}
						
						break;
					case 10:  //check 3 neighbors
						while(true){
							if(pGrid[i+1][j].used == true)  //1
							{
								if(pGrid[i+1][j].groupID ==0) nUsedTab = true;
								else {
									nUsedTab = false;
									break;
								}
							}
							if(pGrid[i][j+1].used == true)  //2
							{
								if(pGrid[i][j+1].groupID == 0) nUsedTab = true;
								else{
									nUsedTab = false;
									break;
								}
							}
							if(pGrid[i+1][j+1].used == true)  //3
							{
								if(pGrid[i+1][j+1].groupID == 0) nUsedTab = true;
								else{
									nUsedTab = false;
									break;
								}
							}
							
							break;
						}//end while
						
						if(pGrid[i][j].groupID == 0 && nUsedTab == true)
						{
							pGrid[i][j].groupID = ++nGroupNum;
							pGrid[i+1][j].groupID = pGrid[i][j].groupID;
							pGrid[i][j+1].groupID = pGrid[i][j].groupID;
							pGrid[i+1][j+1].groupID = pGrid[i][j].groupID;
						}else{
							if(pGrid[i+1][j].used == true && pGrid[i+1][j].groupID != 0) //1
							{
								nMaxDens = pGrid[i+1][j].density;
								nGroupID = pGrid[i+1][j].groupID;
							}
							if(pGrid[i][j+1].used == true && pGrid[i][j+1].groupID != 0)  //2
							{
								if(nMaxDens < pGrid[i][j+1].density)
								{
									nMaxDens = pGrid[i][j+1].density;
									nGroupID = pGrid[i][j+1].groupID;
								}
							}
							if(pGrid[i+1][j+1].used == true && pGrid[i+1][j+1].groupID != 0)  //3
							{
								if(nMaxDens < pGrid[i+1][j+1].density)
								{
									nMaxDens = pGrid[i+1][j+1].density;
									nGroupID = pGrid[i+1][j+1].groupID;
								}
							}
							
							//分配groupID给未分配的cell
							pGrid[i][j].groupID = nGroupID;
							//							if(pGrid[i+1][j].groupID == 0)
							pGrid[i+1][j].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i][j+1].groupID == 0)
							pGrid[i][j+1].groupID = pGrid[i][j].groupID;
							//							if(pGrid[i+1][j+1].groupID == 0)
							pGrid[i+1][j+1].groupID = pGrid[i][j].groupID;
						}
						break;
						
					default:
						break;
					}// end switch
			
									
					 }//end if
					 }//end for
					 }//end for
					 
					 ////////////////////////////////////////////////////////////////////
					 //这部分是用来将聚簇后，相邻的聚簇再合并的程序，同时虑掉孤立点和自身密度小于density/n的网格
					 bool nCorlor_Used[8];  //用于判断哪些颜色可用
					 memset(nCorlor_Used,0x00,sizeof(bool)*8);
                     GRID_COMBINE* pGridCombine = new GRID_COMBINE[nGroupNum+1];
                     int nRealNeighbor_num;   //记录有效网格的实际邻居个数

					 for(i=0;i<nGroupNum+1;i++)
					 {
						 //						 pGridCombine[i].gridID = i;
						 pGridCombine[i].finalID = i;
						 pGridCombine[i].combineTab = false;
					 }
					 
					 int nLocalID,nNeighborID;
					 for(i=0;i<m_IntervalNum;i++)
					 {
						 for(j=0;j<m_IntervalNum;j++)
						 {
							 if(pGrid[i][j].used == true)
							 {
								 nRealNeighbor_num = 0;
								 nLocalID = pGrid[i][j].groupID;

								 nCheckResult = CheckCondition(i,j);
								 switch(nCheckResult) {
								 case 0:   //8 neighbors
									 if(pGrid[i-1][j-1].used == true)
									 {
										 nRealNeighbor_num++;
										 if(pGridCombine[pGrid[i-1][j-1].groupID].finalID != pGridCombine[pGrid[i][j].groupID].finalID)
										 {
										 nNeighborID = pGrid[i-1][j-1].groupID;
										 if(pGridCombine[nNeighborID].finalID > pGridCombine[nLocalID].finalID)
											 pGridCombine[nNeighborID].finalID = pGridCombine[nLocalID].finalID;
										 else if(pGridCombine[nNeighborID].finalID < pGridCombine[nLocalID].finalID)
											 pGridCombine[nLocalID].finalID = pGridCombine[nNeighborID].finalID;
										 pGridCombine[nNeighborID].combineTab = pGridCombine[nLocalID].combineTab = true;
										 }
									 }
									 if (pGrid[i][j-1].used == true) {
										 nRealNeighbor_num++;
										 if(pGridCombine[pGrid[i][j-1].groupID].finalID != pGridCombine[pGrid[i][j].groupID].finalID)
										 {
										 nNeighborID = pGrid[i][j-1].groupID;
										 
										 if(pGridCombine[nNeighborID].finalID > pGridCombine[nLocalID].finalID)
											 pGridCombine[nNeighborID].finalID = pGridCombine[nLocalID].finalID;
										 else if(pGridCombine[nNeighborID].finalID < pGridCombine[nLocalID].finalID)
											 pGridCombine[nLocalID].finalID = pGridCombine[nNeighborID].finalID;
										 pGridCombine[nNeighborID].combineTab = pGridCombine[nLocalID].combineTab = true;
										 }										 
									 }
									 if (pGrid[i+1][j-1].used == true) {
										 nRealNeighbor_num++;
										 if(pGridCombine[pGrid[i+1][j-1].groupID].finalID != pGridCombine[pGrid[i][j].groupID].finalID)
										 {
											 nNeighborID = pGrid[i+1][j-1].groupID;											 
											 if(pGridCombine[nNeighborID].finalID > pGridCombine[nLocalID].finalID)
												 pGridCombine[nNeighborID].finalID = pGridCombine[nLocalID].finalID;
											 else if(pGridCombine[nNeighborID].finalID < pGridCombine[nLocalID].finalID)
												 pGridCombine[nLocalID].finalID = pGridCombine[nNeighborID].finalID;
											 pGridCombine[nNeighborID].combineTab = pGridCombine[nLocalID].combineTab = true;
										 }										 
									 }
									 if (pGrid[i-1][j].used == true) {
										 nRealNeighbor_num++;
										 if(pGridCombine[pGrid[i-1][j].groupID].finalID != pGridCombine[pGrid[i][j].groupID].finalID)
										 {
											 nNeighborID = pGrid[i-1][j].groupID;										 
											 if(pGridCombine[nNeighborID].finalID > pGridCombine[nLocalID].finalID)
												 pGridCombine[nNeighborID].finalID = pGridCombine[nLocalID].finalID;
											 else if(pGridCombine[nNeighborID].finalID < pGridCombine[nLocalID].finalID)
												 pGridCombine[nLocalID].finalID = pGridCombine[nNeighborID].finalID;
											 pGridCombine[nNeighborID].combineTab = pGridCombine[nLocalID].combineTab = true;
										 }										 
									 }
									 if (pGrid[i+1][j].used == true) {
										 nRealNeighbor_num++;
										 if(pGridCombine[pGrid[i+1][j].groupID].finalID != pGridCombine[pGrid[i][j].groupID].finalID)
										 {
											 nNeighborID = pGrid[i+1][j].groupID;										 
											 if(pGridCombine[nNeighborID].finalID > pGridCombine[nLocalID].finalID)
												 pGridCombine[nNeighborID].finalID = pGridCombine[nLocalID].finalID;
											 else if(pGridCombine[nNeighborID].finalID < pGridCombine[nLocalID].finalID)
												 pGridCombine[nLocalID].finalID = pGridCombine[nNeighborID].finalID;
											 pGridCombine[nNeighborID].combineTab = pGridCombine[nLocalID].combineTab = true;
										 }									 
									 }
									 if (pGrid[i-1][j+1].used == true) {
										 nRealNeighbor_num++;
										 if(pGridCombine[pGrid[i-1][j+1].groupID].finalID != pGridCombine[pGrid[i][j].groupID].finalID)
										 {
											 nNeighborID = pGrid[i-1][j+1].groupID;										 
											 if(pGridCombine[nNeighborID].finalID > pGridCombine[nLocalID].finalID)
												 pGridCombine[nNeighborID].finalID = pGridCombine[nLocalID].finalID;
											 else if(pGridCombine[nNeighborID].finalID < pGridCombine[nLocalID].finalID)
												 pGridCombine[nLocalID].finalID = pGridCombine[nNeighborID].finalID;
											 pGridCombine[nNeighborID].combineTab = pGridCombine[nLocalID].combineTab = true;
										 }
									 }
									 if (pGrid[i][j+1].used == true) {
										 nRealNeighbor_num++;
										 if(pGridCombine[pGrid[i][j+1].groupID].finalID != pGridCombine[pGrid[i][j].groupID].finalID)
										 {
											 nNeighborID = pGrid[i][j+1].groupID;											 
											 if(pGridCombine[nNeighborID].finalID > pGridCombine[nLocalID].finalID)
												 pGridCombine[nNeighborID].finalID = pGridCombine[nLocalID].finalID;
											 else if(pGridCombine[nNeighborID].finalID < pGridCombine[nLocalID].finalID)
												 pGridCombine[nLocalID].finalID = pGridCombine[nNeighborID].finalID;
											 pGridCombine[nNeighborID].combineTab = pGridCombine[nLocalID].combineTab = tr