Algorithm-RectanglesContainingDot_XS

 view release on metacpan or  search on metacpan

RectanglesContainingDot_XS.xs  view on Meta::CPAN

        for (i=0; i<top; i++, rect++) {
            /* printf("."); fflush(stdout); */
            *rect = &(chunk->rects[i]);
        }
    }
    
    return algo->div = div;
}

double
find_best_cut(pTHX_ struct rectangle **rects, int size, int dir,
              double *bestv, int *sizel, int *sizer) {
    double **v0, **v1, **vc0, **vc1;
    double v, med, best;
    int op, cl;
    int i;

    my_assert(bestv);
    my_assert(sizel);
    my_assert(sizer);
    
    Newy(v0, size + 1, double *);
    Newy(v1, size + 1, double *);
    
    v0[size] = v1[size] = NULL;
    
    vc0 = v0; vc1 = v1;
    

RectanglesContainingDot_XS.xs  view on Meta::CPAN

        }
        /* printf( "%d: v0=%g, v1=%g\n", i, *(v0[i]), *(v1[i])); fflush(stdout); */
    }
    v0[size] = v1[size] = NULL;

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

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

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

RectanglesContainingDot_XS.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 = (double)l * (double)l + (double)r * (double)r;

        my_assert(good >= 0);
        
        if (good < best) {
            best = good;
            *bestv = v;
            *sizel = op;
            *sizer = size - cl;
        }
    }

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

void
part_division(pTHX_ struct rectangle **rects, int size,
              double cut, int dir,
              struct division **left, int left_size,
              struct division **right, int right_size) {

    int i;
    struct rectangle **rectsl, **rectsr;

RectanglesContainingDot_XS.xs  view on Meta::CPAN

int
subdivide_division(pTHX_ struct division *div) {
    int size;

    my_assert(div);
    
    size = div->size;
    if (size > MIN_DIVISION) {
        struct rectangle **rects = div->rects;
        double bestreq = 0.24 * size * size;
        double bestx, bestxx, besty, bestyy;
        int sizelx, sizerx, sizely, sizery;
        
        bestx = find_best_cut(aTHX_ rects, size, 'x', &bestxx, &sizelx, &sizerx);

        if (bestx > 0)
            besty = find_best_cut(aTHX_ rects, size, 'y', &bestyy, &sizely, &sizery);
        else
            besty = 1;

        if (bestx < besty) {
            if (bestx < bestreq) {
                // fprintf(stderr, "bestx: %f, bestreq: %f\n", bestx, bestreq);
                part_division(aTHX_ rects, size, bestxx, 'x', &(div->left), sizelx, &(div->right), sizerx);
                div->cut = bestxx;
                Safefry(div->rects);
                div->rects = NULL;
                return div->dir = 'x';
            }
        }
        else {
            if (besty < bestreq) {
                // fprintf(stderr, "besty: %f, bestreq: %f\n", besty, bestreq);
                part_division(aTHX_ rects, size, bestyy, 'y', &(div->left), sizely, &(div->right), sizery);
                div->cut = bestyy;
                Safefry(div->rects);
                div->rects = NULL;
                return div->dir = 'y';
            }
        }
    }
    return div->dir = 'n';
}

struct division *

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