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
|
'use strict';
import Voronoi from './3rdparty/rhill-voronoi-core.js';
import { useAverage } from './Util.js';
import { QuadTree } from './Geometry.js';
/* from here on up, we always assume that points live in the range [(0,0), (1,1)) */
function lloydRelax(point_set, density) {
/* setup quadtree and averages */
let tree = new QuadTree(1,1);
let averages = {};
for (let i=0; i<point_set.length; i++) {
const point = point_set[i];
point.index = i;
tree.insert(point);
let [avg, append] = useAverage();
const cent_x = { avg, append };
[avg, append] = useAverage();
const cent_y = { avg, append };
averages[i] = { cent_x, cent_y };
}
/* compute average centroids */
for (let x=0; x<1; x += 1/density) {
for (let y=0; y<1; y += 1/density) {
const point = { x, y };
const closest = tree.closest(point);
const { cent_x, cent_y } = averages[closest.index];
cent_x.append(point.x);
cent_y.append(point.y);
}
}
/* return centroid points */
const result = [];
for (let i=0; i<point_set.length; i++) {
const point = { x: averages[i].cent_x.avg(), y: averages[i].cent_y.avg() };
result.push(point);
}
return result;
}
class Terrain {
constructor() {
const N_SEED_POINTS = 2**14;
const N_RELAX_ITERATIONS = 1;
const RELAX_DENSITY = 400;
const randomPoint = () => ({x: Math.random(), y: Math.random()});
let seed_points = [];
for (let i=0; i<N_SEED_POINTS; i++) seed_points.push(randomPoint());
for (let i=0; i<N_RELAX_ITERATIONS; i++)
lloydRelax(seed_points, RELAX_DENSITY);
const v = new Voronoi();
this.graph = v.compute(seed_points, {xl: 0, xr: 1, yt: 0, yb: 1});
this.tree = new QuadTree(1,1);
for (let v of this.graph.vertices) this.tree.insert(v);
}
renderGrid(ct) {
ct.lineWidth = 0.001;
for (let edge of this.graph.edges) {
ct.beginPath();
ct.moveTo(edge.va.x, edge.va.y);
ct.lineTo(edge.vb.x, edge.vb.y);
ct.closePath();
ct.stroke();
}
}
}
export { lloydRelax };
export default Terrain;
|
