view release on metacpan or  search on metacpan

RectanglesContainingDot_XS.xs  view on Meta::CPAN

            *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;

    my_assert(left);
    my_assert(right);
    my_assert(left_size);
    my_assert(right_size);
    my_assert(right_size < size);
    my_assert(left_size < size);
    
    *left = allocate_division(aTHX_ left_size);
    *right = allocate_division(aTHX_ right_size);

    // fprintf(stderr, "%d => %d, %d\n", size, left_size, right_size);
    
    rectsl = (*left)->rects;
    rectsr = (*right)->rects;

    for (i = 0; i < size; i++) {
        struct rectangle *rect = rects[i];
        if (dir == 'x') {
            if (cut >= rect->x0) *(rectsl++) = rect;
            if (cut < rect->x1) *(rectsr++) = rect;
        }
        else {
            if (cut >= rect->y0) *(rectsl++) = rect;
            if (cut < rect->y1) *(rectsr++) = rect;
        }
    }
    my_assert(rectsl == (*left)->rects + (*left)->size);
    my_assert(rectsr == (*right)->rects + (*right)->size);
}

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 *
division_containing_dot(pTHX_ struct division *div, double x, double y) {
    while(1) {
        int dir = div->dir;
        if (!dir)
            dir = subdivide_division(aTHX_ div);

        switch(dir) {
        case 'x':
            div = (x <= div->cut) ? div->left : div->right;
            break;
        case 'y':
            div = (y <= div->cut) ? div->left : div->right;
            break;
        default:
            my_assert(div->rects);
            return div;
        }
    }
}



MODULE = Algorithm::RectanglesContainingDot_XS		PACKAGE = Algorithm::RectanglesContainingDot_XS		

void