forked from carriebostock/bost.ocks.org
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path404.html
130 lines (100 loc) · 4.18 KB
/
404.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
<!DOCTYPE html>
<meta charset="utf-8">
<title>File Not Found</title>
<style>
@import url(/mike/style.css?20120427);
svg {
border: solid 1px #ccc;
}
rect {
fill: none;
pointer-events: all;
}
</style>
<header>
<aside>April 28, 2012</aside>
<a href="/mike/">Mike Bostock</a>
</header>
<h1>File Not Found</h1>
<script src="http://d3js.org/d3.v2.js?2.9.1"></script>
<script>
var radius = 32,
margin = {top: -radius, right: -radius, bottom: -radius, left: -radius},
width = 960 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom;
var svg = d3.select("body").append("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.left + margin.right)
.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
var quadtree = d3.geom.quadtree([], 0, 0, width, height),
findClosest = finder(quadtree, radius * 2);
d3.timer(add(5, 2500, 50));
// Add m new circles per tick, stopping when we have n circles.
// When adding a circle, pick the best of k candidates.
function add(m, n, k) {
return function() {
for (var j = 0; j < m && --n >= 0; ++j) {
var best = null;
// Create k candidates, picking the best (farthest away).
for (var i = 0; i < k; ++i) {
var candidate = {x: Math.random() * width, y: Math.random() * height};
findClosest(candidate);
if (!best || candidate.radius > best.radius) best = candidate;
}
best.radius = Math.min(radius, (Math.random() + 1) / 2 * best.radius);
quadtree.add(best);
svg.append("circle")
.attr("cx", best.x)
.attr("cy", best.y)
.style("fill-opacity", (Math.random() + .5) / 2)
.transition()
.attr("r", best.radius);
}
return !n;
};
}
// Find the closest circle to the candidate, searching at most r away.
function finder(quadtree, r) {
return function(candidate) {
var rx1 = candidate.x - r,
rx2 = candidate.x + r,
ry1 = candidate.y - r,
ry2 = candidate.y + r;
candidate.radius = Infinity;
quadtree.visit(function(quad, x1, y1, x2, y2) {
if (quad.point) {
var dx = candidate.x - quad.point.x,
dy = candidate.y - quad.point.y,
radius = Math.max(0, Math.sqrt(dx * dx + dy * dy) - quad.point.radius);
if (radius < candidate.radius) candidate.radius = radius;
}
return x1 > rx2 || x2 < rx1 || y1 > ry2 || y2 < ry1;
});
};
}
</script>
<p>Unfortunately, the page you were looking for does not appear to exist. Instead, here is a pleasing demonstration of <b>Mitchell’s best-candidate</b> algorithm.
<p>The best-candidate algorithm generates a new random sample by creating <i>k</i> candidate samples and picking the one farthest from previous samples. The algorithm approximates <a href="http://www.cs.virginia.edu/~gfx/pubs/antimony/">Poisson-disc sampling</a>, producing a more natural appearance (better blue noise spectral characteristics) than uniform random sampling. This has a variety of useful applications in computer graphics, such as reducing <a href="http://en.wikipedia.org/wiki/Moiré_pattern">Moiré patterns</a> in supersampling raytracers.
<p>In pseudo-code:
<pre><code>function bestCandidate(k) {
var bestDistance = -1,
bestCandidate;
// Generate k random candidates.
for (var i = 0; i < k; ++i) {
var c = [Math.random() * width, Math.random() * height];
// Determine if the current candidate is the best.
var d = distance(c);
if (d > bestDistance) {
bestDistance = d;
bestCandidate = c;
}
}
return bestCandidate;
}</code></pre>
<p>This implementation depends on an external function <code>distance</code> which computes the minimum distance between the new candidate <code>c</code> and all previous samples. The naïve implementation is expensive, since it iterates over all previous samples for each new sample! Fortunately, data structures such as <a href="http://en.wikipedia.org/wiki/Quadtree">quadtrees</a> can accelerate these tests by skipping samples that are far away.
<footer>
<aside>April 28, 2012</aside>
<a href="/mike/">Mike Bostock</a>
</footer>
<script src="/mike/highlight.min.js"></script>