1/* vim:set shiftwidth=4 ts=8: */
2
3/*************************************************************************
4 * Copyright (c) 2011 AT&T Intellectual Property
5 * All rights reserved. This program and the accompanying materials
6 * are made available under the terms of the Eclipse Public License v1.0
7 * which accompanies this distribution, and is available at
8 * http://www.eclipse.org/legal/epl-v10.html
9 *
10 * Contributors: See CVS logs. Details at http://www.graphviz.org/
11 *************************************************************************/
12
13#include <assert.h>
14#include <errno.h>
15#include <limits.h>
16#include <math.h>
17#include <stdlib.h>
18#include <stdio.h>
19#include <string.h>
20#define XLABEL_INT
21#include <xlabels.h>
22#include <memory.h>
23
24extern int Verbose;
25
26static int icompare(Dt_t *, void *, void *, Dtdisc_t *);
27
28Dtdisc_t Hdisc = { offsetof(HDict_t, key), sizeof(int), -1, 0, 0,
29 icompare, 0, 0, 0
30};
31
32static int icompare(Dt_t * dt, void * v1, void * v2, Dtdisc_t * disc)
33{
34 int k1 = *((int *) v1), k2 = *((int *) v2);
35 return k1 - k2;
36}
37
38static XLabels_t *xlnew(object_t * objs, int n_objs,
39 xlabel_t * lbls, int n_lbls,
40 label_params_t * params)
41{
42 XLabels_t *xlp;
43
44 xlp = NEW(XLabels_t);
45
46 /* used to load the rtree in hilbert space filling curve order */
47 if (!(xlp->hdx = dtopen(&Hdisc, Dtobag))) {
48 fprintf(stderr, "out of memory\n");
49 goto bad;
50 }
51
52 /* for querying intersection candidates */
53 if (!(xlp->spdx = RTreeOpen())) {
54 fprintf(stderr, "out of memory\n");
55 goto bad;
56 }
57 /* save arg pointers in the handle */
58 xlp->objs = objs;
59 xlp->n_objs = n_objs;
60 xlp->lbls = lbls;
61 xlp->n_lbls = n_lbls;
62 xlp->params = params;
63
64 return xlp;
65
66 bad:
67 if (xlp->hdx)
68 dtclose(xlp->hdx);
69 if (xlp->spdx)
70 RTreeClose(xlp->spdx);
71 free(xlp);
72 return 0;
73}
74
75static void xlfree(XLabels_t * xlp)
76{
77 RTreeClose(xlp->spdx);
78 free(xlp);
79 return;
80}
81
82/***************************************************************************/
83
84/*
85 * floorlog2 - largest base 2 integer logarithm less than n
86 * http://en.wikipedia.org/wiki/Binary_logarithm
87 * ultimately from http://www.hackersdelight.org/
88 */
89static int floorLog2(unsigned int n)
90{
91 int pos = 0;
92
93 if (n == 0)
94 return -1;
95
96 if (n >= 1 << 16) {
97 n >>= 16;
98 pos += 16;
99 }
100 if (n >= 1 << 8) {
101 n >>= 8;
102 pos += 8;
103 }
104 if (n >= 1 << 4) {
105 n >>= 4;
106 pos += 4;
107 }
108 if (n >= 1 << 2) {
109 n >>= 2;
110 pos += 2;
111 }
112 if (n >= 1 << 1) {
113 pos += 1;
114 }
115 return pos;
116}
117
118/*
119 * determine the order(depth) of the hilbert sfc so that we satisfy the
120 * precondition of hd_hil_s_from_xy()
121 */
122unsigned int xlhorder(XLabels_t * xlp)
123{
124 double maxx = xlp->params->bb.UR.x, maxy = xlp->params->bb.UR.y;
125 return floorLog2(maxx > maxy ? maxx : maxy) + 1;
126}
127
128/* from http://www.hackersdelight.org/ site for the book by Henry S Warren */
129/*
130 * precondition
131 * pow(2, n) >= max(p.x, p.y)
132 */
133/* adapted from lams1.c
134Given the "order" n of a Hilbert curve and coordinates x and y, this
135program computes the length s of the curve from the origin to (x, y).
136The square that the Hilbert curve traverses is of size 2**n by 2**n.
137 The method is that given in [Lam&Shap], described by the following
138table. Here i = n-1 for the most significant bit of x and y, and i = 0
139for the least significant bits.
140
141 x[i] y[i] | s[2i+1:2i] x y
142 -----------|-------------------
143 0 0 | 00 y x
144 0 1 | 01 x y
145 1 0 | 11 ~y ~x
146 1 1 | 10 x y
147
148To use this table, start at the most significant bits of x and y
149(i = n - 1). If they are both 0 (first row), set the most significant
150two bits of s to 00 and interchange x and y. (Actually, it is only
151necessary to interchange the remaining bits of x and y.) If the most
152significant bits of x and y are 10 (third row), output 11, interchange x
153and y, and complement x and y.
154 Then, consider the next most significant bits of x and y (which may
155have been changed by this process), and select the appropriate row of
156the table to determine the next two bits of s, and how to change x and
157y. Continue until the least significant bits of x and y have been
158processed. */
159
160static unsigned int hd_hil_s_from_xy(point p, int n)
161{
162 int i, x = p.x, y = p.y, xi, yi;
163 unsigned s;
164
165 s = 0; /* Initialize. */
166 for (i = n - 1; i >= 0; i--) {
167 xi = (x >> i) & 1; /* Get bit i of x. */
168 yi = (y >> i) & 1; /* Get bit i of y. */
169 s = 4 * s + 2 * xi + (xi ^ yi); /* Append two bits to s. */
170
171 x = x ^ y; /* These 3 lines swap */
172 y = y ^ (x & (yi - 1)); /* x and y if yi = 0. */
173 x = x ^ y;
174 x = x ^ (-xi & (yi - 1)); /* Complement x and y if */
175 y = y ^ (-xi & (yi - 1)); /* xi = 1 and yi = 0. */
176 }
177 return s;
178}
179
180/* intersection test from
181 * from Real-Time Collision Detection 4.2.1 by Christer Ericson
182 * intersection area from
183 * http://stackoverflow.com/questions/4549544/total-area-of-intersecting-rectangles
184*/
185static double aabbaabb(Rect_t * r, Rect_t * s)
186{
187 /* per dimension if( max < omin || min > omax) */
188 double iminx, iminy, imaxx, imaxy;
189 if (r->boundary[2] < s->boundary[0] || r->boundary[0] > s->boundary[2])
190 return 0;
191 if (r->boundary[3] < s->boundary[1] || r->boundary[1] > s->boundary[3])
192 return 0;
193
194 /* if we get here we have an intersection */
195
196 /* rightmost left edge of the 2 rectangles */
197 iminx =
198 r->boundary[0] > s->boundary[0] ? r->boundary[0] : s->boundary[0];
199 /* upmost bottom edge */
200 iminy =
201 r->boundary[1] > s->boundary[1] ? r->boundary[1] : s->boundary[1];
202 /* leftmost right edge */
203 imaxx =
204 r->boundary[2] < s->boundary[2] ? r->boundary[2] : s->boundary[2];
205 /* downmost top edge */
206 imaxy =
207 r->boundary[3] < s->boundary[3] ? r->boundary[3] : s->boundary[3];
208 return (imaxx - iminx) * (imaxy - iminy);
209}
210
211/*
212 * test if objp1, a size 0 object is enclosed in the xlabel
213 * associated with objp
214 */
215static int lblenclosing(object_t * objp, object_t * objp1)
216{
217 xlabel_t * xlp = objp->lbl;;
218
219 assert(objp1->sz.x == 0 && objp1->sz.y == 0);
220
221 if(! xlp) return 0;
222
223 return objp1->pos.x > xlp->pos.x &&
224 objp1->pos.x < (xlp->pos.x + xlp->sz.x) &&
225 objp1->pos.y > xlp->pos.y &&
226 objp1->pos.y < (xlp->pos.y + xlp->sz.y);
227}
228
229/*fill in rectangle from the object */
230static void objp2rect(object_t * op, Rect_t * r)
231{
232 r->boundary[0] = op->pos.x;
233 r->boundary[1] = op->pos.y;
234 r->boundary[2] = op->pos.x + op->sz.x;
235 r->boundary[3] = op->pos.y + op->sz.y;
236 return;
237}
238
239/*fill in rectangle from the objects xlabel */
240static void objplp2rect(object_t * objp, Rect_t * r)
241{
242 xlabel_t *lp = objp->lbl;
243 r->boundary[0] = lp->pos.x;
244 r->boundary[1] = lp->pos.y;
245 r->boundary[2] = lp->pos.x + lp->sz.x;
246 r->boundary[3] = lp->pos.y + lp->sz.y;
247 return;
248}
249
250/* compute boundary that encloses all possible label boundaries */
251static Rect_t objplpmks(XLabels_t * xlp, object_t * objp)
252{
253 Rect_t rect;
254 pointf p;
255
256 p.x = p.y = 0.0;
257 if (objp->lbl)
258 p = objp->lbl->sz;
259
260 rect.boundary[0] = (int) floor(objp->pos.x - p.x);
261 rect.boundary[1] = (int) floor(objp->pos.y - p.y);
262
263 rect.boundary[2] = (int) ceil(objp->pos.x + objp->sz.x + p.x);
264 assert(rect.boundary[2] < INT_MAX);
265 rect.boundary[3] = (int) ceil(objp->pos.y + objp->sz.y + p.y);
266 assert(rect.boundary[3] < INT_MAX);
267
268 return rect;
269}
270
271/* determine the position clp will occupy in intrsx[] */
272static int getintrsxi(XLabels_t * xlp, object_t * op, object_t * cp)
273{
274 int i = -1;
275 xlabel_t *lp = op->lbl, *clp = cp->lbl;
276 assert(lp != clp);
277
278 if (lp->set == 0 || clp->set == 0)
279 return i;
280 if ((op->pos.x == 0.0 && op->pos.y == 0.0) ||
281 (cp->pos.x == 0.0 && cp->pos.y == 0.0))
282 return i;
283
284 if (cp->pos.y < op->pos.y)
285 if (cp->pos.x < op->pos.x)
286 i = XLPXPY;
287 else if (cp->pos.x > op->pos.x)
288 i = XLNXPY;
289 else
290 i = XLCXPY;
291 else if (cp->pos.y > op->pos.y)
292 if (cp->pos.x < op->pos.x)
293 i = XLPXNY;
294 else if (cp->pos.x > op->pos.x)
295 i = XLNXNY;
296 else
297 i = XLCXNY;
298 else if (cp->pos.x < op->pos.x)
299 i = XLPXCY;
300 else if (cp->pos.x > op->pos.x)
301 i = XLNXCY;
302
303 return i;
304
305}
306
307/* record the intersecting objects label */
308static double
309recordointrsx(XLabels_t * xlp, object_t * op, object_t * cp, Rect_t * rp,
310 double a, object_t * intrsx[XLNBR])
311{
312 int i = getintrsxi(xlp, op, cp);
313 if (i < 0)
314 i = 5;
315 if (intrsx[i] != NULL) {
316 double sa, maxa = 0.0;
317 Rect_t srect;
318 /* keep maximally overlapping object */
319 objp2rect(intrsx[i], &srect);
320 sa = aabbaabb(rp, &srect);
321 if (sa > a)
322 maxa = sa;
323 /*keep maximally overlapping label */
324 if (intrsx[i]->lbl) {
325 objplp2rect(intrsx[i], &srect);
326 sa = aabbaabb(rp, &srect);
327 if (sa > a)
328 maxa = sa > maxa ? sa : maxa;
329 }
330 if (maxa > 0.0)
331 return maxa;
332 /*replace overlapping label/object pair */
333 intrsx[i] = cp;
334 return a;
335 }
336 intrsx[i] = cp;
337 return a;
338}
339
340/* record the intersecting label */
341static double
342recordlintrsx(XLabels_t * xlp, object_t * op, object_t * cp, Rect_t * rp,
343 double a, object_t * intrsx[XLNBR])
344{
345 int i = getintrsxi(xlp, op, cp);
346 if (i < 0)
347 i = 5;
348 if (intrsx[i] != NULL) {
349 double sa, maxa = 0.0;
350 Rect_t srect;
351 /* keep maximally overlapping object */
352 objp2rect(intrsx[i], &srect);
353 sa = aabbaabb(rp, &srect);
354 if (sa > a)
355 maxa = sa;
356 /*keep maximally overlapping label */
357 if (intrsx[i]->lbl) {
358 objplp2rect(intrsx[i], &srect);
359 sa = aabbaabb(rp, &srect);
360 if (sa > a)
361 maxa = sa > maxa ? sa : maxa;
362 }
363 if (maxa > 0.0)
364 return maxa;
365 /*replace overlapping label/object pair */
366 intrsx[i] = cp;
367 return a;
368 }
369 intrsx[i] = cp;
370 return a;
371}
372
373/* find the objects and labels intersecting lp */
374static BestPos_t
375xlintersections(XLabels_t * xlp, object_t * objp, object_t * intrsx[XLNBR])
376{
377 int i;
378 LeafList_t *ilp, *llp;
379 Rect_t rect, srect;
380 BestPos_t bp;
381
382 assert(objp->lbl);
383
384 bp.n = 0;
385 bp.area = 0.0;
386 bp.pos = objp->lbl->pos;
387
388 for(i=0; i<xlp->n_objs; i++) {
389 if(objp == &xlp->objs[i]) continue;
390 if(xlp->objs[i].sz.x > 0 && xlp->objs[i].sz.y > 0) continue;
391 if(lblenclosing(objp, &xlp->objs[i]) ) {
392 bp.n++;
393 }
394 }
395
396 objplp2rect(objp, &rect);
397
398 llp = RTreeSearch(xlp->spdx, xlp->spdx->root, &rect);
399 if (!llp)
400 return bp;
401
402 for (ilp = llp; ilp; ilp = ilp->next) {
403 double a, ra;
404 object_t *cp = ilp->leaf->data;
405
406 if (cp == objp)
407 continue;
408
409 /*label-object intersect */
410 objp2rect(cp, &srect);
411 a = aabbaabb(&rect, &srect);
412 if (a > 0.0) {
413 ra = recordointrsx(xlp, objp, cp, &rect, a, intrsx);
414 bp.n++;
415 bp.area += ra;
416 }
417 /*label-label intersect */
418 if (!cp->lbl || !cp->lbl->set)
419 continue;
420 objplp2rect(cp, &srect);
421 a = aabbaabb(&rect, &srect);
422 if (a > 0.0) {
423 ra = recordlintrsx(xlp, objp, cp, &rect, a, intrsx);
424 bp.n++;
425 bp.area += ra;
426 }
427 }
428 RTreeLeafListFree(llp);
429 return bp;
430}
431
432/*
433 * xladjust - find a label position
434 * the individual tests at the top are intended to place a preference order
435 * on the position
436 */
437static BestPos_t xladjust(XLabels_t * xlp, object_t * objp)
438{
439 xlabel_t *lp = objp->lbl;
440 double xincr = ((2 * lp->sz.x) + objp->sz.x) / XLXDENOM;
441 double yincr = ((2 * lp->sz.y) + objp->sz.y) / XLYDENOM;
442 object_t *intrsx[XLNBR];
443 BestPos_t bp, nbp;
444
445 assert(objp->lbl);
446
447 memset(intrsx, 0, sizeof(intrsx));
448
449 /*x left */
450 lp->pos.x = objp->pos.x - lp->sz.x;
451 /*top */
452 lp->pos.y = objp->pos.y + objp->sz.y;
453 bp = xlintersections(xlp, objp, intrsx);
454 if (bp.n == 0)
455 return bp;
456 /*mid */
457 lp->pos.y = objp->pos.y;
458 nbp = xlintersections(xlp, objp, intrsx);
459 if (nbp.n == 0)
460 return nbp;
461 if (nbp.area < bp.area)
462 bp = nbp;
463 /*bottom */
464 lp->pos.y = objp->pos.y - lp->sz.y;
465 nbp = xlintersections(xlp, objp, intrsx);
466 if (nbp.n == 0)
467 return nbp;
468 if (nbp.area < bp.area)
469 bp = nbp;
470
471 /*x mid */
472 lp->pos.x = objp->pos.x;
473 /*top */
474 lp->pos.y = objp->pos.y + objp->sz.y;
475 nbp = xlintersections(xlp, objp, intrsx);
476 if (nbp.n == 0)
477 return nbp;
478 if (nbp.area < bp.area)
479 bp = nbp;
480 /*bottom */
481 lp->pos.y = objp->pos.y - lp->sz.y;
482 nbp = xlintersections(xlp, objp, intrsx);
483 if (nbp.n == 0)
484 return nbp;
485 if (nbp.area < bp.area)
486 bp = nbp;
487
488 /*x right */
489 lp->pos.x = objp->pos.x + objp->sz.x;
490 /*top */
491 lp->pos.y = objp->pos.y + objp->sz.y;
492 nbp = xlintersections(xlp, objp, intrsx);
493 if (nbp.n == 0)
494 return nbp;
495 if (nbp.area < bp.area)
496 bp = nbp;
497 /*mid */
498 lp->pos.y = objp->pos.y;
499 nbp = xlintersections(xlp, objp, intrsx);
500 if (nbp.n == 0)
501 return nbp;
502 if (nbp.area < bp.area)
503 bp = nbp;
504 /*bottom */
505 lp->pos.y = objp->pos.y - lp->sz.y;
506 nbp = xlintersections(xlp, objp, intrsx);
507 if (nbp.n == 0)
508 return nbp;
509 if (nbp.area < bp.area)
510 bp = nbp;
511
512 /*sliding from top left */
513 if (intrsx[XLPXNY] || intrsx[XLCXNY] || intrsx[XLNXNY] || intrsx[XLPXCY] || intrsx[XLPXPY]) { /* have to move */
514 if (!intrsx[XLCXNY] && !intrsx[XLNXNY]) { /* some room right? */
515 /* slide along upper edge */
516 for (lp->pos.x = objp->pos.x - lp->sz.x,
517 lp->pos.y = objp->pos.y + objp->sz.y;
518 lp->pos.x <= (objp->pos.x + objp->sz.x);
519 lp->pos.x += xincr) {
520 nbp = xlintersections(xlp, objp, intrsx);
521 if (nbp.n == 0)
522 return nbp;
523 if (nbp.area < bp.area)
524 bp = nbp;
525 }
526 }
527 if (!intrsx[XLPXCY] && !intrsx[XLPXPY]) { /* some room down? */
528 /* slide down left edge */
529 for (lp->pos.x = objp->pos.x - lp->sz.x,
530 lp->pos.y = objp->pos.y + objp->sz.y;
531 lp->pos.y >= (objp->pos.y - lp->sz.y);
532 lp->pos.y -= yincr) {
533 nbp = xlintersections(xlp, objp, intrsx);
534 if (nbp.n == 0)
535 return nbp;
536 if (nbp.area < bp.area)
537 bp = nbp;
538
539 }
540 }
541 }
542
543 /*sliding from bottom right */
544 lp->pos.x = objp->pos.x + objp->sz.x;
545 lp->pos.y = objp->pos.y - lp->sz.y;
546 if (intrsx[XLNXPY] || intrsx[XLCXPY] || intrsx[XLPXPY] || intrsx[XLNXCY] || intrsx[XLNXNY]) { /* have to move */
547 if (!intrsx[XLCXPY] && !intrsx[XLPXPY]) { /* some room left? */
548 /* slide along lower edge */
549 for (lp->pos.x = objp->pos.x + objp->sz.x,
550 lp->pos.y = objp->pos.y - lp->sz.y;
551 lp->pos.x >= (objp->pos.x - lp->sz.x);
552 lp->pos.x -= xincr) {
553 nbp = xlintersections(xlp, objp, intrsx);
554 if (nbp.n == 0)
555 return nbp;
556 if (nbp.area < bp.area)
557 bp = nbp;
558 }
559 }
560 if (!intrsx[XLNXCY] && !intrsx[XLNXNY]) { /* some room up? */
561 /* slide up right edge */
562 for (lp->pos.x = objp->pos.x + objp->sz.x,
563 lp->pos.y = objp->pos.y - lp->sz.y;
564 lp->pos.y <= (objp->pos.y + objp->sz.y);
565 lp->pos.y += yincr) {
566 nbp = xlintersections(xlp, objp, intrsx);
567 if (nbp.n == 0)
568 return nbp;
569 if (nbp.area < bp.area)
570 bp = nbp;
571 }
572 }
573 }
574 return bp;
575}
576
577/* load the hilbert sfc keyed tree */
578static int xlhdxload(XLabels_t * xlp)
579{
580 int i;
581 int order = xlhorder(xlp);
582
583 for (i = 0; i < xlp->n_objs; i++) {
584 HDict_t *hp;
585 point pi;
586
587 hp = NEW(HDict_t);
588
589 hp->d.data = &xlp->objs[i];
590 hp->d.rect = objplpmks(xlp, &xlp->objs[i]);
591 /* center of the labeling area */
592 pi.x = hp->d.rect.boundary[0] +
593 (hp->d.rect.boundary[2] - hp->d.rect.boundary[0]) / 2;
594 pi.y = hp->d.rect.boundary[1] +
595 (hp->d.rect.boundary[3] - hp->d.rect.boundary[1]) / 2;
596
597 hp->key = hd_hil_s_from_xy(pi, order);
598
599#if 0
600 if (dtsearch(xlp->hdx, hp) != 0) {
601 free(hp);
602 continue;
603 }
604#endif
605 if (!(dtinsert(xlp->hdx, hp)))
606 return -1;
607 }
608 return 0;
609}
610
611static void xlhdxunload(XLabels_t * xlp)
612{
613 int size=dtsize(xlp->hdx), freed=0;
614 while(dtsize(xlp->hdx) ) {
615 void*vp=dtfinger(xlp->hdx);
616 assert(vp);
617 if(vp) {
618 dtdetach(xlp->hdx, vp);
619 free(vp);
620 freed++;
621 }
622 }
623 assert(size==freed);
624}
625
626static int xlspdxload(XLabels_t * xlp)
627{
628 HDict_t *op=0;
629
630 for (op = dtfirst(xlp->hdx); op; op = dtnext(xlp->hdx, op)) {
631 /* tree rectangle data node lvl */
632 RTreeInsert(xlp->spdx, &op->d.rect, op->d.data, &xlp->spdx->root, 0);
633 }
634 return 0;
635}
636
637static int xlinitialize(XLabels_t * xlp)
638{
639 int r=0;
640 if ((r = xlhdxload(xlp)) < 0)
641 return r;
642 if ((r = xlspdxload(xlp)) < 0)
643 return r;
644 xlhdxunload(xlp);
645 return dtclose(xlp->hdx);
646}
647
648int
649placeLabels(object_t * objs, int n_objs,
650 xlabel_t * lbls, int n_lbls, label_params_t * params)
651{
652 int r, i;
653 BestPos_t bp;
654 XLabels_t *xlp = xlnew(objs, n_objs, lbls, n_lbls, params);
655 if ((r = xlinitialize(xlp)) < 0)
656 return r;
657
658 /* Place xlabel_t* lp near lp->obj so that the rectangle whose lower-left
659 * corner is lp->pos, and size is lp->sz does not intersect any object
660 * in objs (by convention, an object consisting of a single point
661 * intersects nothing) nor any other label, if possible. On input,
662 * lp->set is 0.
663 *
664 * On output, any label with a position should have this stored in
665 * lp->pos and have lp->set non-zero.
666 *
667 * If params->force is true, all labels must be positioned, even if
668 * overlaps are necessary.
669 *
670 * Return 0 if all labels could be placed without overlap;
671 * non-zero otherwise.
672 */
673 r = 0;
674 for (i = 0; i < n_objs; i++) {
675 if (objs[i].lbl == 0)
676 continue;
677 bp = xladjust(xlp, &objs[i]);
678 if (bp.n == 0) {
679 objs[i].lbl->set = 1;
680 } else if(bp.area == 0) {
681 objs[i].lbl->pos.x = bp.pos.x;
682 objs[i].lbl->pos.y = bp.pos.y;
683 objs[i].lbl->set = 1;
684 } else if (params->force == 1) {
685 objs[i].lbl->pos.x = bp.pos.x;
686 objs[i].lbl->pos.y = bp.pos.y;
687 objs[i].lbl->set = 1;
688 } else {
689 r = 1;
690 }
691 }
692 xlfree(xlp);
693 return r;
694}
695