Algorithm-BreakOverlappingRectangles
view release on metacpan or search on metacpan
BreakOverlappingRectangles.xs view on Meta::CPAN
#define my_assert(a) if(!(a)) _failed_assertion(aTHX_ #a, __LINE__, __FILE__)
#define DP(f) f
#define DUMP(msg, av, start) _dump(aTHX_ (msg), (av), (start))
static void
_dump(pTHX_ char *msg, AV *rects, I32 start) {
I32 end = av_len(rects) + 1;
SV **svs = AvARRAY(rects);
I32 i;
fprintf (stderr, "%s = start: %d, end: %d", msg, start, end);
for (i = start; i < end; i++) {
SV *sv = svs[i];
if (SvOK(sv)) {
STRLEN len, j;
NV* nv = (NV*)SvPV(svs[i], len);
IV* iv = (IV*)(SvPV_nolen(svs[i]) + IDOFFSET);
len = (len - IDOFFSET) / sizeof(IV);
fprintf (stderr, " [%.0f %.0f %.0f %.0f |", nv[0], nv[1], nv[2], nv[3]);
for (j = 0; j < len; j++)
fprintf(stderr, " %d", iv[j]);
fprintf(stderr, "]");
}
else
fprintf(stderr, " undef");
}
fprintf(stderr, "\n");
fflush(stderr);
}
void _failed_assertion(pTHX_ char *str, int line, char *file) {
fprintf(stderr, "assertion %s failed at %s line %d\n", str, line, file);
fflush(stderr);
exit(1);
}
#endif
static SV *
av_sure_fetch(pTHX_ AV *av, I32 i) {
SV **sv = av_fetch(av, i, 0);
my_assert(sv);
return *sv;
BreakOverlappingRectangles.xs view on Meta::CPAN
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;
svs = AvARRAY(rects) + start;
size = end - start;
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;
}
BreakOverlappingRectangles.xs view on Meta::CPAN
((x[0] != x[1]) || (x[2] != x[3])) ) ||
((y[0] == y[1]) && (y[2] == y[3])) ) {
NV b = ((sqr(x[1] - x[0]) + sqr(x[1] - x[3]))
< (sqr(x[2] - x[0]) + sqr(x[2] - x[3])) ? x[1] : x[2]);
if ((r[X0] < b) && (r[X1] > b)) {
SV *svcp = newSVsv(svr);
NV *cp = (NV*)SvPV_nolen(svcp);
cp[X0] = b;
av_push(rects, svcp);
/* fprintf(stderr, "[%f %f %f %f] -> [%f %f %f %f], [%f %f %f %f]\n",
r[0], r[1], r[2], r[3],
cp[0], cp[1], cp[2], cp[3],
b, r[1], r[2], r[3]); fflush(stderr); */
r[X1] = b;
}
if ((p[X0] < b) && (p[X1] > b)) {
SV *svcp = newSVsv(svp);
NV *cp = (NV*)SvPV_nolen(svcp);
cp[X0] = b;
av_push(parts, svcp);
/* fprintf(stderr, "[%f %f %f %f] -> [%f %f %f %f], [%f %f %f %f]\n",
p[0], p[1], p[2], p[3],
cp[0], cp[1], cp[2], cp[3],
p[0], p[1], b, p[3]); fflush(stderr); */
p[X1] = b;
}
}
else {
NV b = ((sqr(y[1] - y[0]) + sqr(y[1] - y[3]))
< (sqr(y[2] - y[0]) + sqr(y[2] - y[3])) ? y[1] : y[2]);
if ((r[Y0] < b) && (r[Y1] > b)) {
SV *svcp = newSVsv(svr);
NV *cp = (NV*)SvPV_nolen(svcp);
cp[Y0] = b;
av_push(rects, svcp);
/* fprintf(stderr, "[%f %f %f %f] -> [%f %f %f %f], [%f %f %f %f]\n",
r[0], r[1], r[2], r[3],
cp[0], cp[1], cp[2], cp[3],
r[0], b, r[2], r[3]); fflush(stderr); */
r[Y1] = b;
}
if ((p[Y0] < b) && (p[Y1] > b)) {
SV *svcp = newSVsv(svp);
NV *cp = (NV*)SvPV_nolen(svcp);
cp[Y0] = b;
av_push(parts, svcp);
/* fprintf(stderr, "[%f %f %f %f] -> [%f %f %f %f], [%f %f %f %f]\n",
p[0], p[1], p[2], p[3],
cp[0], cp[1], cp[2], cp[3],
p[0], p[1], p[2], b); fflush(stderr); */
p[Y1] = b;
}
}
continue;
}
}
j++;
}
}
BreakOverlappingRectangles.xs view on Meta::CPAN
while (end-- >= middle)
av_push(parts, av_pop(rects));
return _brute_force_merge(aTHX_ rects, start, parts);
}
while (--end1 >= start) {
SV *last, *next;
SV **svs;
DP(fprintf(stderr, "bfb: start: %d, end1: %d, end: %d\n", start, end1, av_len(rects) + 1));
svs = AvARRAY(rects);
last = svs[AvFILLp(rects)];
svs[AvFILLp(rects)--] = &PL_sv_undef;
next = svs[end1];
svs[end1] = last;
av_push(parts, next);
_brute_force_merge(aTHX_ rects, end1, parts);
}
BreakOverlappingRectangles.xs view on Meta::CPAN
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--;
BreakOverlappingRectangles.xs view on Meta::CPAN
i++;
}
DUMP("b2", rects, start);
end += start - middle;
off += 2;
i = start;
middle = end;
DP(fprintf(stderr, "i: %d, middle: %d\n", i, middle));
while (i < middle) {
SV *sv = svs[i];
NV n0 = ((NV*)SvPV_nolen(sv))[off];
if (n0 > div) {
middle--;
svs[i] = svs[middle];
svs[middle] = sv;
}
else
i++;
PerlIO_flush||5.007003|
PerlIO_get_base||5.007003|
PerlIO_get_bufsiz||5.007003|
PerlIO_get_cnt||5.007003|
PerlIO_get_ptr||5.007003|
PerlIO_read||5.007003|
PerlIO_seek||5.007003|
PerlIO_set_cnt||5.007003|
PerlIO_set_ptrcnt||5.007003|
PerlIO_setlinebuf||5.007003|
PerlIO_stderr||5.007003|
PerlIO_stdin||5.007003|
PerlIO_stdout||5.007003|
PerlIO_tell||5.007003|
PerlIO_unread||5.007003|
PerlIO_write||5.007003|
Perl_warner_nocontext|5.006000||p
Perl_warner|5.006000||p
PoisonFree|5.009004||p
PoisonNew|5.009004||p
PoisonWith|5.009004||p
vwarner||5.006000|
vwarn||5.006000|
wait4pid|||
warn_nocontext|||vn
warner_nocontext|||vn
warner|5.006000|5.004000|pv
warn|||v
watch|||
whichsig|||
write_no_mem|||
write_to_stderr|||
xmldump_all|||
xmldump_attr|||
xmldump_eval|||
xmldump_form|||
xmldump_indent|||v
xmldump_packsubs|||
xmldump_sub|||
xmldump_vindent|||
yyerror|||
yylex|||
( run in 0.990 second using v1.01-cache-2.11-cpan-49f99fa48dc )