Algorithm-BreakOverlappingRectangles

 view release on metacpan or  search on metacpan

BreakOverlappingRectangles.xs  view on Meta::CPAN

    DP(printf("cmp(%f, %f) => %d\n", fa, fb, (fa < fb) ? -1 : ((fa > fb) ? 1 : 0)));
    return (fa < fb) ? -1 : ((fa > fb) ? 1 : 0);
}

void
sort_inplace(pTHX_ double **v, int size) {
    sortsv((SV**)v, size, (SVCOMPARE_t)&double_cmp);
}

static NV
find_best_cut(pTHX_ AV *rects, I32 start, I32 end, int dir, NV *bestv) {
    NV **v0, **v1, **vc0, **vc1;
    NV v, med, best;
    int op, cl;
    int i;
    SV **svs;
    I32 size = end - start;

    my_assert(bestv);
    
    DUMP("fbc  in", rects, start);
    DP(fprintf(stderr, "end: %d\n", end));
    
    Newx(v0, size + 1, NV *);
    Newx(v1, size + 1, NV *);
    
    v0[size] = v1[size] = NULL;
    
    vc0 = v0; vc1 = v1;

BreakOverlappingRectangles.xs  view on Meta::CPAN

            v1[i] = nv + Y1;
        }
    }
    v0[size] = v1[size] = NULL;

    sort_inplace(aTHX_ v0, size);
    sort_inplace(aTHX_ v1, size);
    
    op = cl = 0;
    med = 0.5 * size;
    best =  .24 * sqr(size);

    my_assert(best >= 0);
             
    while (*v0 && *v1) {
        NV v, good;
        NV l, r;
        
        v =  (**v0 <= **v1) ? **v0 : **v1;

        while (*v0 && v == **v0) {
            op++;
            v0++;

BreakOverlappingRectangles.xs  view on Meta::CPAN

        my_assert(op > 0 && op <= size);
        my_assert(cl >= 0 && cl <= size);
        
        l = op - med;
        r = size - cl - med;
        good = sqr(l) + sqr(r);

        my_assert(good >= 0);
        
        if (good < best) {
            DP(fprintf(stderr, "find_best_cut l: %.2f, r: %.2f, good: %.2f\n", l, r, good));
            best = good;
            *bestv = v;
        }
    }

    Safefree(vc0);
    Safefree(vc1);
    
    return best;
}

static void
_break(pTHX_ AV *rects, I32 start, AV *parts);

static void
_brute_force_merge(pTHX_ AV *rects, I32 start, AV *parts) {
    I32 i, len;
    for (i = start; i <= av_len(rects); i++) {
        SV *svr = (AvARRAY(rects))[i];

BreakOverlappingRectangles.xs  view on Meta::CPAN

        svs[end1] = last;
        av_push(parts, next);

        _brute_force_merge(aTHX_ rects, end1, parts);
    }
    return;
}

static void
_break(pTHX_ AV *rects, I32 start, AV *parts) {
    NV bestx, bestxx, besty, bestyy, div;
    int off;
    I32 i, j, middle, end;
    SV **svs;
    
    DUMP("break", rects, start);

    while (1) {

        end = av_len(rects) + 1;

        if ((end - start) <= BRUTEFORCECUTOFF)
            return _brute_force_break(aTHX_ rects, start, parts);

        bestx = find_best_cut(aTHX_ rects, start, end, 'x', &bestxx);
        besty = ((bestx == 0) ? 1 : find_best_cut(aTHX_ rects, start, end, 'y', &bestyy));

        if (bestx < besty) {
            off = X0;
            div = bestxx;
            DP(fprintf(stderr, "cutting at x=%.0f, best=%.2f\n", bestxx, bestx));
        }
        else {
            off = Y0;
            div = bestyy;
            DP(fprintf(stderr, "cutting at y=%.0f, best=%.2f\n", bestyy, besty));
        }
    
        svs = AvARRAY(rects);
        i = start;
        middle = end;
        while (i < middle) {
            SV *sv = svs[i];
            NV n0 = ((NV*)SvPV_nolen(sv))[off];
            if (n0 < div) {
                middle--;

ppport.h  view on Meta::CPAN

#ifndef UV_MAX
#  define UV_MAX                         PERL_ULONG_MAX
#endif

#endif

#ifndef IVSIZE
#  ifdef LONGSIZE
#    define IVSIZE LONGSIZE
#  else
#    define IVSIZE 4 /* A bold guess, but the best we can make. */
#  endif
#endif
#ifndef UVTYPE
#  define UVTYPE                         unsigned IVTYPE
#endif

#ifndef UVSIZE
#  define UVSIZE                         IVSIZE
#endif
#ifndef sv_setuv

ppport.h  view on Meta::CPAN

#endif

#ifndef PERL_MAGIC_backref
#  define PERL_MAGIC_backref             '<'
#endif

#ifndef PERL_MAGIC_ext
#  define PERL_MAGIC_ext                 '~'
#endif

/* That's the best we can do... */
#ifndef SvPV_force_nomg
#  define SvPV_force_nomg                SvPV_force
#endif

#ifndef SvPV_nomg
#  define SvPV_nomg                      SvPV
#endif

#ifndef sv_catpvn_nomg
#  define sv_catpvn_nomg                 sv_catpvn