+int overlaps(struct placement *p1, struct placement *p2)
+{
+ if (p1->request->type != REQUEST_POINT &&
+ p1->request->type != REQUEST_SEGMENT &&
+ p1->request->type != REQUEST_AREA)
+ return 0;
+
+ if (p2->request->type != REQUEST_POINT &&
+ p2->request->type != REQUEST_SEGMENT &&
+ p2->request->type != REQUEST_AREA)
+ return 0;
+
+ if (p1->variant_used == -1 || p2->variant_used == -1)
+ return 0;
+
+ struct variant *v1, *v2;
+
+ v1 = &(p1->request->variants[p1->variant_used]);
+ v2 = &(p2->request->variants[p2->variant_used]);
+
+ // FIXME: This doesn't fully respect offset which it probably should
+ int p1x = p1->x; int p1y = p1->y;
+ int p2x = p2->x; int p2y = p2->y;
+
+ int overlap = 0;
+ for (int y=max2(0, max2(p1y, p2y)); y<min2(page_height_int, min2(p1y+v1->height, p2y+v2->height)); y++)
+ for (int x=max2(0, max2(p1x, p2x)); x<min2(page_width_int, min2(p1x+v1->width, p2x+v2->width)); x++)
+ {
+ if (v1->bitmap[(y-p1y)*v1->width + (x-p1x)] &&
+ v2->bitmap[(y-p2y)*v2->width + (x-p2x)])
+ overlap++;
+ }
+
+ return overlap;
+}
+
+int get_overlap(struct placement *p)
+{
+ struct map_part **parts = get_map_parts(p);
+ if (! parts)
+ {
+ if (dbg_overlaps >= VERBOSITY_PLACEMENT)
+ printf("Placement of request %d seems not to be placed\n", p->request->ind);
+ return 0;
+ }
+
+ struct placement **others;
+ bool *planned;
+
+ GARY_INIT_ZERO(planned, num_requests);
+ planned[p->request->ind] = 1;
+ GARY_INIT(others, 0);
+
+ for (uns i=0; i<GARY_SIZE(parts); i++)
+ {
+ struct map_placement *mp = parts[i]->placement->next_in_map;
+ while (mp)
+ {
+ if (! planned[mp->placement->request->ind])
+ {
+ struct placement **p = GARY_PUSH(others);
+ *p = mp->placement;
+ planned[mp->placement->request->ind] = true;
+ }
+ mp = mp->next_in_map;
+ }
+ }
+
+ int overlap = 0;
+ for (uns i=0; i<GARY_SIZE(others); i++)
+ {
+ overlap += overlaps(p, others[i]);
+ }
+
+ GARY_FREE(planned);
+ GARY_FREE(parts);
+ GARY_FREE(others);
+
+ if (dbg_overlaps >= VERBOSITY_PLACEMENT)
+ printf("Placement of request %d add %d to overlaps\n", p->request->ind, overlap);
+
+ return overlap;
+}
+
+int individual_overlap(struct individual *individual)
+{
+ int overlap = 0;
+
+ for (uns i=0; i<GARY_SIZE(individual->placements); i++)
+ {
+ overlap += get_overlap(&individual->placements[i]);
+ }
+
+ return overlap;
+}
+
+double get_distance(struct placement *p)
+{
+ if (p->variant_used < 0) return 0;
+ struct variant *v = &p->request->variants[p->variant_used];
+
+ double dx, dy, distance;
+ switch (p->request->type)
+ {
+ case REQUEST_POINT: ;
+ struct request_point *rp = (struct request_point *) p->request;
+ dx = rp->x + v->offset_x - p->x;
+ dy = rp->y + v->offset_y - p->y;
+ distance = sqrt(dx*dx + dy*dy);
+ if (dbg_rank >= VERBOSITY_PLACEMENT)
+ printf("Point placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, rp->x, rp->y);
+ break;
+ case REQUEST_AREA: ;
+ struct request_area *ra = (struct request_area *) p->request;
+ dx = ra->cx + v->offset_x - p->x;
+ dy = ra->cy + v->offset_y - p->y;
+ distance = sqrt(dx*dx + dy*dy);
+ if (dbg_rank >= VERBOSITY_PLACEMENT)
+ printf("Area placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
+ break;
+ default:
+ return 0;
+ }
+
+ if (dbg_rank >= VERBOSITY_PLACEMENT)
+ printf("Placement %d has distance %.2f\n", p->ind, distance);
+ return distance;
+}
+
+double individual_distances(struct individual *individual)
+{
+ int distances = 0;
+
+ for (uns i=0; i<GARY_SIZE(individual->placements); i++)
+ {
+ distances += get_distance(&individual->placements[i]);
+ }
+
+ return distances;
+}
+
+int cmp_individual(const void *a, const void *b)
+{
+ struct individual **ia = (struct individual **) a;
+ struct individual **ib = (struct individual **) b;
+
+ return (*ia)->penalty - (*ib)->penalty;
+}
+