軟件項目技術點(25)——提升性能之檢測繪制范圍 - fangsmile－IT工程師數位筆記本

文章出處

軟件里的一個畫面包含很多個元素，但是當縮放到某個局部位置時，需要繪制的元素個數就很少。那么怎么判斷某個元素是否需要進行繪制呢？

我們在繪制整個畫面時，是進行循環遍歷每個元素的，如下判斷是否進行繪制的代碼：

 1 var elements = this.commonElements.all();//獲取所有元素列表
 2 var winInfo = getWindow();//獲取畫布窗口的寬高值
 3 var viewMinx = 0;
 4 var viewMiny = 0;
 5 var viewMaxx = winInfo.width;
 6 var viewMaxy = winInfo.height;
 7 
 8 var windowViewPoints = new Common.List<Core.Point>();//存儲窗口矩形四個頂點的坐標值
 9 windowViewPoints.add(new Core.Point(viewMinx, viewMiny));
10 windowViewPoints.add(new Core.Point(viewMaxx, viewMaxy));
11 windowViewPoints.add(new Core.Point(viewMinx, viewMaxy));
12 windowViewPoints.add(new Core.Point(viewMaxx, viewMiny));
13 //循環繪制每個元素
14 for (var key in elements) {
15     var isDraw = false;
16     var config = elements[key].config;
17     if (config.width * that.scale > 20 || config.height * that.scale > 20) {//首先判斷該元素寬高不能都低于20像素，控制元素太小時不繪制
18         var points = elements[key].getAllPoints().viewTruePoints;//獲取該元素矩形四個點相對于畫布窗口的坐標值
19         isDraw = Common.CollisiionDetector._instance.RectToRectCollisionDec(windowViewPoints, points);//判斷窗口矩形和元素矩形是否有交叉重疊，決定是否進行繪制
20         if (isDraw) {
21             elements[key].draw(gotoComplete);
22         }
23     }
24 }

矩形間交叉重疊的檢測

下面主要介紹判斷窗口矩形和元素矩形是否有交叉重疊RectToRectCollisionDec方法是如何實現的?

下面讓大家看一個demo，主要展示如果兩個矩形同時在旋轉，沒有重疊時繪制的顏色是藍色，如果有重疊繪制成紅色

實現原理：

　　對于兩個多邊形，如果存在一個軸，使得兩個多邊形的在該軸上的投影不重疊，則多邊形之間沒有碰撞發生。

　　在這里所有可能的軸是指垂直于多邊形每個邊的軸。

第一步：我們需要制定哪個軸作為參考軸

　由于矩形對邊相互平行，因此平行的兩個邊共同擁有一條垂直于它們的軸。因此，對于每個矩形，需要用于檢測的軸只有兩條。我們只需要檢測在另一個矩形在該軸上的投影是否和該軸重疊。為了方便，我們可以直接拿矩形相鄰的兩個邊作為兩個軸，然后把這兩個軸和另一個矩形的四個邊作是否有重疊的比較。

RectToRectCollisionDec檢測兩個矩形是否有重疊交叉：

 1 //獲取該矩形上的四條邊
 2 private getFourLines(rectPointsArr: List<Core.Point>) {
 3     var p0 = rectPointsArr.get(0);
 4     var p1 = rectPointsArr.get(1);
 5     var p2 = rectPointsArr.get(2);
 6     var p3 = rectPointsArr.get(3);
 7     var l1 = [[p0.x, p0.y], [p1.x, p1.y]];
 8     var l2 = [[p1.x, p1.y], [p2.x, p2.y]];
 9     var l3 = [[p2.x, p2.y], [p3.x, p3.y]];
10     var l4 = [[p3.x, p3.y], [p0.x, p0.y]];
11     return [l1, l2, l3, l4];
12 }
13  //傳入兩個矩形的四個點，檢測兩個矩形是否有重疊交叉
14 RectToRectCollisionDec(r1PointArray: List<Core.Point>, r2PointArray: List<Core.Point>) {
15 
16     var linesArr1 = this.getFourLines(r1PointArray);//矩形1的四條邊
17     var linesArr2 = this.getFourLines(r2PointArray);//矩形2的四條邊
18 
19     //每個矩形相鄰的兩個邊作為兩個軸，分別和另一個矩形的四個邊進行投影重疊的比較，如果有一個返回false代表存在一個軸上的投影不重疊，detectAxisCollision函數來檢查一個矩形的四邊在指定軸上的投影是否和軸線段本身的投影重疊
20     if (this.detectAxisCollision(linesArr2[0], linesArr1) && this.detectAxisCollision(linesArr2[1], linesArr1) && this.detectAxisCollision(linesArr1[0], linesArr2) && this.detectAxisCollision(linesArr1[1], linesArr2)) {
21         return true;
22     }
23     return false;
24 
25 }

第二步：檢查一個矩形的四條邊在指定軸上的投影和軸線段本身在向量上的投影是否有重疊，首先需要獲取到一個矩形各個邊在該軸上的投影和該軸在該向量上的投影

要獲得線段在軸上的投影，我們需要分解為計算線段兩個頂點在軸上的投影。如何計算點在軸上的投影？

 1 private getTYPoing(p, axis) {//獲取點在軸上的投影點
 2     //頂點在軸上的投影
 3     var x = ((p[0] * axis[0] + p[1] * axis[1]) / (axis[0] * axis[0] + axis[1] * axis[1])) * axis[0];
 4     var y = ((p[0] * axis[0] + p[1] * axis[1]) / (axis[0] * axis[0] + axis[1] * axis[1])) * axis[1];
 5     return [x, y];
 6 }
 7 private getLineTYToAxis(line, axis) {//線到軸的投影
 8 
 9     var a = [axis[1][0] - axis[0][0], axis[1][1] - axis[0][1]];//軸向量axis的計算
10     var p0 = line[0];//線的一個頂點0
11     var p1 = line[1];//線的一個頂點1
12     var pt0 = this.getTYPoing(p0, a);
13     var pt1 = this.getTYPoing(p1, a);
14     return [pt0, pt1];
15 }
16

第三步：計算一條邊在指定軸上的投影和軸線段本身在向量上的投影是否有重疊

如何檢測線段的重疊？由于這里兩個線段是投影在同一個軸向量上，因此他們肯定平行，所以判別方法也比較簡單了。方法這里提供一個：線段端點的x軸坐標分別和另一線段的兩個端點的x軸坐標相減，得出的兩個結果相乘，如果存在結果小于0，則證明線段重疊（當兩個線段垂直的時候，使用端點的y軸坐標作判斷）

 1 private isLineOverlap(l1, l2) {//判斷線段是否重疊
 2 
 3     var l1p1 = l1[0], l1p2 = l1[1], l2p1 = l2[0], l2p2 = l2[1];
 4     if (l1p1[0] != l2p1[0]) {//非垂直X軸的兩線段
 5         if ((l1p1[0] - l2p1[0]) * (l1p1[0] - l2p2[0]) < 0 || (l1p2[0] - l2p1[0]) * (l1p2[0] - l2p2[0]) < 0 || (l2p1[0] - l1p1[0]) * (l2p1[0] - l1p2[0]) < 0 || (l2p2[0] - l1p1[0]) * (l2p2[0] - l1p2[0]) < 0) {
 6             return true;
 7         }
 8     }
 9     else {//垂直X軸
10         if ((l1p1[1] - l2p1[1]) * (l1p1[1] - l2p2[1]) < 0 || (l1p2[1] - l2p1[1]) * (l1p2[1] - l2p2[1]) < 0 || (l2p1[1] - l1p1[1]) * (l2p1[1] - l1p2[1]) < 0 || (l2p2[1] - l1p1[1]) * (l2p2[1] - l1p2[1]) < 0) {
11             return true;
12         }
13     }
14 
15     return false;
16 }

第四步：檢查一個矩形的四條邊在指定軸上的投影和軸線段本身在向量上的投影是否都不重疊，則沒有碰撞，否則產生碰撞。就是第一段代碼中函數RectToRectCollisionDec中調用的四次函數detectAxisCollision

線段交叉的檢測

軟件有也需要判斷線段與矩形是否交叉，線段之間是否交叉？

下面先介紹一個函數

CCW(p1, p2, p3): boolean {
     return (p3.y - p1.y) * (p2.x - p1.x) > (p2.y - p1.y) * (p3.x - p1.x);
}

CCW利用叉積的性質，這是圖形學的標準算法。

兩個向量的叉積如果是正的，說明是第一個向量轉到第二個向量是逆時針方向；反之亦然
。他的CCW函數就是干這個的。
用這個可以判斷一個點是在線段的左側還是右側。
然后只要判斷是否線段A的兩個端點在線段B的兩側并且線段B的兩個端點也在線段A的兩側就可以了。

線段與線段是否交叉的方法（線段A的兩個端點在線段B的兩側并且線段B的兩個端點也在線段A的兩側）：

LineToLineCollisionDec(line1Start: Core.Point, line1End: Core.Point, line2Start: Core.Point, line2End: Core.Point) {
    return (this.CCW(line1Start, line2Start, line2End) != this.CCW(line1End, line2Start, line2End)) && (this.CCW(line1Start, line1End, line2Start) != this.CCW(line1Start, line1End, line2End));
}

參考資料：碰撞檢測作分析：方向包圍盒(OBB)碰撞檢測 http://www.cnblogs.com/iamzhanglei/archive/2012/06/07/2539751.html

文章列表