31 int k1 = *((
int *) v1), k2 = *((
int *) v2);
43 XLabels_t *xlp =
gv_alloc(
sizeof(XLabels_t));
47 fprintf(stderr,
"out of memory\n");
53 fprintf(stderr,
"out of memory\n");
80 double maxx = xlp->params->bb.UR.x, maxy = xlp->params->bb.UR.y;
81 return (
unsigned)floor(log2(round(fmax(maxx, maxy)))) + 1;
118 int x = p.
x, y = p.
y;
121 for (
int i = n - 1; i >= 0; i--) {
122 int xi = (x >> i) & 1;
123 int yi = (y >> i) & 1;
124 s = 4 *
s + 2 * (unsigned)xi + ((
unsigned)xi ^ (unsigned)yi);
127 y = y ^ (x & (yi - 1));
129 x = x ^ (-xi & (yi - 1));
130 y = y ^ (-xi & (yi - 1));
147 double iminx = fmax(r.
boundary[0],
s.boundary[0]);
149 double iminy = fmax(r.
boundary[1],
s.boundary[1]);
151 double imaxx = fmin(r.
boundary[2],
s.boundary[2]);
153 double imaxy = fmin(r.
boundary[3],
s.boundary[3]);
154 return (imaxx - iminx) * (imaxy - iminy);
164 assert(objp1->
sz.
x == 0 && objp1->
sz.
y == 0);
166 if(! xlp)
return false;
220 if (lp->
set == 0 || clp->set == 0)
222 if ((op->
pos.
x == 0.0 && op->
pos.
y == 0.0) ||
223 (cp->
pos.
x == 0.0 && cp->
pos.
y == 0.0))
255 if (intrsx[i] !=
NULL) {
256 double sa, maxa = 0.0;
263 if (intrsx[i]->lbl) {
267 maxa = fmax(sa, maxa);
287 if (intrsx[i] !=
NULL) {
288 double sa, maxa = 0.0;
295 if (intrsx[i]->lbl) {
299 maxa = fmax(sa, maxa);
323 for (
size_t i = 0; i < xlp->n_objs; i++) {
324 if(objp == &xlp->objs[i])
continue;
325 if(xlp->objs[i].sz.x > 0 && xlp->objs[i].sz.y > 0)
continue;
375 double xincr = (2 * lp->
sz.
x + objp->
sz.
x) / XLXDENOM;
376 double yincr = (2 * lp->
sz.
y + objp->
sz.
y) / XLYDENOM;
394 if (nbp.area < bp.area)
401 if (nbp.area < bp.area)
411 if (nbp.area < bp.area)
418 if (nbp.area < bp.area)
428 if (nbp.area < bp.area)
435 if (nbp.area < bp.area)
442 if (nbp.area < bp.area)
446 if (intrsx[XLPXNY] || intrsx[XLCXNY] || intrsx[XLNXNY] || intrsx[XLPXCY] || intrsx[XLPXPY]) {
447 if (!intrsx[XLCXNY] && !intrsx[XLNXNY]) {
452 lp->
pos.
x += xincr) {
456 if (nbp.area < bp.area)
460 if (!intrsx[XLPXCY] && !intrsx[XLPXPY]) {
465 lp->
pos.
y -= yincr) {
469 if (nbp.area < bp.area)
479 if (intrsx[XLNXPY] || intrsx[XLCXPY] || intrsx[XLPXPY] || intrsx[XLNXCY] || intrsx[XLNXNY]) {
480 if (!intrsx[XLCXPY] && !intrsx[XLPXPY]) {
485 lp->
pos.
x -= xincr) {
489 if (nbp.area < bp.area)
493 if (!intrsx[XLNXCY] && !intrsx[XLNXNY]) {
498 lp->
pos.
y += yincr) {
502 if (nbp.area < bp.area)
515 for (
size_t i = 0; i < xlp->n_objs; i++) {
520 hp->d.data = &xlp->objs[i];
523 const double x = hp->d.rect.boundary[0] +
524 (hp->d.rect.boundary[2] - hp->d.rect.boundary[0]) / 2;
525 const double y = hp->d.rect.boundary[1] +
526 (hp->d.rect.boundary[3] - hp->d.rect.boundary[1]) / 2;
527 assert(x >= INT_MIN && x <= INT_MAX);
528 assert(y >= INT_MIN && y <= INT_MAX);
529 const point pi = {.
x = (int)x, .y = (
int)y};
541 int size=
dtsize(xlp->hdx), freed=0;
542 while(
dtsize(xlp->hdx) ) {
556 for (HDict_t *op =
dtfirst(xlp->hdx); op; op =
dtnext(xlp->hdx, op)) {
558 RTreeInsert(xlp->spdx, op->d.rect, op->d.data, &xlp->spdx->root);
576 XLabels_t *xlp =
xlnew(objs, n_objs, lbls, n_lbls, params);
596 for (
size_t i = 0; i < n_objs; i++) {
597 if (objs[i].lbl == 0)
602 }
else if(bp.area == 0) {
606 }
else if (params->
force == 1) {
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)