Skip to content

Commit fa6ef52

Browse files
jasondaviesjasondavies
committed
Add d3.layout.voronoi.{links,triangles}.
1 parent 78a30ba commit fa6ef52

6 files changed

Lines changed: 99 additions & 19 deletions

File tree

‎d3.js‎

Lines changed: 31 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -3794,7 +3794,7 @@ d3 = function() {
37943794
var polygons = vertices.map(function() {
37953795
return [];
37963796
}), Z = 1e6;
3797-
d3_voronoi_tessellate(vertices, function(e) {
3797+
d3_geom_voronoiTessellate(vertices, function(e) {
37983798
var s1, s2, x1, x2, y1, y2;
37993799
if (e.a === 1 && e.b >= 0) {
38003800
s1 = e.ep.r;
@@ -3853,11 +3853,11 @@ d3 = function() {
38533853
});
38543854
return polygons;
38553855
};
3856-
var d3_voronoi_opposite = {
3856+
var d3_geom_voronoiOpposite = {
38573857
l: "r",
38583858
r: "l"
38593859
};
3860-
function d3_voronoi_tessellate(vertices, callback) {
3860+
function d3_geom_voronoiTessellate(vertices, callback) {
38613861
var Sites = {
38623862
list: vertices.map(function(v, i) {
38633863
return {
@@ -3919,7 +3919,7 @@ d3 = function() {
39193919
return he.edge == null ? Sites.bottomSite : he.edge.region[he.side];
39203920
},
39213921
rightRegion: function(he) {
3922-
return he.edge == null ? Sites.bottomSite : he.edge.region[d3_voronoi_opposite[he.side]];
3922+
return he.edge == null ? Sites.bottomSite : he.edge.region[d3_geom_voronoiOpposite[he.side]];
39233923
}
39243924
};
39253925
var Geom = {
@@ -4009,7 +4009,7 @@ d3 = function() {
40094009
},
40104010
endPoint: function(edge, side, site) {
40114011
edge.ep[side] = site;
4012-
if (!edge.ep[d3_voronoi_opposite[side]]) return;
4012+
if (!edge.ep[d3_geom_voronoiOpposite[side]]) return;
40134013
callback(edge);
40144014
},
40154015
distance: function(s, t) {
@@ -4109,7 +4109,7 @@ d3 = function() {
41094109
e = Geom.bisect(bot, top);
41104110
bisector = EdgeList.createHalfEdge(e, pm);
41114111
EdgeList.insert(llbnd, bisector);
4112-
Geom.endPoint(e, d3_voronoi_opposite[pm], v);
4112+
Geom.endPoint(e, d3_geom_voronoiOpposite[pm], v);
41134113
p = Geom.intersect(llbnd, bisector);
41144114
if (p) {
41154115
EventQueue.del(llbnd);
@@ -4131,7 +4131,7 @@ d3 = function() {
41314131
var edges = vertices.map(function() {
41324132
return [];
41334133
}), triangles = [];
4134-
d3_voronoi_tessellate(vertices, function(e) {
4134+
d3_geom_voronoiTessellate(vertices, function(e) {
41354135
edges[e.region.l.index].push(vertices[e.region.r.index]);
41364136
});
41374137
edges.forEach(function(edge, i) {
@@ -6204,6 +6204,30 @@ d3 = function() {
62046204
}
62056205
return voronoi;
62066206
};
6207+
voronoi.links = function(data) {
6208+
var points = [], graph = [], links = [], fx = d3_functor(x), fy = d3_functor(y), d, i, n = data.length;
6209+
for (i = 0; i < n; ++i) points.push([ +fx.call(this, d = data[i], i), +fy.call(this, d, i) ]),
6210+
graph.push([]);
6211+
d3_geom_voronoiTessellate(points, function(e) {
6212+
var l = e.region.l.index, r = e.region.r.index;
6213+
if (graph[l][r]) return;
6214+
graph[l][r] = graph[r][l] = true;
6215+
links.push({
6216+
source: points[l],
6217+
target: points[r]
6218+
});
6219+
});
6220+
return links;
6221+
};
6222+
voronoi.triangles = function(data) {
6223+
var points = [], point, fx = d3_functor(x), fy = d3_functor(y), d, i, n = data.length;
6224+
for (i = 0; i < n; ++i) {
6225+
point = [ +fx.call(this, d = data[i], i), +fy.call(this, d, i) ];
6226+
point.data = d;
6227+
points.push(point);
6228+
}
6229+
return d3.geom.delaunay(points);
6230+
};
62076231
return voronoi;
62086232
};
62096233
d3.random = {

‎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/geom/delaunay.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@ d3.geom.delaunay = function(vertices) {
1010
triangles = [];
1111

1212
// Use the Voronoi tessellation to determine Delaunay edges.
13-
d3_voronoi_tessellate(vertices, function(e) {
13+
d3_geom_voronoiTessellate(vertices, function(e) {
1414
edges[e.region.l.index].push(vertices[e.region.r.index]);
1515
});
1616

‎src/geom/voronoi.js‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@ d3.geom.voronoi = function(vertices) {
2626
var polygons = vertices.map(function() { return []; }),
2727
Z = 1e6;
2828

29-
d3_voronoi_tessellate(vertices, function(e) {
29+
d3_geom_voronoiTessellate(vertices, function(e) {
3030
var s1,
3131
s2,
3232
x1,
@@ -103,9 +103,9 @@ d3.geom.voronoi = function(vertices) {
103103
return polygons;
104104
};
105105

106-
var d3_voronoi_opposite = {l: "r", r: "l"};
106+
var d3_geom_voronoiOpposite = {l: "r", r: "l"};
107107

108-
function d3_voronoi_tessellate(vertices, callback) {
108+
function d3_geom_voronoiTessellate(vertices, callback) {
109109

110110
var Sites = {
111111
list: vertices
@@ -188,7 +188,7 @@ function d3_voronoi_tessellate(vertices, callback) {
188188
rightRegion: function(he) {
189189
return he.edge == null
190190
? Sites.bottomSite
191-
: he.edge.region[d3_voronoi_opposite[he.side]];
191+
: he.edge.region[d3_geom_voronoiOpposite[he.side]];
192192
}
193193
};
194194

@@ -307,7 +307,7 @@ function d3_voronoi_tessellate(vertices, callback) {
307307

308308
endPoint: function(edge, side, site) {
309309
edge.ep[side] = site;
310-
if (!edge.ep[d3_voronoi_opposite[side]]) return;
310+
if (!edge.ep[d3_geom_voronoiOpposite[side]]) return;
311311
callback(edge);
312312
},
313313

@@ -422,7 +422,7 @@ function d3_voronoi_tessellate(vertices, callback) {
422422
e = Geom.bisect(bot, top);
423423
bisector = EdgeList.createHalfEdge(e, pm);
424424
EdgeList.insert(llbnd, bisector);
425-
Geom.endPoint(e, d3_voronoi_opposite[pm], v);
425+
Geom.endPoint(e, d3_geom_voronoiOpposite[pm], v);
426426
p = Geom.intersect(llbnd, bisector);
427427
if (p) {
428428
EventQueue.del(llbnd);

‎src/layout/voronoi.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
import "../core/functor";
2+
import "../geom/delaunay";
23
import "../geom/polygon";
34
import "../geom/voronoi";
45
import "../svg/line";
@@ -44,5 +45,41 @@ d3.layout.voronoi = function() {
4445
return voronoi;
4546
};
4647

48+
voronoi.links = function(data) {
49+
var points = [],
50+
graph = [],
51+
links = [],
52+
fx = d3_functor(x),
53+
fy = d3_functor(y),
54+
d,
55+
i,
56+
n = data.length;
57+
for (i = 0; i < n; ++i) points.push([+fx.call(this, d = data[i], i), +fy.call(this, d, i)]), graph.push([]);
58+
d3_geom_voronoiTessellate(points, function(e) {
59+
var l = e.region.l.index,
60+
r = e.region.r.index;
61+
if (graph[l][r]) return;
62+
graph[l][r] = graph[r][l] = true;
63+
links.push({source: points[l], target: points[r]});
64+
});
65+
return links;
66+
};
67+
68+
voronoi.triangles = function(data) {
69+
var points = [],
70+
point,
71+
fx = d3_functor(x),
72+
fy = d3_functor(y),
73+
d,
74+
i,
75+
n = data.length;
76+
for (i = 0; i < n; ++i) {
77+
point = [+fx.call(this, d = data[i], i), +fy.call(this, d, i)];
78+
point.data = d;
79+
points.push(point);
80+
}
81+
return d3.geom.delaunay(points);
82+
};
83+
4784
return voronoi;
4885
};

‎test/layout/voronoi-test.js‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -60,6 +60,25 @@ suite.addBatch({
6060
"the returned cells' data points back to the input data": function(cells) {
6161
assert.deepEqual(cells.map(function(cell) { return cell.data; }), [[200, 200], [760, 300]]);
6262
}
63+
},
64+
"links": {
65+
"for two points": function(v) {
66+
assert.deepEqual(v.links([[200, 200], [760, 300]]), [
67+
{source: [200, 200], target: [760, 300]}]);
68+
},
69+
"for three points": function(v) {
70+
assert.deepEqual(v.links([[200, 200], [500, 250], [760, 300]]), [
71+
{source: [200, 200], target: [760, 300]},
72+
{source: [500, 250], target: [760, 300]},
73+
{source: [200, 200], target: [500, 250]}]);
74+
}
75+
},
76+
"triangles": {
77+
"for three points": function(v) {
78+
assert.deepEqual(v.triangles([[200, 200], [500, 250], [760, 300]]).map(function(d) {
79+
return d.map(function(d) { return d.data; });
80+
}), [[ [200, 200], [760, 300], [500, 250]]]);
81+
}
6382
}
6483
},
6584

0 commit comments

Comments
 (0)