整型数组处理算法（十一）请实现一个函数：线段重叠(性能优化)。[风林火山]

请实现一个函数：线段重叠;
输入多个一维线段,求出这些线段相交的所有区域(也用线段表示);
一条线段用两个值表示(x0,x1), 其中x1>x0;
比如：输入线段数组[(2,4),(1.5,6),(0.5,3.5),(5,7),(7.5,9)],
输出线段数组[(1.5,4),(5,6)]

实现如下：

//线段点信息struct T_LineMsg{int nCount;//个数float fx;//值T_LineMsg(){nCount = 0;}};float** GetSegmentOverlap(float** array, int nCount,int& OutCount){int i;vector<T_LineMsg*> vecX0;vector<T_LineMsg*> vecX1;vector<T_LineMsg> vecXAll;float* tempX0 = new float[nCount];//保存X0float* tempX1 = new float[nCount];//保存X1int nRet = 0;  memset(tempX0, 0, nCount *sizeof(float));memset(tempX1, 0, nCount *sizeof(float));int nTotalData0 =0;int nTotalData1 =0;for (i = 0; i < nCount; i++) {  T_LineMsg TempAll;TempAll.fx = array[i][0];vecXAll.push_back(TempAll);TempAll.fx = array[i][1];vecXAll.push_back(TempAll);T_LineMsg* tempX0 = new T_LineMsg;tempX0->fx = array[i][0];vecX0.push_back(tempX0);T_LineMsg* tempX1 = new T_LineMsg;tempX1->fx = array[i][1];vecX1.push_back(tempX1);}nTotalData0 = vecX0.size();nTotalData1 = vecX1.size();for (i=0; i< vecXAll.size(); i++){cout << vecXAll[i].fx << ",";}cout << endl;/*for (i=0; i< nTotalData0; i++){cout << vecX0[i]->fx << ",";}cout << endl;for (i=0; i< nTotalData1; i++){cout << vecX1[i]->fx << ",";}cout << endl;*/float x0 = 0.0;  float x1 = 0.0;  int kk;//统计各值在线段区间里出现的次数for (i = 0; i < nCount; i++) {  x0 = array[i][0];  x1 = array[i][1];//cout << x0 << ", " << x1 << endl;for (kk = 0; kk < nTotalData0; kk++){  if (vecX0[kk]->fx > x0 && vecX0[kk]->fx < x1){++vecX0[kk]->nCount;}}for (kk = 0; kk < nTotalData1; kk++) {  if (vecX1[kk]->fx > x0 && vecX1[kk]->fx < x1){++vecX1[kk]->nCount;}}} nTotalData0 =1;nTotalData1 =1;//保存X0std::vector<T_LineMsg*>::iterator IterX0;for(IterX0=vecX0.begin(); IterX0!=vecX0.end(); IterX0++){T_LineMsg* temp = *IterX0;if (temp->nCount== 1){nRet = InsertData(tempX0, temp->fx, nTotalData0);if (nRet>0)  nTotalData0++;}delete temp;temp = NULL;}vecX0.clear();//保存X1std::vector<T_LineMsg*>::iterator IterX1;for(IterX1=vecX1.begin(); IterX1!=vecX1.end(); IterX1++){T_LineMsg* temp = *IterX1;if (temp->nCount == 1){nRet = InsertData(tempX1, temp->fx, nTotalData1);if (nRet>0)  nTotalData1++;}delete temp;temp = NULL;}vecX1.clear();OutCount = nTotalData0-1;float lastX1;if (OutCount > 0){float** result = new float* [OutCount];for (int m=0; m<OutCount; m++){result[m] = new float[2];}kk = 0;for (i=nTotalData0-2; i>=0; i--){if (kk > 0)lastX1 = result[kk-1][1];//处理(5,5.5),(5.5,6)的情况if (tempX0[i] == lastX1){result[kk-1][1] = tempX1[i];delete result[OutCount-1];OutCount--;}else{result[kk][0] = tempX0[i];result[kk][1] = tempX1[i];}kk++;}delete[] tempX0;tempX0=NULL;delete[] tempX1;tempX1=NULL;return result;}else{delete[] tempX0;tempX0=NULL;delete[] tempX1;tempX1=NULL;return NULL;}}/*按降序排列数组*/int InsertData(float* a, float nValue, int nCount){int nRet = 0;for (int i=0; i<nCount; i++){if (a[i]<nValue){for (int j=nCount-1; j>i; j--){a[j]=a[j-1];}a[i]=nValue;nRet = 1;break;//跳出循环}else if(a[i] == nValue){break;//跳出循环}}return nRet;}

转载请注明原创链接：http://blog.csdn.net/wujunokay/article/details/12623871