学步园

　　Sutherland－Hodgeman多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。
　　上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。

//点在有向线段那侧<br /> /*<br /> 向量叉积法</p> <p> 　　为简单计，测试点表示为P点。假设窗口边界方向为顺时针，如图中所示，对于其中任一边界向量，从向量起点A向终点B看过去：</p> <p> 　　如果被测试点P在该边界线右边(即内侧)，AB×AP的方向与X-Y平面垂直并指向屏幕里面，即右手坐标系中Z轴的负方向。</p> <p> 　　反过来，如果P在该边界线的左边(即外侧)，这时AB×AP的方向与X-Y平面垂直并指向屏幕外面，即右手坐标系中Z轴的正方向。</p> <p> 　　设：点P(x，y)、点A(xA，yA)、点B(xB，yB)，<br /> 　　　　向量AB={(xB-xA)，(yB-yA)}，<br /> 　　　　向量AP={(x-xA)，(y-yA)}，</p> <p> 　　那么AB×AP的方向可由下式的符号来确定：</p> <p> V=(xB-xA)·(y-yA)-(x-xA)·(yB-yA) (3-14) </p> <p> 　　因此，当V≤0时，P在边界线内侧；</p> <p> 　　　　　而V>0时，P在边界线外侧。</p> <p>*/<br /> static int _RtInSide(RtVector vector, RtPoint point)<br /> {<br /> return (vector.ep.x - vector.sp.x) * (point.y - vector.sp.y) - (vector.ep.y - vector.sp.y) * (point.x - vector.sp.x);<br /> }</p> <p>//多边形点必须是顺时针方向<br /> int rtPrunePSH(RtPoint* src, int num, RtPoint** dest, int* total)<br /> {<br /> int i = 0, j = 0, k = -1, flag = 0;<br /> RtPoint start, stop;//被剪裁多边形<br /> RtPoint sp, ep;//剪裁窗口<br /> RtPoint* temp = NULL;<br /> temp = (RtPoint*)malloc(sizeof(RtPoint) * 3 * (*total));<br /> if (temp == NULL) return -1;</p> <p> sp = *(src + num - 1);</p> <p> for ( i = 0; i < num; i++)//剪裁窗口<br /> {<br /> ep = *(src + i);</p> <p> start = *((*dest) + *total - 1);<br /> flag = _RtInSide(rtVector(sp, ep), start) > 0 ? 0 : 1;</p> <p> for ( j = 0; j < *total; j++)//被剪裁的多边形<br /> {<br /> stop = *((*dest) + j);<br /> if (_RtInSide(rtVector(sp, ep), stop) <= 0)//当前第i个顶点是否在边界内侧<br /> {<br /> if (flag == 0)/*前一个点在外侧吗？*/<br /> {<br /> flag = 1;/*从外到内的情况，将标志置0,作为下一次循环的前一点标志*/<br /> k++;<br /> CRtPoint<double> point;<br /> CRtPoint<int> st(sp.x, sp.y), et(ep.x, ep.y);<br /> CRtLine<int> v1(st, et);<br /> st.SetData(start.x, start.y);<br /> et.SetData(stop.x, stop.y);<br /> CRtLine<int> v2(st, et);<br /> v2.Intersect(v1,point);<br /> (temp + k)->x = point[0];/*将交点放入新多边形*/<br /> (temp + k)->y = point[1];<br /> }<br /> k++;<br /> *(temp + k) = stop;/*将当前点pi放入新多边形*/<br /> }<br /> else<br /> {<br /> if (0 != flag)/*前一个点在内侧吗？*/<br /> {<br /> flag = 0;/*从内到外的情况，将标志置1,作为下一次循环的前一点标志*/<br /> k++;<br /> CRtPoint<double> point;<br /> CRtPoint<int> st(sp.x, sp.y), et(ep.x, ep.y);<br /> CRtLine<int> v1(st, et);<br /> st.SetData(start.x, start.y);<br /> et.SetData(stop.x, stop.y);<br /> CRtLine<int> v2(st, et);<br /> v2.Intersect(v1,point);<br /> (temp + k)->x = point[0];/*将交点放入新多边形*/<br /> (temp + k)->y = point[1];<br /> }<br /> }<br /> start = stop;/*将当前点作为下次循环的前一点*/<br /> }</p> <p> sp = ep;</p> <p> *total = k + 1;<br /> memcpy(*dest, temp, sizeof(RtPoint) * (*total));<br /> k = -1;<br /> }</p> <p> return 0;<br /> }