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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
#include <stdio.h>
#include <math.h>
#include "tectonics.h"
#include "geometry.h"
#include "util.h"
static void rebuild_tree(struct world_t *world)
{
// remove any existing tree
if (world->tree.nw != NULL) {
quadtree_free(world->tree.nw);
quadtree_free(world->tree.ne);
quadtree_free(world->tree.sw);
quadtree_free(world->tree.se);
world->tree.nw = NULL;
world->tree.ne = NULL;
world->tree.sw = NULL;
world->tree.se = NULL;
}
world->tree.id = -1;
// build a new tree
for (int i=0; i<world->n_points; i++) {
quadtree_insert(&(world->tree), world->points, i);
}
}
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
struct centroid_t {
double x, y;
int updates;
};
// monte-carlo lloyd's algorithm
static void relax_points(struct world_t *world, int iterations)
{
// centroids to compute
struct centroid_t *centroid =
malloc(sizeof(struct centroid_t) * world->n_points);
// initialize centroids with current locations
for (int i=0; i<world->n_points; i++) {
struct point_t *pt = world->points + i;
struct centroid_t *c = centroid + i;
c->x = pt->x;
c->y = pt->y;
c->updates = 1;
}
// approximate centroids
for (int i=0; i<iterations; i++) {
printf("%02f%%\n", 100*((double)i+1)/iterations);
// generate a random point and find the closest
// terrain point
double x = rand01();
double y = rand01();
int closest = quadtree_get_closest(&(world->tree),
world->points,
(struct point_t){x, y});
if (closest == -1) {
printf("WARN: bad closest point!\n");
}
else {
// average the centroid towards that random point
struct centroid_t *c = centroid + closest;
int u = c->updates;
c->x = (u*c->x + x)/(u+1);
c->y = (u*c->y + y)/(u+1);
c->updates += 1;
}
}
// update positions from centroids
for (int i=0; i<world->n_points; i++) {
struct point_t *pt = world->points + i;
struct centroid_t *c = centroid + i;
pt->x = c->x;
pt->y = c->y;
}
rebuild_tree(world);
free(centroid);
}
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
void create_world(struct world_t *world, int n_points)
{
world->n_points = n_points;
world->points = malloc(sizeof(struct point_t) * n_points);
if (world->points == NULL) {
fprintf(stderr,
"ERROR: failed to allocate %d points\n",
n_points);
return;
}
struct point_t center = { 0.5, 0.5 };
world->tree = quadtree_new_node(center, 0.5);
for (int i=0; i<n_points; i++) {
struct point_t *pt = world->points + i;
pt->x = rand01();
pt->y = rand01();
//quadtree_insert(&(world->tree), world->points, i);
}
rebuild_tree(world);
for (int i=0; i<3; i++)
relax_points(world, 10*world->n_points);
}
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
void free_world(struct world_t *world)
{
if (world->tree.nw != NULL) {
quadtree_free(world->tree.nw);
quadtree_free(world->tree.ne);
quadtree_free(world->tree.sw);
quadtree_free(world->tree.se);
}
free(world->points);
}
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
void render_world(cairo_t *cr, struct world_t *world)
{
int width, height;
get_cairo_size(cr, &width, &height);
double r = ((double)width) / (100*sqrt(world->n_points));
cairo_set_source_rgba(cr, 1, 0, 0, 1);
for (int i=0; i<world->n_points; i++) {
struct point_t *pt = world->points + i;
double xc = pt->x * width;
double yc = pt->y * height;
cairo_arc(cr, xc, yc, r, 0, 2*M_PI);
cairo_stroke(cr);
}
//draw_quadtree(cr, &(world->tree));
}
|
