ZwqXin - 图形相关算法http://www.zwqxin.com/ 一起学习OPENGL吧 - RainbowSoft Studio Z-Blog 1.8 Arwen Build 90619zh-CNCopyright 2008-2010 ZwqXin. Some Rights Reserved. Theme edited from ipati. Fri, 10 Sep 2010 12:16:21 +0800QuickSort 快速排序的实现a@b.com (zwqxin)http://www.zwqxin.com/archives/arithmetic/quick-sort-implement.htmlWed, 06 May 2009 01:21:55 +0800http://www.zwqxin.com/archives/arithmetic/quick-sort-implement.htmlQuickSort，快速排序。数据结构必然遇上之，原理都知道是分治法，但不实现一次总有些心慌。而一步一步实现算法的时候，往往会遇到新问题，新困难，新考验。本篇从QuickSort算法的理解说起，希望我不会又忘记了吧~——ZwqXin.com

1.二分治十分喜欢logN

我不太清楚这鼓仰慕之情是从哪里来的，是偶然的吗？不，大妈都说，只有必然。因此，请相信严谨的数学大师给予我们的教诲：二分治就是就是喜欢logN。而QuickSort是二分治，所以说起QuickSort，我们就联想起logN......注意底数是二哦。

把一个问题分解为两个，把两个问题分解为四个......分解直到能轻易解决当前问题的地步，再如同聚焦一样反噬回来——把原问题解决。假设底线是分解为N个，那么共经过logN次分解行为。当然这每次分解行为都包含了多个分解动作，但只要它们是同时发生的，就不必区分它们——这是什么道理？

2.QuickSort的道理

QuickSort处理N个数的时候，就是按上思路，先选取一个“主元”，再把整个数列分割成两部分，前部分的值小于“主元”，后部分的值大于“主元”——主元位于这两部分之间。然后分别对这两部分再做此处理（递归），最后就成了一组从小到大排列的数表了。主元的选取本来应该很考究，但为了效率应该随便选一个。理想情况是主元位是当前排序表中间大的元素，这样分出来的两子列将基本等大；如果不好采每次选的主元都是最小的那个，那就等着N^2的复杂度来收尾吧。但若非精心安排，是难以出现这个局面的，这里有篇文章[算法与数据结构——快速排序]用一堆数学证明了平均情况跟最好情况一样是N*logN（最好情况：二分，分解logN次，每次里都蕴涵N次比较换位）。

3.大于.小于

比较动作涉及比较换位，若是数值类型还好办，其他类型的怎么办呢？很明显需要自定义我们的“大于.小于”。由于相反性，就考虑小于就可以了（元素相等也得处理啊，归于“大于”那里吧）。抽象出这个“小于”函数，设为QSCompareL(A，B)，则整个QS算法弄成以下模样：

 
  1. template<typename ObjectQS>
  2. int QSort<ObjectQS>::Partition(ObjectQS *buffer, int low, int high, bool (*QSCompareL)( ObjectQS A,  ObjectQS B))
  3. {
  4.     ObjectQS pivotkey = buffer[low];
  5.  
  6.     while(low<high)
  7.     {
  8.         //while(low<high && buffer[high].ID >= pivotkey)
  9.         //while(low<high && QsortCompareGE(buffer[high], pivotkey) )
  10.           while(low<high && !(*QSCompareL)(buffer[high], pivotkey) )
  11.             high--;
  12.  
  13.         if(low < high)
  14.             buffer[low++] = buffer[high];
  15.  
  16.         //while(low<high && buffer[low].ID <= pivotkey)
  17.         //while(low<high && QsortCompareLE(buffer[low], pivotkey) )  
  18.           while(low<high && (*QSCompareL)(buffer[low], pivotkey) )           
  19.             low++;
  20.  
  21.         if(low < high)
  22.             buffer[high--] = buffer[low];
  23.  
  24.     }
  25.  
  26.  
  27.     buffer[low] = pivotkey;
  28.  
  29.     SORTtimes++;
  30.     return low;
  31. }
  32.  
  33. template<typename ObjectQS>
  34. void QSort<ObjectQS>::SetQSortObject(ObjectQS *buffer, int low, int high, bool (*QSCompareL)( ObjectQS A,  ObjectQS B))
  35. {
  36.     QSortObject = buffer;
  37.     mLow = low;
  38.     mHigh = high;
  39.     
  40.     QSCompareL_Func = QSCompareL;
  41.  
  42. }
  43.  
  44. template<typename ObjectQS>
  45. void QSort<ObjectQS>::CalQSortProcess(int low, int high)
  46. {
  47.     if(low<high)
  48.     {
  49.         int pivotloc = Partition(QSortObject, low, high, QSCompareL_Func);
  50.         CalQSortProcess(low, pivotloc-1);
  51.         CalQSortProcess(pivotloc+1, high);
  52.     }
  53. }
  54.  
  55. template<typename ObjectQS>
  56. void QSort<ObjectQS>::QSortProcess()
  57. { 
  58.     CalQSortProcess(mLow, mHigh);
  59. }

上面的注释行表明了一路下来代码的进化。递归的思路就不多说了，QSORT的核心是Partition函数和CalQSortProcess。基本上外调用之QSortProcess函数要知道的是待比较表和表的起始和结束位置，还有比较函数。这由SetQSortObject设置。函数编写运用了类模板，ObjectQS是随意的类型，因此使用者要自定义比较函数——当然对单纯的数值类型也可以不用，因为我给了个默认形参QsortCompareL专门比较数值类型的。

4.在游戏中的运用

排序是到处都需要用的东西。比起冒泡，Qsort具有明显的优势，事实上VC函数库也给出了简单数值的QSORT的API调用，STL里面的通用函数SORT很明显跟QSORT有关，我也很明显是看着STL之SORT来作为程序完备性的衡量.....

在游戏中，有时候需要给眼前怪物的ID排序，有时候需要知道怪物位置前后信息……实在太多应用了，只有你想不到的。

 
  1. typedef struct tagObjectX{
  2.     unsigned int ID;
  3.     CVector3  Position;
  4.     CVector3  Rotation;
  5.  
  6. } ObjectX;
  7.  
  8. bool CompareObjectX_ID(ObjectX A, ObjectX B){   return A.ID < B.ID; }
  9. bool CompareObjectX_PosZ(ObjectX A, ObjectX B){ return A.Position.z < B.Position.z; }
  10.  
  11. int main(int argc, char* argv[])
  12. {
  13.    ObjectX ObjectArray[10] = {.....};
  14.  
  15.  
  16.     //qsortX.SetQSortObject(ObjectArray, 0, 9, CompareObjectX_PosZ);
  17.     qsortX.SetQSortObject(ObjectArray, 0, 9, CompareObjectX_ID);
  18.     qsortX.QSortProcess();
  19.  
  20.  
  21.         int buffer[40] = {23,56,23,....,50,100,98};
  22.  
  23.       qsortX2.SetQSortObject(buffer, 0, 39);
  24.       qsortX2.QSortProcess();
  25.     
  26.       printf("SORTtimes:%d\n",qsortX2.GetSortTimes());
  27.       printf("index:%d\n", qsortX2.GetElementIndex(88) );
  28.  
  29.     return 0;
  30. }
  31.  

最后一行是返回查找元素的索引，既然都排好序了，何不用折半查找？于是就实现了一下折半查找，恩，又是递归，又是二分治，又是logN。

放出DEMO：QuickSort-searchByZwqXin.rar

]]>图形相关算法http://www.zwqxin.com/archives/arithmetic/quick-sort-implement.html#commenthttp://www.zwqxin.com/http://www.zwqxin.com/feed.asp?cmt=51http://www.zwqxin.com/cmd.asp?act=tb&id=51&key=842ce1023D数学：求点到直线的投影a@b.com (zwqxin)http://www.zwqxin.com/archives/arithmetic/project-point-to-line.htmlWed, 04 Mar 2009 14:26:13 +0800http://www.zwqxin.com/archives/arithmetic/project-point-to-line.html今天思考一个问题的时候，考虑到把空间中一个点投影到一个向量上，也就是project-point-to-vector，发现原来自己想不出来，惟有求助google，算法理解。——ZwqXin.com

事情是这样的，在OPENGL中，点的坐标定义于其模型坐标系XYZ，现在我经过某个转换生成了另一个3维坐标系X'Y'Z'，反映于原坐标系，就是三个满足正交的方向向量，干脆叫做X'和Y'和Z'。现在我有一个定义于模型坐标系XYZ的点阵，我需要把这些点分别投影到X'和Y'和Z'上，求投影点坐标。

问题有点虚，所以考虑把这三个正交向量看作三条直线，问题就变成了：求点到直线的投影。考虑一个点和一条直线，描述这条直线需要两个点P1和P2 （顺带一提，P2 -P1就是相应的那向量），待投影的点叫P3。不妨设P3投影到该直线后所得的点是P3'，注意P3'与P1、P2 共线，因此必然有一个比例因子t，令

t * （P2  - P1） =   P3' - P1

因此问题变为：已知P1、P2 、P3 ， P1和P2 共线，求比例因子t 。令vec1 = P3 - P1  ， vec2 = P2  - P1，显然dis = vec1 * vec2（点乘）就是vec1在vec2上的投影，既然vec1与vec2共享一个起点P1，那么dis就是P1到投影点P3'的距离了。于是

t = dis / length(P 1P2) = vec1 * vec2 / length(P 1P2)

                                                 = (P3 - P1) * (P2  - P1)  / abs (P2  - P1)

                                                          = (P3 - P1) * (P2  - P1)  / (P2  - P1) *(P2  - P1)

abs (P2  - P1)表示求模（也就是线段P 1P2的长度），abs (P2  - P1) = (P2  - P1) *(P2  - P1) 。由上两式子就能求出P3' 了。这么简单..........看来脑袋锈豆不浅。算法写进我的CVector3类里了。直线还原成向量的样子，相当于把直线用一个向量和一个参考点描述。

 
  1.  //点到矢量vec2的投影，ori_vec2表示vec2起点（投影参照点）
  2.   inline CVector3 Project2Vector(CVector3& vec2, CVector3 ori_vec2){
  3.       CVector3 dir = (*this) - ori_vec2;
  4.       double t = dir.DotProd(vec2) / vec2.DotProd(vec2);
  5.  
  6.       return ori_vec2 + vec2 * t;
  7.   };
  8.  
  9.  
  10. //例子
  11. {
  12. CVector3 pt = CVector3(.....);//待投影的点
  13. CVector3 ori_pt = CVector3(.....);//投影参考点,也就是上文的P1
  14. CVector3 vector = CVector3(.....);//待投影于其上的某向量
  15.  
  16. CVector3 point;
  17. point = pt .Project2Vector（vector， ori_pt ）；
  18. }

另：点到线段P 1P2的投影：

 
  1. CVector3 ClosestPointOnSegment(CVector3 p, CVector3 p1, CVector3 p2)
  2. {
  3.     CVector3 diff = p-p1;
  4.     CVector3 dir = p2-p1;
  5.     float dot1 = dot(diff,dir);
  6.     if (dot1 <= 0.0f) {
  7.         return p1;
  8.     }    
  9.     float dot2 = dot(dir,dir);
  10.     if (dot2 <= dot1) {
  11.         return p2;
  12.     }
  13.     float t=dot1/dot2;
  14.     return p1 + t * dir;
  15. }
]]>图形相关算法http://www.zwqxin.com/archives/arithmetic/project-point-to-line.html#commenthttp://www.zwqxin.com/http://www.zwqxin.com/feed.asp?cmt=36http://www.zwqxin.com/cmd.asp?act=tb&id=36&key=59942ab6