在網頁上實做簡單的多邊形-速度加強版
Tue, 18 Jul 2006 11:17:25 +0800之前用Javascript OOP的方式寫的polygon物件,在產生大量polygons時會明顯地變慢。
用Javascript來繪圖可預期的就是會慢,不過原來的寫法還是有改進的空間。想到的方法就是捨棄定義Line以及Polygon物件,而以元素為Point的陣列來代替。一些需要的操作包括產生Line與Polygon的Point陣列、偵測點是否在多邊形內等,都用函數來實做。
如果要進一步改進,可能連Point物件都捨棄,全部用陣列來做,只是要改比較多程式,有空再做吧。
Point的定義仍然相同:
function Point (_x, _y) { this.x = _x; this.y = _y; }
產生Line的Point陣列的函數:
function getLine (_points) { if (_points.length != 2) { return false;//Line只有兩個頂點 } var points = new Array(); if (Math.abs(_points[1].x-_points[0].x) > Math.abs(_points[1].y-_points[0].y)) { var accu = _points[0].y; if (_points[1].x > _points[0].x) { for (var x = _points[0].x; x < _points[1].x+1; x++) { y = Math.floor(accu); accu += (_points[1].y - _points[0].y) / (_points[1].x - _points[0].x); points.push(new Point(x,y)); } } else if (_points[0].x > _points[1].x) { for (var x = _points[0].x; x > _points[1].x-1; x--) { y = Math.floor(accu); accu -= (_points[1].y - _points[0].y) / (_points[1].x - _points[0].x); points.push(new Point(x,y)); } } else { if (_points[1].y > _points[0].y) { for (var y=_points[0].y; y<_points[1].y+1; y++) { points.push(new Point(_points[0].x,y)) } } else { for (var y=_points[0].y; y>_points[1].y-1; y--) { points.push(new Point(_points[0].x,y)) } } } } else { var accu = _points[0].x; if (_points[1].y > _points[0].y) { for (var y = _points[0].y; y < _points[1].y+1; y++) { x = Math.floor(accu); accu += (_points[1].x - _points[0].x) / (_points[1].y - _points[0].y); points.push(new Point(x,y)); } } else if (_points[0].y > _points[1].y) { for (var y = _points[0].y; y > _points[1].y-1; y--) { x = Math.floor(accu); accu -= (_points[1].x - _points[0].x) / (_points[1].y - _points[0].y); points.push(new Point(x,y)); } } else { if (_points[1].x > _points[0].x) { for (var x=_points[0].x; x<_points[1].x+1; x++) { points.push(new Point(x,_points[0].y)) } } else { for (var x=_points[0].x; x>_points[1].x-1; x--) { points.push(new Point(x,_points[0].y)) } } } } return points; }
產生Polygon的Point陣列的函數:
function getPolygon (_points) { if (_points.length < 3) { return false;//polygon至少要有三個頂點 } var ret = new Array(); for (var i=0; i<_points.length; i++) { if ((i+1) == _points.length) { ret = ret.concat(getLine(new Array(_points[i], _points[0]))); ret.pop();//刪掉最後一個點,才不會重複 } else { ret = ret.concat(getLine(new Array(_points[i], _points[i+1]))); ret.pop(); } } return ret; }
偵測一個點是否在多邊形中的函數(簡化很多):
function inPolygon (_polygon, _point) { var testUp = false; var testDn = false; var testLt = false; var testRt = false; //修改了測試方法,由一個點向上下左右延伸出直線,如果與多邊形的邊相交 //則點在多邊形中(必須是凸多邊形才有效,不過我沒考慮邊是水平或垂直的狀況) for (var i=0; i<_polygon.length; i++) { if (_polygon.x == _point.x && _polygon.y > _point.y) testUp = true; if (_polygon.x == _point.x && _polygon.y < _point.y) testDn = true; if (_polygon.y == _point.y && _polygon.x > _point.x) testLt = true; if (_polygon.y == _point.y && _polygon.x < _point.x) testRt = true; } return (testUp && testDn && testLt && testRt); }
移動Polygon的函數:
function movePolygon(_polygon, _point) { for (var i=0; i<_polygon.length; i++) { _polygon[i].x += _point.x; _polygon[i].y += _point.y; } }
畫出多邊形的函數,因為用一個<div>代表一個點,其實速度是很慢的:
//處理點陣列,呼叫drawPixel畫出點
function drawPixels(_points, _color) {
for (var j=0;j<_points.length; j++) {
drawPixel(_points[j], _color);
}
}
//畫出點的函數
function drawPixel(_point, _color) {
var obj = document.createElement("div");
obj.style.position = "absolute";
obj.style.clip = "rect(0,1,1,0)";
obj.style.background = _color;
obj.innerHTML = " ";
obj.width = 1;
obj.height = 1;
obj.style.left = _point.x+"px";
obj.style.top = _point.y+"px";
obj.style.zIndex = 50;
obj.style.margin = "0";
obj.style.padding = "0";
obj.style.cursor = "default";
document.body.appendChild(obj);
}
最後做了一點小測試,速度比舊的方法提昇了不少。
(產生256個多邊形、移動、測試點是否在其中、畫出32個多邊形。時間單位:milliseconds)
舊的方法:
Firefox | 1 | 2 | 3 | 平均 |
產生多邊形 | 1219 | 1203 | 1219 | 1213.67 |
移動多邊形 | 1000 | 984 | 1000 | 994.67 |
測試點位置 | 1203 | 1125 | 1063 | 1130.33 |
畫出多邊形 | 21266 | 17578 | 20453 | 19765.67 |
IE 6 | 1 | 2 | 3 | 平均 |
產生多邊形 | 29672 | 29687 | 29547 | 29635.33 |
移動多邊形 | 50016 | 51500 | 50719 | 50745 |
測試點位置 | 1297 | 860 | 1157 | 1104.67 |
畫出多邊形 | 103922 | 103250 | 103250 | 103474 |
Firefox | 1 | 2 | 3 | 平均 |
產生多邊形 | 797 | 500 | 500 | 599 |
移動多邊形 | 63 | 63 | 63 | 63 |
測試點位置 | 907 | 875 | 921 | 901 |
畫出多邊形 | 4532 | 4656 | 4750 | 4646 |
IE 6 | 1 | 2 | 3 | 平均 |
產生多邊形 | 1703 | 1641 | 1641 | 1661.67 |
移動多邊形 | 94 | 94 | 94 | 94 |
測試點位置 | 110 | 109 | 94 | 104.33 |
畫出多邊形 | 10062 | 10297 | 10031 | 10130 |
以下是我測試的連結(慢一點、記憶體較少的機器有可能會當掉,請小心使用):