Skip to content

Commit bcf37e4

Browse files
mbostockmbostock
committed
Generate Delaunay from Voronoi.
1 parent 841f354 commit bcf37e4

6 files changed

Lines changed: 109 additions & 186 deletions

File tree

‎examples/delaunay/delaunay.html‎

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
55
<title>Delaunay Triangulation</title>
66
<script type="text/javascript" src="../../d3.js"></script>
7-
<script type="text/javascript" src="delaunay.js"></script>
7+
<script type="text/javascript" src="../../lib/jit/voronoi.min.js"></script>
88
<style type="text/css">
99

1010
@import url("../../lib/colorbrewer/colorbrewer.css");
@@ -22,8 +22,8 @@
2222
var w = 960,
2323
h = 500;
2424

25-
var vertices = d3.range(500).map(function() {
26-
return [~~(w * Math.random()), ~~(h * Math.random())];
25+
var vertices = d3.range(500).map(function(d) {
26+
return [Math.random() * w, Math.random() * h];
2727
});
2828

2929
var svg = d3.select("body")
@@ -32,11 +32,12 @@
3232
.attr("height", h)
3333
.attr("class", "PiYG");
3434

35-
svg.selectAll("path")
35+
svg.append("svg:g")
36+
.selectAll("path")
3637
.data(delaunay(vertices))
3738
.enter("svg:path")
3839
.attr("class", function(d, i) { return "q" + (i % 9) + "-9"; })
39-
.attr("d", function(d) { return "M" + d[0] + "L" + d[1] + "L" + d[2] + "Z"; });
40+
.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
4041

4142
</script>
4243
</body>

‎examples/delaunay/delaunay.js‎

Lines changed: 0 additions & 120 deletions
This file was deleted.

‎examples/index.html‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,16 +12,19 @@
1212
<li><a href="calendar/dji.html">calendar-dji</a></li>
1313
<li><a href="calendar/vix.html">calendar-vix</a></li>
1414
<li><a href="choropleth/choropleth.html">choropleth</a></li>
15+
<li><a href="delaunay/delaunay.html">delaunay</a></li>
1516
<li><a href="donut/donut.html">donut</a></li>
1617
<li><a href="dot/dot.html">dot</a></li>
1718
<li><a href="force/force.html">force</a></li>
1819
<li><a href="horizon/horizon.html">horizon</a></li>
1920
<li><a href="line/line.html">line</a></li>
2021
<li><a href="pie/pie.html">pie</a></li>
2122
<li><a href="pie/pie-transition.html">pie-transition</a></li>
23+
<li><a href="splom/splom.html">splom</a></li>
2224
<li><a href="stream/stream.html">stream</a></li>
2325
<li><a href="stream/stack.html">stack</a></li>
2426
<li><a href="symbol-map/symbol-map.html">symbol-map</a></li>
27+
<li><a href="voronoi/voronoi.html">voronoi</a></li>
2528
<li><a href="zoom/zoom.html">zoom</a></li>
2629
</ul>
2730
</body>

‎lib/jit/voronoi.js‎

Lines changed: 87 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -7,42 +7,90 @@
77
* @returns polygons [[[x1, y1], [x2, y2], …], …]
88
*/
99
voronoi = function(vertices) {
10-
var polygons = vertices.map(function() { return []; }),
11-
opposite = {"l": "r", "r": "l"};
10+
var polygons = vertices.map(function() { return []; });
1211

1312
// Note: we expect the caller to clip the polygons, if needed.
14-
var Canvas = {
15-
plotEdge: function(e) {
16-
var s1,
17-
s2,
18-
x1,
19-
x2,
20-
y1,
21-
y2;
22-
if (e.a == 1 && e.b >= 0) {
23-
s1 = e.ep["r"];
24-
s2 = e.ep["l"];
25-
} else {
26-
s1 = e.ep["l"];
27-
s2 = e.ep["r"];
28-
}
29-
if (e.a == 1) {
30-
y1 = s1 ? s1.y : -1e6;
31-
x1 = e.c - e.b * y1;
32-
y2 = s2 ? s2.y : 1e6;
33-
x2 = e.c - e.b * y2;
34-
} else {
35-
x1 = s1 ? s1.x : -1e6;
36-
y1 = e.c - e.a * x1;
37-
x2 = s2 ? s2.x : 1e6;
38-
y2 = e.c - e.a * x2;
39-
}
40-
var v1 = [x1, y1],
41-
v2 = [x2, y2];
42-
polygons[e.region["l"].index].push(v1, v2);
43-
polygons[e.region["r"].index].push(v1, v2);
13+
voronoi_tessellate(vertices, function(e) {
14+
var s1,
15+
s2,
16+
x1,
17+
x2,
18+
y1,
19+
y2;
20+
if (e.a == 1 && e.b >= 0) {
21+
s1 = e.ep["r"];
22+
s2 = e.ep["l"];
23+
} else {
24+
s1 = e.ep["l"];
25+
s2 = e.ep["r"];
4426
}
45-
};
27+
if (e.a == 1) {
28+
y1 = s1 ? s1.y : -1e6;
29+
x1 = e.c - e.b * y1;
30+
y2 = s2 ? s2.y : 1e6;
31+
x2 = e.c - e.b * y2;
32+
} else {
33+
x1 = s1 ? s1.x : -1e6;
34+
y1 = e.c - e.a * x1;
35+
x2 = s2 ? s2.x : 1e6;
36+
y2 = e.c - e.a * x2;
37+
}
38+
var v1 = [x1, y1],
39+
v2 = [x2, y2];
40+
polygons[e.region["l"].index].push(v1, v2);
41+
polygons[e.region["r"].index].push(v1, v2);
42+
});
43+
44+
// Reconnect the polygon segments into counterclockwise loops.
45+
return polygons.map(function(polygon, i) {
46+
var cx = vertices[i][0],
47+
cy = vertices[i][1];
48+
polygon.forEach(function(v) {
49+
v.angle = Math.atan2(v[0] - cx, v[1] - cy);
50+
});
51+
return polygon.sort(function(a, b) {
52+
return a.angle - b.angle;
53+
}).filter(function(d, i) {
54+
return !i || (d.angle - polygon[i - 1].angle > 1e-10);
55+
});
56+
});
57+
};
58+
59+
/**
60+
* @param vertices [[x1, y1], [x2, y2], …]
61+
* @returns triangles [[[x1, y1], [x2, y2], [x3, y3]], …]
62+
*/
63+
delaunay = function(vertices) {
64+
var edges = vertices.map(function() { return []; }),
65+
triangles = [];
66+
67+
// Use the Voronoi tessellation to determine Delaunay edges.
68+
voronoi_tessellate(vertices, function(e) {
69+
edges[e.region["l"].index].push(vertices[e.region["r"].index]);
70+
});
71+
72+
// Reconnect the edges into counterclockwise triangles.
73+
edges.forEach(function(edge, i) {
74+
var v = vertices[i],
75+
cx = v[0],
76+
cy = v[1];
77+
edge.forEach(function(v) {
78+
v.angle = Math.atan2(v[0] - cx, v[1] - cy);
79+
});
80+
edge.sort(function(a, b) {
81+
return a.angle - b.angle;
82+
});
83+
for (var j = 0, m = edge.length - 1; j < m; j++) {
84+
triangles.push([v, edge[j], edge[j + 1]]);
85+
}
86+
});
87+
88+
return triangles;
89+
};
90+
91+
var voronoi_opposite = {"l": "r", "r": "l"};
92+
93+
function voronoi_tessellate(vertices, callback) {
4694

4795
var Sites = {
4896
list: vertices
@@ -125,7 +173,7 @@ voronoi = function(vertices) {
125173
rightRegion: function(he) {
126174
return he.edge == null
127175
? Sites.bottomSite
128-
: he.edge.region[opposite[he.side]];
176+
: he.edge.region[voronoi_opposite[he.side]];
129177
}
130178
};
131179

@@ -244,8 +292,8 @@ voronoi = function(vertices) {
244292

245293
endPoint: function(edge, side, site) {
246294
edge.ep[side] = site;
247-
if (!edge.ep[opposite[side]]) return;
248-
Canvas.plotEdge(edge);
295+
if (!edge.ep[voronoi_opposite[side]]) return;
296+
callback(edge);
249297
},
250298

251299
distance: function(s, t) {
@@ -359,7 +407,7 @@ voronoi = function(vertices) {
359407
e = Geom.bisect(bot, top);
360408
bisector = EdgeList.createHalfEdge(e, pm);
361409
EdgeList.insert(llbnd, bisector);
362-
Geom.endPoint(e, opposite[pm], v);
410+
Geom.endPoint(e, voronoi_opposite[pm], v);
363411
p = Geom.intersect(llbnd, bisector);
364412
if (p) {
365413
EventQueue.del(llbnd);
@@ -377,20 +425,6 @@ voronoi = function(vertices) {
377425
for (lbnd = EdgeList.right(EdgeList.leftEnd);
378426
lbnd != EdgeList.rightEnd;
379427
lbnd = EdgeList.right(lbnd)) {
380-
Canvas.plotEdge(lbnd.edge);
428+
callback(lbnd.edge);
381429
}
382-
383-
// Reconnect the polygon segments into counterclockwise loops.
384-
return polygons.map(function(polygon, i) {
385-
var cx = vertices[i][0],
386-
cy = vertices[i][1];
387-
polygon.forEach(function(v) {
388-
v.angle = Math.atan2(v[0] - cx, v[1] - cy);
389-
});
390-
return polygon.sort(function(a, b) {
391-
return a.angle - b.angle;
392-
}).filter(function(d, i) {
393-
return !i || (d.angle - polygon[i - 1].angle > 1e-10);
394-
});
395-
});
396-
};
430+
}

‎lib/jit/voronoi.min.js‎

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

‎src/externs.js‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -168,3 +168,7 @@ d3.time = {
168168
format: 1,
169169
parse: 1
170170
};
171+
172+
// jit
173+
var voronoi,
174+
delaunay;

0 commit comments

Comments
 (0)