-
Notifications
You must be signed in to change notification settings - Fork 0
/
voronoi.c
147 lines (136 loc) · 4.55 KB
/
voronoi.c
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
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#include "voronoi.h"
float minkowski_distance(int ay, int ax, int by, int bx, int p){
switch (p){
case 1:
return abs(by - ay) + abs(bx - ax);
case 2:
return sqrt(pow(by - ay, 2) + pow(bx - ax, 2));
default:
return pow(pow(abs(ay - by), p) + pow(abs(ax - bx), p), 1./p);
}
}
site * get_center_array(int size, int divisions){
site * center_array = (site *)calloc(pow(4, divisions), sizeof(site));
int pitch = (size - 1)/pow(2, divisions);
int index = 0;
for (int i = 0; i < size - pitch; i += pitch){
for (int j = 0; j < size - pitch; j += pitch){
center_array[index].y = (2 * i + pitch)/2;
center_array[index].x = (2 * j + pitch)/2;
index ++;
}
}
return center_array;
}
void move_centers(int seed, site * center_array, int center_quantity){
srand(seed);
bool movement_down;
bool movement_right;
int max_movement = center_array[0].x;
for (int i = 0; i < center_quantity; i ++){
movement_down = rand()%101 > 50;
movement_right = rand()%101 > 50;
if (movement_down){
center_array[i].y += rand()%max_movement;
}
else{
center_array[i].y -= rand()%max_movement;
}
if (movement_right){
center_array[i].x += rand()%max_movement;
}
else{
center_array[i].x -= rand()%max_movement;
}
}
}
short get_closest_site(int y, int x, site * sites, int site_quantity, int p){
float min;
short index;
float * distances = (float *)calloc(site_quantity, sizeof(float));
min = minkowski_distance(y, x, sites[0].y, sites[0].x, p);
index = 0;
for (int i = 0; i < site_quantity; i++){
distances[i] = minkowski_distance(y, x, sites[i].y, sites[i].x, p);
if (distances[i] < min){
min = distances[i];
index = i;
}
}
return index;
}
void voronoi_diagram(short ** map, int size, site * sites, int site_quantity, int p){
for (int i = 0; i < size; i ++){
for (int j = 0; j < size; j ++){
map[i][j] = get_closest_site(j, i, sites, site_quantity, p);
}
}
}
void worley_noise(short ** diagram, float ** map, int size, site * sites, int site_quantity, int p){
short current_site_id;
float current_distance;
float * max_distances = (float *)calloc(site_quantity, sizeof(float));
for (int i = 0; i < size; i ++){
for (int j = 0; j < size; j ++){
current_site_id = diagram[i][j];
current_distance = minkowski_distance(i, j, sites[current_site_id].y, sites[current_site_id].x, p);
if (current_distance > max_distances[current_site_id]){
max_distances[current_site_id] = current_distance;
}
}
}
for (int i = 0; i < size; i ++){
for (int j = 0; j < size; j ++){
current_site_id = diagram[i][j];
current_distance = minkowski_distance(i, j, sites[current_site_id].y, sites[current_site_id].x, p);
map[i][j] = current_distance/max_distances[current_site_id];
}
}
free(max_distances);
}
short ** generate_voronoi_diagram(int seed, int size, int divisions, int p){
srand(seed);
short ** map = (short **)calloc(size, sizeof(short *));
for (int i = 0; i < size; i ++){
map[i] = (short *)calloc(size, sizeof(short));
}
site * centarr = get_center_array(size, divisions);
int cent_q = pow(4, divisions);
move_centers(seed, centarr, cent_q);
voronoi_diagram(map, size, centarr, cent_q, p);
free(centarr);
return map;
}
float ** generate_worley_noise(int seed, int size, int divisions, int p){
srand(seed);
int current_site_id = 0;
float current_distance = 0;
site * centarr = get_center_array(size, divisions);
int cent_q = pow(4, divisions);
move_centers(seed, centarr, cent_q);
float * distarr = (float *)calloc(cent_q, sizeof(float));
float ** map = (float **)calloc(size, sizeof(float *));
for (int i = 0; i < size; i ++){
map[i] = (float *)calloc(size, sizeof(float));
for (int j = 0; j < size; j ++){
current_site_id = get_closest_site(i, j, centarr, cent_q, p);
current_distance = minkowski_distance(i, j, centarr[current_site_id].y, centarr[current_site_id].x, p);
if (current_distance > distarr[current_site_id]){
distarr[current_site_id] = current_distance;
}
}
}
for (int i = 0; i < size; i ++){
for (int j = 0; j < size; j ++){
current_site_id = get_closest_site(i, j, centarr, cent_q, p);
current_distance = minkowski_distance(i, j, centarr[current_site_id].y, centarr[current_site_id].x, p);
map[i][j] = (distarr[current_site_id] - current_distance)/distarr[current_site_id];
}
}
free(centarr);
free(distarr);
return map;
}