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
|
#include <stdio.h>
#include <math.h>
#include "tectonics.h"
struct centroid_t {
double x, y;
int updates;
};
static void rebuild_tree(struct world_t *world)
{
if (world->tree.nw != NULL) {
free_tree(world->tree.nw);
free_tree(world->tree.ne);
free_tree(world->tree.sw);
free_tree(world->tree.se);
world->tree.nw = NULL;
world->tree.ne = NULL;
world->tree.sw = NULL;
world->tree.se = NULL;
}
world->tree.id = -1;
for (int i=0; i<world->n_points; i++) {
insert(&(world->tree), world->points, i);
}
}
static void relax_points(struct world_t *world, int iterations)
{
struct centroid_t *centroid =
malloc(sizeof(struct centroid_t) * world->n_points);
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;
}
for (int i=0; i<iterations; i++) {
printf("%02f%%\n", 100*((double)i+1)/iterations);
double x = rand01();
double y = rand01();
int closest = get_closest(&(world->tree),
world->points,
(struct point_t){x, y});
if (closest == -1) {
printf("WARN: bad closest point!\n");
}
else {
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;
}
}
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 = 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();
//insert(&(world->tree), world->points, i);
}
rebuild_tree(world);
for (int i=0; i<10; i++)
relax_points(world, 100000);
}
void free_world(struct world_t *world)
{
if (world->tree.nw != NULL) {
free_tree(world->tree.nw);
free_tree(world->tree.ne);
free_tree(world->tree.sw);
free_tree(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));
}
|
