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

输出线段数组[(1.5,4),(5,6)]

实现代码如下：

float** GetSegmentOverlap(float** array, int nCount,int& OutCount){int i;float* temp = new float[nCount * 2];  int* count = new int[nCount * 2];  memset(temp, 0, nCount * 2 *sizeof(float));int nTotalData = 0;for (i = 0; i < nCount; i++) {  for (int j = 0; j < 2; j++){  //temp[i * 2 + j] =  array[i][j];//这里进行排序InsertData(temp, array[i][j], ++nTotalData);count[i * 2 + j] =0;}  }/*for (i=0; i< (nCount * 2); i++){cout << temp[i] << ",";}cout << endl;*///Arrays.sort(temp);float x = 0.0;  float y = 0.0;  for (i = 0; i < nCount; i++) {  x = array[i][0];  for (int j = 1; j < nCount; j++) {  y = array[i][j];  for (int k = 0; k < nCount * 2; k++) {  //if (temp[k] >= x && temp[k] < y)  if (temp[k] > x && temp[k] < y)  ++count[k];  }  }  }  list<int*> resultList; int flag = 0;  for (i = 0; i < nCount * 2; i++) {  //if (count[i] > 1 && flag == 0) if (count[i] == 1 && flag == 0){  flag = 1;  resultList.push_back(new int(i));} else if (count[i] > 1 && flag == 1) {  } else if (count[i] == 1 && flag == 1) {  flag = 0;  resultList.push_back(new int(i)); }  }  list<int*>::iterator itorResultList;int k =resultList.size()-1;int* j;if (resultList.size() > 0) {  OutCount = resultList.size()/2;float** result = new float* [OutCount];for (int m=0; m<OutCount; m++){result[m] = new float[2];//new float}for (itorResultList = resultList.begin(); itorResultList != resultList.end(); itorResultList++) {  //for (int j = 0; j < list.size(); j++) //{  //result[i][j] = list.get(j);  //}  j = *itorResultList;//cout << (*j) << ", ";result[k/2][k%2] = temp[*j];k--;//cout << temp[*j] << "," ;//释放内存delete *itorResultList;*itorResultList=NULL;,这样是有问题的。delete j;j=NULL;}  delete[] temp;temp=NULL;delete[] count;count=NULL;return result;  } else  {delete[] temp;temp=NULL;delete[] count;count=NULL;return NULL;}}/*按降序排列数组*/int InsertData(float* a, float nValue, int nCount){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;break;//跳出循环}}return 0;}

有兴趣的朋友可以自己测试一下，仅提供参考。

此算法有点问题，当有相同起点的时候，完善版明天发布。

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