29 const int k1 = *(
int *)v1;
30 const int k2 = *(
int *)v2;
42 XLabels_t *xlp =
gv_alloc(
sizeof(XLabels_t));
46 fprintf(stderr,
"out of memory\n");
52 fprintf(stderr,
"out of memory\n");
77 double maxx = xlp->params->bb.UR.x, maxy = xlp->params->bb.UR.y;
78 return (
unsigned)floor(log2(round(fmax(maxx, maxy)))) + 1;
114 int x = p.
x, y = p.
y;
117 for (
int i = n - 1; i >= 0; i--) {
118 int xi = (x >> i) & 1;
119 int yi = (y >> i) & 1;
120 s = 4 *
s + 2 * (unsigned)xi +
121 ((
unsigned)xi ^ (unsigned)yi);
124 y = y ^ (x & (yi - 1));
126 x = x ^ (-xi & (yi - 1));
127 y = y ^ (-xi & (yi - 1));
144 double iminx = fmax(r.
boundary[0],
s.boundary[0]);
146 double iminy = fmax(r.
boundary[1],
s.boundary[1]);
148 double imaxx = fmin(r.
boundary[2],
s.boundary[2]);
150 double imaxy = fmin(r.
boundary[3],
s.boundary[3]);
151 return (imaxx - iminx) * (imaxy - iminy);
162 assert(objp1->
sz.
x == 0 && objp1->
sz.
y == 0);
214 if (lp->
set == 0 || clp->set == 0)
216 if ((op->
pos.
x == 0.0 && op->
pos.
y == 0.0) ||
217 (cp->
pos.
x == 0.0 && cp->
pos.
y == 0.0))
248 if (intrsx[i] !=
NULL) {
249 double sa, maxa = 0.0;
256 if (intrsx[i]->lbl) {
260 maxa = fmax(sa, maxa);
278 if (intrsx[i] !=
NULL) {
279 double sa, maxa = 0.0;
286 if (intrsx[i]->lbl) {
290 maxa = fmax(sa, maxa);
307 BestPos_t bp = {.pos = objp->
lbl->
pos};
309 for (
size_t i = 0; i < xlp->n_objs; i++) {
310 if (objp == &xlp->objs[i])
312 if (xlp->objs[i].sz.x > 0 && xlp->objs[i].sz.y > 0)
362 double xincr = (2 * lp->
sz.
x + objp->
sz.
x) / XLXDENOM;
363 double yincr = (2 * lp->
sz.
y + objp->
sz.
y) / XLYDENOM;
380 if (nbp.area < bp.area)
387 if (nbp.area < bp.area)
397 if (nbp.area < bp.area)
404 if (nbp.area < bp.area)
414 if (nbp.area < bp.area)
421 if (nbp.area < bp.area)
428 if (nbp.area < bp.area)
432 if (intrsx[XLPXNY] || intrsx[XLCXNY] || intrsx[XLNXNY] || intrsx[XLPXCY] ||
434 if (!intrsx[XLCXNY] && !intrsx[XLNXNY]) {
442 if (nbp.area < bp.area)
446 if (!intrsx[XLPXCY] && !intrsx[XLPXPY]) {
454 if (nbp.area < bp.area)
463 if (intrsx[XLNXPY] || intrsx[XLCXPY] || intrsx[XLPXPY] || intrsx[XLNXCY] ||
465 if (!intrsx[XLCXPY] && !intrsx[XLPXPY]) {
473 if (nbp.area < bp.area)
477 if (!intrsx[XLNXCY] && !intrsx[XLNXNY]) {
485 if (nbp.area < bp.area)
497 for (
size_t i = 0; i < xlp->n_objs; i++) {
498 HDict_t *hp =
gv_alloc(
sizeof(HDict_t));
500 hp->d.data = &xlp->objs[i];
503 const double x = hp->d.rect.boundary[0] +
504 (hp->d.rect.boundary[2] - hp->d.rect.boundary[0]) / 2;
505 const double y = hp->d.rect.boundary[1] +
506 (hp->d.rect.boundary[3] - hp->d.rect.boundary[1]) / 2;
507 assert(x >= INT_MIN && x <= INT_MAX);
508 assert(y >= INT_MIN && y <= INT_MAX);
509 const point pi = {.
x = (int)x, .y = (
int)y};
520 int size =
dtsize(xlp->hdx), freed = 0;
521 while (
dtsize(xlp->hdx)) {
530 assert(size == freed);
535 for (HDict_t *op =
dtfirst(xlp->hdx); op; op =
dtnext(xlp->hdx, op)) {
537 RTreeInsert(xlp->spdx, op->d.rect, op->d.data, &xlp->spdx->root);
553 XLabels_t *xlp =
xlnew(objs, n_objs, lbls, n_lbls, params);
573 for (
size_t i = 0; i < n_objs; i++) {
574 if (objs[i].lbl == 0)
576 const BestPos_t bp =
xladjust(xlp, &objs[i]);
579 }
else if (bp.area == 0) {
580 objs[i].
lbl->
pos = bp.pos;
582 }
else if (params->
force == 1) {
583 objs[i].
lbl->
pos = bp.pos;
Memory allocation wrappers that exit on failure.
static void * gv_alloc(size_t size)
CDT_API Dtmethod_t * Dtobag
ordered multiset
CDT_API int dtsize(Dt_t *)
CDT_API int dtclose(Dt_t *)
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
static NORETURN void graphviz_exit(int status)
void RTreeLeafListFree(LeafList_t *llp)
RTree_t * RTreeOpen(void)
int RTreeClose(RTree_t *rtp)
int RTreeInsert(RTree_t *rtp, Rect_t r, void *data, Node_t **n)
LeafList_t * RTreeSearch(RTree_t *rtp, Node_t *n, Rect_t r)
bool Overlap(const Rect_t r, const Rect_t s)
double boundary[NUMSIDES]
static BestPos_t xlintersections(XLabels_t *xlp, object_t *objp, object_t *intrsx[XLNBR])
static double aabbaabb(Rect_t r, Rect_t s)
static double recordlintrsx(object_t *op, object_t *cp, Rect_t *rp, double a, object_t *intrsx[XLNBR])
int placeLabels(object_t *objs, size_t n_objs, xlabel_t *lbls, size_t n_lbls, label_params_t *params)
static void xlfree(XLabels_t *xlp)
static void xlspdxload(XLabels_t *xlp)
static Rect_t objplp2rect(const object_t *objp)
static Rect_t objp2rect(const object_t *op)
static void xlhdxunload(XLabels_t *xlp)
static double recordointrsx(object_t *op, object_t *cp, Rect_t rp, double a, object_t *intrsx[XLNBR])
static int getintrsxi(object_t *op, object_t *cp)
static bool lblenclosing(object_t *objp, object_t *objp1)
static int xlinitialize(XLabels_t *xlp)
static XLabels_t * xlnew(object_t *objs, size_t n_objs, xlabel_t *lbls, size_t n_lbls, label_params_t *params)
static BestPos_t xladjust(XLabels_t *xlp, object_t *objp)
static Rect_t objplpmks(object_t *objp)
static unsigned int hd_hil_s_from_xy(point p, int n)
static unsigned int xlhorder(XLabels_t *xlp)
static int icompare(void *, void *)
static int xlhdxload(XLabels_t *xlp)