在網頁上實做簡單的多邊形-速度加強版
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 |
以下是我測試的連結（慢一點、記憶體較少的機器有可能會當掉，請小心使用）：