在網頁上實做簡單的多邊形-速度加強版

 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

以下是我測試的連結(慢一點、記憶體較少的機器有可能會當掉,請小心使用):

  1. 舊的方法http://www.fillano.idv.tw/test18.html
  2. 新的方法http://www.fillano.idv.tw/test20.html