Skip to content

Commit 5bc83c3

Browse files
mbostockmbostock
committed
Use objects rather than arrays.
Turns out, o.x is much faster than o[0]!
1 parent fc73f2e commit 5bc83c3

11 files changed

Lines changed: 215 additions & 153 deletions

File tree

‎d3.js‎

Lines changed: 117 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -3018,7 +3018,7 @@ d3 = function() {
30183018
}
30193019
function d3_geom_clipLine(x0, y0, x1, y1) {
30203020
return function(line) {
3021-
var a = line[0], b = line[1], ax = a[0], ay = a[1], bx = b[0], by = b[1], t0 = 0, t1 = 1, dx = bx - ax, dy = by - ay, q, r;
3021+
var a = line.a, b = line.b, ax = a.x, ay = a.y, bx = b.x, by = b.y, t0 = 0, t1 = 1, dx = bx - ax, dy = by - ay, q, r;
30223022
q = ax - x0;
30233023
if (!dx && q < 0) return;
30243024
r = -q / dx;
@@ -3051,8 +3051,14 @@ d3 = function() {
30513051
} else if (dy > 0) {
30523052
if (r < t0) return; else if (r < t1) t1 = r;
30533053
}
3054-
if (t0 > 0) line[0] = [ ax + t0 * dx, ay + t0 * dy ];
3055-
if (t1 < 1) line[1] = [ ax + t1 * dx, ay + t1 * dy ];
3054+
if (t0 > 0) line.a = {
3055+
x: ax + t0 * dx,
3056+
y: ay + t0 * dy
3057+
};
3058+
if (t1 < 1) line.b = {
3059+
x: ax + t1 * dx,
3060+
y: ay + t1 * dy
3061+
};
30563062
return line;
30573063
};
30583064
}
@@ -3171,13 +3177,22 @@ d3 = function() {
31713177
}
31723178
} else {
31733179
if (v && v_) listener.point(x, y); else {
3174-
var l = [ [ x_, y_ ], [ x, y ] ];
3180+
var l = {
3181+
a: {
3182+
x: x_,
3183+
y: y_
3184+
},
3185+
b: {
3186+
x: x,
3187+
y: y
3188+
}
3189+
};
31753190
if (clipLine(l)) {
31763191
if (!v_) {
31773192
listener.lineStart();
3178-
listener.point(l[0][0], l[0][1]);
3193+
listener.point(l.a.x, l.a.y);
31793194
}
3180-
listener.point(l[1][0], l[1][1]);
3195+
listener.point(l.b.x, l.b.y);
31813196
if (!v) listener.lineEnd();
31823197
clean = false;
31833198
} else if (v) {
@@ -4563,10 +4578,13 @@ d3 = function() {
45634578
d3_geom_voronoiRedBlackNode(beach);
45644579
}
45654580
function d3_geom_voronoiRemoveBeach(beach) {
4566-
var circle = beach.circle, x = circle[0], y = circle.cy, vertex = [ x, y ], previous = beach.P, next = beach.N, disappearing = [ beach ];
4581+
var circle = beach.circle, x = circle.x, y = circle.cy, vertex = {
4582+
x: x,
4583+
y: y
4584+
}, previous = beach.P, next = beach.N, disappearing = [ beach ];
45674585
d3_geom_voronoiDetachBeach(beach);
45684586
var lArc = previous;
4569-
while (lArc.circle && abs(x - lArc.circle[0]) < ε && abs(y - lArc.circle.cy) < ε) {
4587+
while (lArc.circle && abs(x - lArc.circle.x) < ε && abs(y - lArc.circle.cy) < ε) {
45704588
previous = lArc.P;
45714589
disappearing.unshift(lArc);
45724590
d3_geom_voronoiDetachBeach(lArc);
@@ -4575,7 +4593,7 @@ d3 = function() {
45754593
disappearing.unshift(lArc);
45764594
d3_geom_voronoiDetachCircle(lArc);
45774595
var rArc = next;
4578-
while (rArc.circle && abs(x - rArc.circle[0]) < ε && abs(y - rArc.circle.cy) < ε) {
4596+
while (rArc.circle && abs(x - rArc.circle.x) < ε && abs(y - rArc.circle.cy) < ε) {
45794597
next = rArc.N;
45804598
disappearing.push(rArc);
45814599
d3_geom_voronoiDetachBeach(rArc);
@@ -4596,7 +4614,7 @@ d3 = function() {
45964614
d3_geom_voronoiAttachCircle(rArc);
45974615
}
45984616
function d3_geom_voronoiAddBeach(site) {
4599-
var x = site[0], directrix = site[1], lArc, rArc, dxl, dxr, node = d3_geom_voronoiBeaches._;
4617+
var x = site.x, directrix = site.y, lArc, rArc, dxl, dxr, node = d3_geom_voronoiBeaches._;
46004618
while (node) {
46014619
dxl = d3_geom_voronoiLeftBreakPoint(node, directrix) - x;
46024620
if (dxl > ε) node = node.L; else {
@@ -4639,20 +4657,23 @@ d3 = function() {
46394657
}
46404658
d3_geom_voronoiDetachCircle(lArc);
46414659
d3_geom_voronoiDetachCircle(rArc);
4642-
var lSite = lArc.site, ax = lSite[0], ay = lSite[1], bx = site[0] - ax, by = site[1] - ay, rSite = rArc.site, cx = rSite[0] - ax, cy = rSite[1] - ay, d = 2 * (bx * cy - by * cx), hb = bx * bx + by * by, hc = cx * cx + cy * cy, vertex = [ (cy * hb - by * hc) / d + ax, (bx * hc - cx * hb) / d + ay ];
4660+
var lSite = lArc.site, ax = lSite.x, ay = lSite.y, bx = site.x - ax, by = site.y - ay, rSite = rArc.site, cx = rSite.x - ax, cy = rSite.y - ay, d = 2 * (bx * cy - by * cx), hb = bx * bx + by * by, hc = cx * cx + cy * cy, vertex = {
4661+
x: (cy * hb - by * hc) / d + ax,
4662+
y: (bx * hc - cx * hb) / d + ay
4663+
};
46434664
d3_geom_voronoiSetEdgeEnd(rArc.edge, lSite, rSite, vertex);
46444665
newArc.edge = d3_geom_voronoiCreateEdge(lSite, site, null, vertex);
46454666
rArc.edge = d3_geom_voronoiCreateEdge(site, rSite, null, vertex);
46464667
d3_geom_voronoiAttachCircle(lArc);
46474668
d3_geom_voronoiAttachCircle(rArc);
46484669
}
46494670
function d3_geom_voronoiLeftBreakPoint(arc, directrix) {
4650-
var site = arc.site, rfocx = site[0], rfocy = site[1], pby2 = rfocy - directrix;
4671+
var site = arc.site, rfocx = site.x, rfocy = site.y, pby2 = rfocy - directrix;
46514672
if (!pby2) return rfocx;
46524673
var lArc = arc.P;
46534674
if (!lArc) return -Infinity;
46544675
site = lArc.site;
4655-
var lfocx = site[0], lfocy = site[1], plby2 = lfocy - directrix;
4676+
var lfocx = site.x, lfocy = site.y, plby2 = lfocy - directrix;
46564677
if (!plby2) return lfocx;
46574678
var hl = lfocx - rfocx, aby2 = 1 / pby2 - 1 / plby2, b = hl / plby2;
46584679
if (aby2) return (-b + Math.sqrt(b * b - 2 * aby2 * (hl * hl / (-2 * plby2) - lfocy + plby2 / 2 + rfocy - pby2 / 2))) / aby2 + rfocx;
@@ -4662,7 +4683,7 @@ d3 = function() {
46624683
var rArc = arc.N;
46634684
if (rArc) return d3_geom_voronoiLeftBreakPoint(rArc, directrix);
46644685
var site = arc.site;
4665-
return site[1] === directrix ? site[0] : Infinity;
4686+
return site.y === directrix ? site.x : Infinity;
46664687
}
46674688
function d3_geom_voronoiCell(site) {
46684689
this.site = site;
@@ -4672,7 +4693,7 @@ d3 = function() {
46724693
var halfEdges = this.edges, iHalfEdge = halfEdges.length, edge;
46734694
while (iHalfEdge--) {
46744695
edge = halfEdges[iHalfEdge].edge;
4675-
if (!edge[1] || !edge[0]) halfEdges.splice(iHalfEdge, 1);
4696+
if (!edge.b || !edge.a) halfEdges.splice(iHalfEdge, 1);
46764697
}
46774698
halfEdges.sort(d3_geom_voronoiHalfEdgeOrder);
46784699
return halfEdges.length;
@@ -4686,8 +4707,8 @@ d3 = function() {
46864707
nHalfEdges = halfEdges.length;
46874708
iHalfEdge = 0;
46884709
while (iHalfEdge < nHalfEdges) {
4689-
end = halfEdges[iHalfEdge].end(), x3 = end[0], y3 = end[1];
4690-
start = halfEdges[++iHalfEdge % nHalfEdges].start(), x2 = start[0], y2 = start[1];
4710+
end = halfEdges[iHalfEdge].end(), x3 = end.x, y3 = end.y;
4711+
start = halfEdges[++iHalfEdge % nHalfEdges].start(), x2 = start.x, y2 = start.y;
46914712
if (abs(x3 - x2) > ε || abs(y3 - y2) > ε) {
46924713
edge = d3_geom_voronoiCreateBorderEdge(cell.site, end, abs(x3 - x0) < ε && y1 - y3 > ε ? [ x0, abs(x2 - x0) < ε ? y2 : y1 ] : abs(y3 - y1) < ε && x1 - x3 > ε ? [ abs(y2 - y1) < ε ? x2 : x1, y1 ] : abs(x3 - x1) < ε && y3 - y0 > ε ? [ x1, abs(x2 - x1) < ε ? y2 : y0 ] : abs(y3 - y0) < ε && x3 - x0 > ε ? [ abs(y2 - y0) < ε ? x2 : x0, y0 ] : null);
46934714
halfEdges.splice(iHalfEdge, 0, new d3_geom_voronoiHalfEdge(edge, cell.site, null));
@@ -4701,27 +4722,27 @@ d3 = function() {
47014722
}
47024723
function d3_geom_voronoiCircle() {
47034724
d3_geom_voronoiRedBlackNode(this);
4704-
this[0] = this[1] = this.arc = this.site = this.cy = null;
4725+
this.x = this.y = this.arc = this.site = this.cy = null;
47054726
}
47064727
function d3_geom_voronoiAttachCircle(arc) {
47074728
var lArc = arc.P, rArc = arc.N;
47084729
if (!lArc || !rArc) return;
47094730
var lSite = lArc.site, cSite = arc.site, rSite = rArc.site;
47104731
if (lSite === rSite) return;
4711-
var bx = cSite[0], by = cSite[1], ax = lSite[0] - bx, ay = lSite[1] - by, cx = rSite[0] - bx, cy = rSite[1] - by;
4732+
var bx = cSite.x, by = cSite.y, ax = lSite.x - bx, ay = lSite.y - by, cx = rSite.x - bx, cy = rSite.y - by;
47124733
var d = 2 * (ax * cy - ay * cx);
47134734
if (d >= -ε2) return;
47144735
var ha = ax * ax + ay * ay, hc = cx * cx + cy * cy, x = (cy * ha - ay * hc) / d, y = (ax * hc - cx * ha) / d, cy = y + by;
47154736
var circle = d3_geom_voronoiCirclePool.pop() || new d3_geom_voronoiCircle();
47164737
circle.arc = arc;
47174738
circle.site = cSite;
4718-
circle[0] = x + bx;
4719-
circle[1] = cy + Math.sqrt(x * x + y * y);
4739+
circle.x = x + bx;
4740+
circle.y = cy + Math.sqrt(x * x + y * y);
47204741
circle.cy = cy;
47214742
arc.circle = circle;
47224743
var before = null, node = d3_geom_voronoiCircles._;
47234744
while (node) {
4724-
if (circle[1] < node[1] || circle[1] === node[1] && circle[0] <= node[0]) {
4745+
if (circle.y < node.y || circle.y === node.y && circle.x <= node.x) {
47254746
if (node.L) node = node.L; else {
47264747
before = node.P;
47274748
break;
@@ -4750,54 +4771,90 @@ d3 = function() {
47504771
var edges = d3_geom_voronoiEdges, clip = d3_geom_clipLine(extent[0][0], extent[0][1], extent[1][0], extent[1][1]), i = edges.length, e;
47514772
while (i--) {
47524773
e = edges[i];
4753-
if (!d3_geom_voronoiConnectEdge(e, extent) || !clip(e) || abs(e[0][0] - e[1][0]) < ε && abs(e[0][1] - e[1][1]) < ε) {
4754-
e[0] = e[1] = null;
4774+
if (!d3_geom_voronoiConnectEdge(e, extent) || !clip(e) || abs(e.a.x - e.b.x) < ε && abs(e.a.y - e.b.y) < ε) {
4775+
e.a = e.b = null;
47554776
edges.splice(i, 1);
47564777
}
47574778
}
47584779
}
47594780
function d3_geom_voronoiConnectEdge(edge, extent) {
4760-
var vb = edge[1];
4781+
var vb = edge.b;
47614782
if (vb) return true;
4762-
var va = edge[0], x0 = extent[0][0], x1 = extent[1][0], y0 = extent[0][1], y1 = extent[1][1], lSite = edge.l, rSite = edge.r, lx = lSite[0], ly = lSite[1], rx = rSite[0], ry = rSite[1], fx = (lx + rx) / 2, fy = (ly + ry) / 2, fm, fb;
4783+
var va = edge.a, x0 = extent[0][0], x1 = extent[1][0], y0 = extent[0][1], y1 = extent[1][1], lSite = edge.l, rSite = edge.r, lx = lSite.x, ly = lSite.y, rx = rSite.x, ry = rSite.y, fx = (lx + rx) / 2, fy = (ly + ry) / 2, fm, fb;
47634784
if (ry !== ly) {
47644785
fm = (lx - rx) / (ry - ly);
47654786
fb = fy - fm * fx;
47664787
}
47674788
if (fm == null) {
47684789
if (fx < x0 || fx >= x1) return;
47694790
if (lx > rx) {
4770-
if (!va) va = [ fx, y0 ]; else if (va[1] >= y1) return;
4771-
vb = [ fx, y1 ];
4791+
if (!va) va = {
4792+
x: fx,
4793+
y: y0
4794+
}; else if (va.y >= y1) return;
4795+
vb = {
4796+
x: fx,
4797+
y: y1
4798+
};
47724799
} else {
4773-
if (!va) va = [ fx, y1 ]; else if (va[1] < y0) return;
4774-
vb = [ fx, y0 ];
4800+
if (!va) va = {
4801+
x: fx,
4802+
y: y1
4803+
}; else if (va.y < y0) return;
4804+
vb = {
4805+
x: fx,
4806+
y: y0
4807+
};
47754808
}
47764809
} else if (fm < -1 || fm > 1) {
47774810
if (lx > rx) {
4778-
if (!va) va = [ (y0 - fb) / fm, y0 ]; else if (va[1] >= y1) return;
4779-
vb = [ (y1 - fb) / fm, y1 ];
4811+
if (!va) va = {
4812+
x: (y0 - fb) / fm,
4813+
y: y0
4814+
}; else if (va.y >= y1) return;
4815+
vb = {
4816+
x: (y1 - fb) / fm,
4817+
y: y1
4818+
};
47804819
} else {
4781-
if (!va) va = [ (y1 - fb) / fm, y1 ]; else if (va[1] < y0) return;
4782-
vb = [ (y0 - fb) / fm, y0 ];
4820+
if (!va) va = {
4821+
x: (y1 - fb) / fm,
4822+
y: y1
4823+
}; else if (va.y < y0) return;
4824+
vb = {
4825+
x: (y0 - fb) / fm,
4826+
y: y0
4827+
};
47834828
}
47844829
} else {
47854830
if (ly < ry) {
4786-
if (!va) va = [ x0, fm * x0 + fb ]; else if (va[0] >= x1) return;
4787-
vb = [ x1, fm * x1 + fb ];
4831+
if (!va) va = {
4832+
x: x0,
4833+
y: fm * x0 + fb
4834+
}; else if (va.x >= x1) return;
4835+
vb = {
4836+
x: x1,
4837+
y: fm * x1 + fb
4838+
};
47884839
} else {
4789-
if (!va) va = [ x1, fm * x1 + fb ]; else if (va[0] < x0) return;
4790-
vb = [ x0, fm * x0 + fb ];
4840+
if (!va) va = {
4841+
x: x1,
4842+
y: fm * x1 + fb
4843+
}; else if (va.x < x0) return;
4844+
vb = {
4845+
x: x0,
4846+
y: fm * x0 + fb
4847+
};
47914848
}
47924849
}
4793-
edge[0] = va;
4794-
edge[1] = vb;
4850+
edge.a = va;
4851+
edge.b = vb;
47954852
return true;
47964853
}
47974854
function d3_geom_voronoiEdge(lSite, rSite) {
47984855
this.l = lSite;
47994856
this.r = rSite;
4800-
this[0] = this[1] = null;
4857+
this.a = this.b = null;
48014858
}
48024859
function d3_geom_voronoiCreateEdge(lSite, rSite, va, vb) {
48034860
var edge = new d3_geom_voronoiEdge(lSite, rSite);
@@ -4810,32 +4867,34 @@ d3 = function() {
48104867
}
48114868
function d3_geom_voronoiCreateBorderEdge(lSite, va, vb) {
48124869
var edge = new d3_geom_voronoiEdge(lSite, null);
4813-
edge[0] = va;
4814-
edge[1] = vb;
4870+
edge.a = va;
4871+
edge.b = vb;
48154872
d3_geom_voronoiEdges.push(edge);
48164873
return edge;
48174874
}
48184875
function d3_geom_voronoiSetEdgeEnd(edge, lSite, rSite, vertex) {
4819-
if (!edge[0] && !edge[1]) {
4820-
edge[0] = vertex;
4876+
if (!edge.a && !edge.b) {
4877+
edge.a = vertex;
48214878
edge.l = lSite;
48224879
edge.r = rSite;
4880+
} else if (edge.l === rSite) {
4881+
edge.b = vertex;
48234882
} else {
4824-
edge[+(edge.l === rSite)] = vertex;
4883+
edge.a = vertex;
48254884
}
48264885
}
48274886
function d3_geom_voronoiHalfEdge(edge, lSite, rSite) {
4828-
var i = +(edge.l !== lSite), va = edge[1 - i], vb = edge[i];
4887+
var va = edge.a, vb = edge.b;
48294888
this.edge = edge;
48304889
this.site = lSite;
4831-
this.angle = rSite ? Math.atan2(rSite[1] - lSite[1], rSite[0] - lSite[0]) : Math.atan2(vb[0] - va[0], va[1] - vb[1]);
4890+
this.angle = rSite ? Math.atan2(rSite.y - lSite.y, rSite.x - lSite.x) : edge.l === lSite ? Math.atan2(vb.x - va.x, va.y - vb.y) : Math.atan2(va.x - vb.x, vb.y - va.y);
48324891
}
48334892
d3_geom_voronoiHalfEdge.prototype = {
48344893
start: function() {
4835-
return this.edge[+(this.edge.l !== this.site)];
4894+
return this.edge.l === this.site ? this.edge.a : this.edge.b;
48364895
},
48374896
end: function() {
4838-
return this.edge[+(this.edge.l === this.site)];
4897+
return this.edge.l === this.site ? this.edge.b : this.edge.a;
48394898
}
48404899
};
48414900
function d3_geom_voronoiRedBlackTree() {
@@ -5042,11 +5101,11 @@ d3 = function() {
50425101
d3_geom_voronoiCircles = new d3_geom_voronoiRedBlackTree();
50435102
while (true) {
50445103
circle = d3_geom_voronoiFirstCircle;
5045-
if (site && (!circle || site[1] < circle[1] || site[1] === circle[1] && site[0] < circle[0])) {
5046-
if (site[0] !== x0 || site[1] !== y0) {
5104+
if (site && (!circle || site.y < circle.y || site.y === circle.y && site.x < circle.x)) {
5105+
if (site.x !== x0 || site.y !== y0) {
50475106
d3_geom_voronoiCells[site.i] = new d3_geom_voronoiCell(site);
50485107
d3_geom_voronoiAddBeach(site);
5049-
x0 = site[0], y0 = site[1];
5108+
x0 = site.x, y0 = site.y;
50505109
}
50515110
site = sites.pop();
50525111
} else if (circle) {
@@ -5065,22 +5124,23 @@ d3 = function() {
50655124
return diagram;
50665125
}
50675126
function d3_geom_voronoiVertexOrder(a, b) {
5068-
return b[1] - a[1] || b[0] - a[0];
5127+
return b.y - a.y || b.x - a.x;
50695128
}
50705129
d3.geom.voronoi = function(points) {
50715130
var x = d3_svg_lineX, y = d3_svg_lineY, clipExtent = d3_geom_voronoiClipExtent;
50725131
if (points) return voronoi(points);
50735132
function voronoi(data) {
50745133
var fx = d3_functor(x), fy = d3_functor(y), sites = data.map(function(d, i) {
50755134
return {
5076-
0: fx(d, i),
5077-
1: fy(d, i),
5135+
x: fx(d, i),
5136+
y: fy(d, i),
50785137
i: i
50795138
};
50805139
}), polygons = [];
50815140
d3_geom_voronoi(sites, clipExtent).cells.forEach(function(cell, i) {
50825141
(polygons[i] = cell.edges.length ? cell.edges.map(function(edge) {
5083-
return edge.start();
5142+
var start = edge.start();
5143+
return [ start.x, start.y ];
50845144
}).reverse() : [ [ clipExtent[0][0], clipExtent[0][1] ], [ clipExtent[1][0], clipExtent[0][1] ], [ clipExtent[1][0], clipExtent[1][1] ], [ clipExtent[0][0], clipExtent[1][1] ] ]).point = data[i];
50855145
});
50865146
return polygons;

‎d3.min.js‎

Lines changed: 5 additions & 5 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/geo/clip-extent.js‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -154,13 +154,13 @@ function d3_geo_clipExtent(x0, y0, x1, y1) {
154154
} else {
155155
if (v && v_) listener.point(x, y);
156156
else {
157-
var l = [[x_, y_], [x, y]];
157+
var l = {a: {x: x_, y: y_}, b: {x: x, y: y}};
158158
if (clipLine(l)) {
159159
if (!v_) {
160160
listener.lineStart();
161-
listener.point(l[0][0], l[0][1]);
161+
listener.point(l.a.x, l.a.y);
162162
}
163-
listener.point(l[1][0], l[1][1]);
163+
listener.point(l.b.x, l.b.y);
164164
if (!v) listener.lineEnd();
165165
clean = false;
166166
} else if (v) {

0 commit comments

Comments
 (0)