9 #include <ucw/eltpool.h>
14 #include "lab-utils.h"
15 #include "lab-bitmaps.h"
16 #include "lab-evolution.h"
26 static void evolution_compute_sizes(void);
28 static void make_population(void);
29 static void rank_population(void);
31 static bool shall_terminate(void);
32 static void breed(void);
33 static void mutate(void);
34 static void elite(void);
36 static void hide_segment_labels(struct individual *individual);
38 static void init_placement(struct placement *p, struct individual *individual, struct request *r);
40 static void init_individual(struct individual *i);
41 static int cmp_individual(const void *a, const void *b);
42 static void plan_individual(struct individual *individual);
43 static void clear_individual(struct individual *individual);
45 static struct individual **perform_crossover(struct individual *parent1, struct individual *parent2);
46 static void perform_mutation(struct individual *individual);
47 static void copy_individual(struct individual *src, struct individual *dest);
49 static double gen_movement(void);
50 static double gen_movement_uniform(void);
51 static void move_symbol(struct placement *p);
52 static void move_symbol_point(struct placement *p);
53 static void move_symbol_segment(struct placement *p);
55 static void gen_coords(struct placement *p);
56 static void gen_coords_point(struct placement *p);
57 static void gen_coords_segment(struct placement *p);
58 static void gen_coords_area(struct placement *p);
60 static void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr);
62 static int individual_overlap(struct individual *individual);
64 static double get_distance(struct placement *p);
65 static double individual_distances(struct individual *individual);
67 static double get_omittment(struct placement *p);
68 static double individual_omittment(struct individual *individual);
70 static void clear_population(struct individual **pop);
72 static void dump_penalties(struct individual **population);
74 static struct eltpool *ep_individuals;
76 static int conf_pop_size = 200, conf_fit_size = 1, conf_term_cond = TERM_COND_ITERATIONS;
78 static double conf_penalty_bound = 100, conf_stagnation_bound = 10;
79 static int conf_iteration_limit = 200;
81 static int breed_pop_size;
82 static int breed_rbest_size;
84 static int mutate_pop_size;
85 static int mutate_rbest_size;
87 static int elite_pop_size;
90 static int move_min = 0;
91 static int move_max = 5;
93 static double conf_breed_pop_size = 0.45, conf_breed_rbest = 1,
94 conf_mutate_children, conf_mutate_children_prob = 0.6,
95 conf_mutate_pop_size = 0.45, conf_mutate_rbest = 1,
96 conf_mutate_move_bound = 0.1, conf_mutate_regen_bound = 0.05, conf_mutate_chvar_bound = 0.1,
97 conf_elite_pop_size = 0.1;
99 static struct cf_section evolution_cf = {
101 CF_INT("PopSize", &conf_pop_size),
102 CF_INT("FitSize", &conf_fit_size),
103 CF_INT("TermCond", &conf_term_cond),
104 CF_DOUBLE("PenaltyBound", &conf_penalty_bound),
105 CF_DOUBLE("StagnationBound", &conf_stagnation_bound),
106 CF_INT("IterationLimit", &conf_iteration_limit),
107 CF_DOUBLE("BreedPopSize", &conf_breed_pop_size),
108 CF_DOUBLE("BreedNumBest", &conf_breed_rbest),
109 CF_DOUBLE("MutateChild", &conf_mutate_children_prob),
110 CF_DOUBLE("MutatePopSize", &conf_mutate_pop_size),
111 CF_DOUBLE("MutateNumBest", &conf_mutate_rbest),
112 CF_DOUBLE("MutateMoveBound", &conf_mutate_move_bound),
113 CF_DOUBLE("MutateRegenBound", &conf_mutate_regen_bound),
114 CF_DOUBLE("MutateChvarBound", &conf_mutate_chvar_bound),
115 CF_DOUBLE("ElitePopSize", &conf_elite_pop_size),
120 static struct placement dummy_placement;
122 static struct individual **population1;
123 static struct individual **population2;
125 static int old_best = INT_MAX;
126 static int iteration = 0;
131 void evolution_conf(void)
133 cf_declare_section("Evolution", &evolution_cf, 0);
136 void evolution_init(void)
138 evolution_compute_sizes();
143 ep_individuals = ep_new(sizeof(struct individual), 1);
145 GARY_INIT(population1, conf_pop_size);
146 GARY_INIT(population2, conf_pop_size);
150 qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);
152 if (dbg_evolution >= VERBOSITY_GENERAL)
154 printf("Penalties after initialization\n");
155 dump_penalties(population1);
158 while (! shall_terminate())
162 printf("\n*** Iteration %d ***\n", iteration);
168 struct individual **swp = population1;
169 population1 = population2;
172 clear_population(population2);
176 if (dbg_evolution >= VERBOSITY_INDIVIDUAL)
178 printf("Penalties before sort\n");
179 dump_penalties(population1);
182 DEBUG(dbg_evolution, VERBOSITY_GENERAL, "Sorting population\n");
183 qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);
185 if (dbg_evolution >= VERBOSITY_GENERAL)
187 printf("Penalties after sort\n");
188 dump_penalties(population1);
191 old_best = population1[0]->penalty;
194 if (dbg_overlaps >= VERBOSITY_GENERAL)
195 dump_bitmaps(population1[0]);
197 plan_individual(population1[0]);
201 static void evolution_compute_sizes(void)
203 breed_pop_size = conf_breed_pop_size * conf_pop_size;
204 breed_rbest_size = conf_breed_rbest * conf_pop_size;
205 if (dbg_evolution >= VERBOSITY_GENERAL)
207 printf("Breeding parameters:\n");
208 printf(" %d individuals are created\n", breed_pop_size);
209 printf(" %d best individuals in old population are considered\n", breed_rbest_size);
212 mutate_pop_size = conf_mutate_pop_size * conf_pop_size;
213 mutate_rbest_size = conf_mutate_rbest * conf_pop_size;
214 if (dbg_evolution >= VERBOSITY_GENERAL)
216 printf("Mutation parameters:\n");
217 printf(" %d individuals are created\n", mutate_pop_size);
218 printf(" %d best individuals in old population are considered\n", mutate_rbest_size);
221 elite_pop_size = conf_elite_pop_size * conf_pop_size;
222 if (dbg_evolution >= VERBOSITY_GENERAL)
224 printf("Elitism parameters:\n");
225 printf(" %d best individuals are copied\n", elite_pop_size);
228 if (breed_pop_size + mutate_pop_size + elite_pop_size != conf_pop_size)
232 elite_pop_size += conf_pop_size - (breed_pop_size + mutate_pop_size + elite_pop_size);
236 fprintf(stderr, "Breeding + mutation + elitism won't create correct number of individuals\n");
237 fprintf(stderr, "Please fix conf_breed_pop_size, conf_mutate_pop_size and conf_elite_pop_size parameters\n");
244 void dump_individual(struct individual *individual)
246 printf("*** Individual dump\n");
247 printf("(There are %d requests)\n", num_requests);
249 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
251 struct placement *p = &(individual->placements[i]);
253 switch (p->request->type)
256 printf("Point at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_point *) p->request)->zindex);
259 struct request_line *rl = (struct request_line *) p->request;
261 dump_label(rl->sections[0].segments[0].label);
263 case REQUEST_SECTION: ;
266 case REQUEST_SEGMENT: ;
267 if (p->variant_used >= 0)
268 printf("Segment placed at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_segment *) p->request)->zindex);
270 printf("Segment not placed\n");
273 struct request_area *ra = (struct request_area *) p->request;
274 printf("Area label ");
275 dump_label(ra->label);
276 printf(" at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_area *) p->request)->zindex);
279 ASSERT(p->request->type != 0);
282 printf("\nTotal penalty: %d\n", individual->penalty);
285 static void plan_individual(struct individual *individual)
287 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
289 struct symbol *s = NULL;
290 z_index_t zindex = 0;
292 if (individual->placements[i].variant_used < 0)
294 printf("Skipping placement of request %d\n", individual->placements[i].request->ind);
297 if (individual->placements[i].variant_used < 0) continue;
298 switch (individual->placements[i].request->type)
300 case REQUEST_POINT: ;
301 struct request_point *rp = (struct request_point *) individual->placements[i].request;
305 case REQUEST_SEGMENT: ;
306 struct request_segment *rs = (struct request_segment *) individual->placements[i].request;
313 struct request_area *ra = (struct request_area *) individual->placements[i].request;
318 ASSERT(individual->placements[i].request != REQUEST_INVALID);
322 DEBUG(dbg_plan, VERBOSITY_PLACEMENT, "Will plan symbol of request %d at [%.2f; %.2f] on %u\n", individual->placements[i].request->ind, individual->placements[i].x, individual->placements[i].y, zindex);
324 if (s) switch (s->type)
326 case SYMBOLIZER_POINT: ;
327 struct sym_point *sp = (struct sym_point *) s;
328 sp->x = individual->placements[i].x;
329 sp->y = individual->placements[i].y;
330 sym_plan((struct symbol *) sp, zindex);
332 case SYMBOLIZER_ICON: ;
333 struct sym_icon *si = (struct sym_icon *) s;
334 si->sir.x = individual->placements[i].x;
335 si->sir.y = individual->placements[i].y;
336 sym_plan((struct symbol *) si, zindex);
338 case SYMBOLIZER_TEXT: ;
339 struct sym_text *st = (struct sym_text *) s;
340 st->x = individual->placements[i].x;
341 st->y = individual->placements[i].y;
342 st->next_duplicate = NULL;
343 DEBUG(dbg_plan, VERBOSITY_PLACEMENT, "Planning text %s at [%.2f; %.2f] on %u, with rotation %.2f\n", osm_val_decode(st->text), st->x, st->y, zindex, st->rotate);
344 sym_plan((struct symbol *) st, zindex);
347 ASSERT(s->type != SYMBOLIZER_INVALID);
352 static void dump_penalties(struct individual **population)
354 for (int i=0; i<conf_pop_size; i++)
356 printf("Individual %d has penalty %d\n", i, population[i]->penalty);
360 static void make_population(void)
362 for (int i=0; i<conf_pop_size; i++)
364 num_placements = 0; // FIXME: This IS a terrible HACK
365 struct individual *i2 = ep_alloc(ep_individuals);
369 DEBUG(dbg_init, VERBOSITY_INDIVIDUAL, "Making individual %d\n", i);
370 struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
371 population1[i] = individual;
374 for (uns j=0; j<GARY_SIZE(requests_point); j++)
376 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_point[j]);
379 for (uns j=0; j<GARY_SIZE(requests_line); j++)
381 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j]);
383 for (uns k=0; k<GARY_SIZE(requests_line[j].sections); k++)
385 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k]);
387 for (uns l=0; l<GARY_SIZE(requests_line[j].sections[k].segments); l++)
389 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k].segments[l]);
394 for (uns j=0; j<GARY_SIZE(requests_area); j++)
396 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_area[j]);
399 hide_segment_labels(individual);
401 ASSERT(p == num_requests);
405 static bool shall_terminate(void)
407 switch (conf_term_cond)
409 case TERM_COND_PENALTY:
410 return (population1[0]->penalty < conf_penalty_bound);
411 case TERM_COND_STAGNATION:
412 return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
413 case TERM_COND_ITERATIONS:
414 return (iteration >= conf_iteration_limit);
416 fprintf(stderr, "Warning: No termination condition is set, terminating\n");
421 static void breed(void)
425 struct individual **breed_buffer;
426 while (i < breed_pop_size)
428 int parent1 = randint(0, breed_rbest_size);
429 int parent2 = randint(0, breed_rbest_size);
430 DEBUG(dbg_breeding, VERBOSITY_INDIVIDUAL, "Will breed %d and %d\n", parent1, parent2);
432 breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
433 population2[pop2_ind++] = breed_buffer[0];
434 population2[pop2_ind++] = breed_buffer[1];
440 static struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
442 struct individual **buffer = xmalloc(2*sizeof(struct individual));
443 struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
444 struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
447 GARY_INIT_ZERO(processed, GARY_SIZE(parent1->placements));
449 for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
451 if (! processed[parent1->placements[i].ind])
453 DEBUG(dbg_breeding, VERBOSITY_PLACEMENT, "Creating symbol closure for placement %u\n", i);
455 struct placement **clos_symbols = get_closure(&(parent1->placements[i]));
456 int x = randint(0, 2);
460 DEBUG(dbg_breeding, VERBOSITY_PLACEMENT, "Copying parent->child 1->1 and 2->2\n");
461 copy_symbols(clos_symbols, parent1, child1, &processed);
462 copy_symbols(clos_symbols, parent2, child2, &processed);
466 DEBUG(dbg_breeding, VERBOSITY_PLACEMENT, "Copying parent->child 2->1 and 1->2\n");
467 copy_symbols(clos_symbols, parent2, child1, &processed);
468 copy_symbols(clos_symbols, parent1, child2, &processed);
471 GARY_FREE(clos_symbols);
475 GARY_FREE(processed);
477 if (conf_mutate_children)
479 if (randdouble() < conf_mutate_children_prob) perform_mutation(child1);
480 else hide_segment_labels(child1);
482 if (randdouble() < conf_mutate_children_prob) perform_mutation(child2);
483 else hide_segment_labels(child2);
491 static void mutate(void)
493 for (int i=0; i < mutate_pop_size; i++)
495 DEBUG(dbg_mutation, VERBOSITY_INDIVIDUAL, "Creating %d-th individual by mutation\n", i);
496 int ind = randint(0, mutate_rbest_size);
497 DEBUG(dbg_mutation, VERBOSITY_INDIVIDUAL, "Mutating %d-th individual of original population\n", ind);
498 population2[pop2_ind] = ep_alloc(ep_individuals);
499 copy_individual(population1[ind], population2[pop2_ind]);
500 DEBUG(dbg_mutation, VERBOSITY_INDIVIDUAL, "Individual %d in pop2 inited from individual %d in pop1\n", pop2_ind, ind);
501 perform_mutation(population2[pop2_ind]);
506 static void perform_mutation(struct individual *individual)
508 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
510 double x = randdouble();
513 if (x <= acc + conf_mutate_move_bound)
515 DEBUG(dbg_mutation, VERBOSITY_PLACEMENT, "Mutation: Moving symbol in placement %u\n", i);
516 move_symbol(&(individual->placements[i]));
519 acc += conf_mutate_move_bound;
521 if (x <= acc + conf_mutate_regen_bound)
523 gen_coords(&(individual->placements[i]));
526 acc += conf_mutate_regen_bound;
528 if (x <= acc + conf_mutate_chvar_bound)
530 struct placement *p = &(individual->placements[i]);
531 switch (p->request->type)
535 // Does nothing when there are 0 variants... does it mind?
536 p->variant_used = randint(-1, GARY_SIZE(p->request->variants));
538 case REQUEST_SEGMENT:
539 p->variant_used = randint(0, GARY_SIZE(p->request->variants));
541 case REQUEST_SECTION:
542 p->variant_used = randint(0, GARY_SIZE(((struct request_section *) p->request)->segments));
550 hide_segment_labels(individual);
553 static void elite(void)
555 for (int i=0; i<elite_pop_size; i++)
557 DEBUG(dbg_evolution, VERBOSITY_INDIVIDUAL, "Iteration %d: Copying individual #%d from pop 1 to #%d in pop 2\n", iteration, i, pop2_ind);
558 population2[pop2_ind] = ep_alloc(ep_individuals);
559 copy_individual(population1[i], population2[pop2_ind++]);
563 static int cmp_individual(const void *a, const void *b)
565 struct individual **ia = (struct individual **) a;
566 struct individual **ib = (struct individual **) b;
568 return (*ia)->penalty - (*ib)->penalty;
571 static void rank_population(void)
575 for (int i=0; i<conf_pop_size; i++)
577 DEBUG(dbg_rank, VERBOSITY_INDIVIDUAL, "Individual %d\n", i);
578 population1[i]->penalty = 0;
580 penalty = individual_omittment(population1[i]);
581 DEBUG(dbg_rank, VERBOSITY_INDIVIDUAL, "Increasing penalty by %d for omittment\n", penalty);
582 population1[i]->penalty += penalty;
584 penalty = individual_overlap(population1[i]);
585 DEBUG(dbg_rank, VERBOSITY_INDIVIDUAL, "Increasing penalty by %d for overlap\n", penalty);
586 population1[i]->penalty += penalty;
588 penalty = individual_distances(population1[i]);
589 DEBUG(dbg_rank, VERBOSITY_INDIVIDUAL, "Increasing penalty by %d for distances\n", penalty);
590 population1[i]->penalty += penalty;
594 static void gen_coords(struct placement *p)
596 switch(p->request->type)
604 case REQUEST_SEGMENT:
605 gen_coords_segment(p);
609 printf("Not yet implemented\n");
612 DEBUG(dbg_movement, VERBOSITY_ALL, "Testing request type\n");
613 ASSERT(p->request->type != REQUEST_INVALID);
619 static double gen_movement(void)
621 double m = (random() % 100000) / 10000;
622 m = pow(m, 1.0/3) * flip(1, -1);
623 DEBUG(dbg_movement, VERBOSITY_ALL, "Movement %.2f\n", m);
627 static double gen_movement_uniform(void)
629 return (move_max - move_min) * randdouble() * flip(1, -1);
632 static void gen_coords_point(struct placement *p)
634 p->x = p->x + gen_movement();
637 static void gen_coords_segment(struct placement *p)
639 struct request_segment *rs = (struct request_segment *) p->request;
640 p->x = (rs->x1 + rs->x2) / 2;
641 p->y = (rs->y1 + rs->y2) / 2;
644 static void gen_coords_area(struct placement *p)
646 struct request_area *ra = (struct request_area *) p->request;
648 p->x = p->x + gen_movement();
649 p->y = p->y + gen_movement();
651 DEBUG(dbg_movement, VERBOSITY_PLACEMENT, "Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
654 static void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr)
656 bool *processed = *processed_ptr;
657 DEBUG(dbg_breeding, VERBOSITY_ALL, "Will copy %zu symbols\n", GARY_SIZE(closure));
659 for (uns i=0; i<GARY_SIZE(closure); i++)
661 processed[closure[i]->ind] = 1;
662 int ind = closure[i]->ind;
663 child->placements[ind] = parent->placements[ind];
664 child->placements[ind].individual = child;
665 child->placements[ind].processed = 0;
666 child->placements[ind].map_links = NULL;
667 update_map_parts(&child->placements[ind]);
671 static void move_symbol(struct placement *p)
673 switch (p->request->type)
677 move_symbol_point(p);
679 case REQUEST_SEGMENT:
680 move_symbol_segment(p);
683 ASSERT(p->request->type != REQUEST_INVALID);
687 static void move_symbol_point(struct placement *p)
689 p->x += gen_movement_uniform();
690 p->y += gen_movement_uniform();
693 static void move_symbol_segment(struct placement *p)
695 struct request_segment *rs = (struct request_segment *) p->request;
696 double m = gen_movement_uniform();
697 if (fabs(rs->x2 - rs->x1) > 0.01)
700 p->y += m * rs->slope;
708 static void hide_segment_labels(struct individual *individual)
710 // BEWARE: This fully depends on current genetic encoding
712 int used = -1, num = -1;
713 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
715 switch (individual->placements[i].request->type)
717 case REQUEST_SECTION:
718 used = individual->placements[i].variant_used;
721 case REQUEST_SEGMENT:
723 individual->placements[i].variant_used = 0;
725 individual->placements[i].variant_used = -1;
734 static void init_placement(struct placement *p, struct individual *individual, struct request *r)
736 p->ind = num_placements++;
739 p->x = p->y = 0; // To prevent valgrind from complaining
742 p->individual = individual;
745 case REQUEST_POINT: ;
746 struct request_point *rp = (struct request_point *) r;
752 case REQUEST_SECTION: ;
753 struct request_section *rls = (struct request_section *) r;
754 p->variant_used = randint(0, GARY_SIZE(rls->segments));
756 case REQUEST_SEGMENT: ;
757 struct request_segment *rs = (struct request_segment *) r;
762 struct request_area *ra = (struct request_area *) r;
768 ASSERT(p->request->type != REQUEST_INVALID);
772 DEBUG(dbg_init, VERBOSITY_PLACEMENT, "Inited placement to [%.2f; %.2f]\n", p->x, p->y);
775 static void clear_individual(struct individual *individual)
777 for (uns j=0; j<num_map_parts; j++)
779 struct map_placement *mp = individual->map[j]->placement;
782 struct map_placement *tmp = mp;
783 mp = mp->next_in_map;
787 free(individual->map[j]);
790 GARY_FREE(individual->map);
791 GARY_FREE(individual->placements);
792 ep_free(ep_individuals, individual);
795 static void clear_population(struct individual **pop)
797 for (uns i=0; i<GARY_SIZE(pop); i++)
799 clear_individual(pop[i]);
803 static void init_individual(struct individual *individual)
805 GARY_INIT(individual->placements, num_requests);
806 GARY_INIT(individual->map, 0);
807 for (uns j=0; j<num_map_parts; j++)
809 GARY_PUSH(individual->map);
810 struct map_part *part = xmalloc(sizeof(struct map_part));
811 struct map_placement *mp = xmalloc(sizeof(struct map_placement));
812 part->placement = mp;
814 mp->placement = &dummy_placement;
815 mp->next_in_map = mp->prev_in_map = NULL;
816 mp->next_in_placement = mp->prev_in_placement = NULL;
817 individual->map[j] = part;
819 individual->penalty = 0;
822 static void copy_individual(struct individual *src, struct individual *dest)
824 init_individual(dest);
825 dest->penalty = src->penalty;
827 for (uns i=0; i<GARY_SIZE(src->placements); i++)
829 dest->placements[i] = src->placements[i];
830 dest->placements[i].map_links = NULL;
831 dest->placements[i].individual = dest;
833 update_map_parts_create(&dest->placements[i]);
837 static int individual_overlap(struct individual *individual)
842 GARY_INIT_ZERO(planned, GARY_SIZE(individual->placements));
844 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
846 overlap += get_overlap(&individual->placements[i], &planned, i+1);
851 // printf("Total overlap is %d\n", overlap);
856 static double get_distance(struct placement *p)
858 if (p->variant_used < 0) return 0;
859 struct variant *v = &p->request->variants[p->variant_used];
861 double dx, dy, distance;
862 switch (p->request->type)
864 case REQUEST_POINT: ;
865 struct request_point *rp = (struct request_point *) p->request;
866 dx = rp->x + v->offset_x - p->x;
867 dy = rp->y + v->offset_y - p->y;
868 distance = hypot(dx, dy);
869 DEBUG(dbg_rank, VERBOSITY_PLACEMENT, "Point placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, rp->x, rp->y);
871 case REQUEST_SEGMENT: ;
872 struct request_segment *rs = (struct request_segment *) p->request;
873 struct sym_text *st = (struct sym_text *) rs->label;
875 double width = p->request->variants[p->variant_used].width;
876 double rotated_x = p->x + width * sin(convert_to_rad(st->rotate));
877 double rotated_y = p->y + width * cos(convert_to_rad(st->rotate));
886 else if (rotated_x > rs->x2)
888 dx = rotated_x - rs->x2;
889 dy = rotated_y - rs->y2;
903 else if (rotated_x > rs->x1)
905 dx = rotated_x - rs->x1;
906 dy = rotated_y - rs->y1;
914 distance = hypot(dx, dy);
917 struct request_area *ra = (struct request_area *) p->request;
918 dx = ra->cx + v->offset_x - p->x;
919 dy = ra->cy + v->offset_y - p->y;
920 distance = hypot(dx, dy);
921 DEBUG(dbg_rank, VERBOSITY_PLACEMENT, "Area placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
927 DEBUG(dbg_rank, VERBOSITY_PLACEMENT, "Placement %d has distance %.2f\n", p->ind, distance);
931 static double individual_distances(struct individual *individual)
935 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
937 distances += get_distance(&individual->placements[i]);
943 static double get_omittment(struct placement *p)
945 if (p->variant_used >= 0) return 0;
948 switch (p->request->type)
959 static double individual_omittment(struct individual *individual)
963 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
965 omittment += get_omittment(&individual->placements[i]);