ref: 0ba3b3ea5128ab3d28b5951b1abfa5b4336079dc
parent: 671771e4799498d22262f134274e804461a90e40
author: Halfwit <michaelmisch1985@gmail.com>
date: Mon Nov 7 02:53:38 PST 2016
initial refactoring to new algorithm, but there is an issue with growing - not stable
--- a/binpack.c
+++ b/binpack.c
@@ -25,7 +25,7 @@
unsigned x, y, w, h;
};
-size_t
+size_t
create_rect(struct input r[]) {size_t length = 0;
char line[50] = "";
@@ -38,7 +38,7 @@
}
/* (max bin size - blob size) / 2 */
-void
+void
center(const size_t length, struct output r[], struct mbin mb) {unsigned w = 0, h = 0;
for (size_t i = 0; i < length; i++) {@@ -60,6 +60,19 @@
for (unsigned i = 1; i < *bin_count; i++) { for (unsigned j = 0; j < *bin_count - i; j++) {+ /* If two bins can be logically made in to one bin, do so */
+ if (b[j + 1].x == b[j].x + b[j].w && b[j + 1].y == b[j].y && b[j].h == b[j].h) {+ b[j].w += b[j + 1].w;
+ b[j + 1].h = 0;
+ b[j + 1].w = 0;
+ continue;
+ }
+ if (b[j + 1].y == b[j].y + b[j].h && b[j + 1].x == b[j].x && b[j + 1].w == b[j].w) {+ b[j].h += b[j + 1].h;
+ b[j + 1].h = 0;
+ b[j + 1].w = 0;
+ continue;
+ }
if ((b[j + 1].w * b[j + 1].h) > (b[j].w * b[j].h)) {temp = b[j];
b[j] = b[j + 1];
@@ -123,7 +136,7 @@
}
}
-void
+void
save_rect(struct bins bin[], struct output out[], struct input r[], size_t i, size_t j, struct mbin mb)
{/* Store rect x y w h wid */
@@ -130,9 +143,8 @@
out[i] = (struct output){bin[j].x + (mb.gaps / 2), bin[j].y + (mb.gaps / 2), r[i].min_w, r[i].min_h, r[i].wid};}
-/* Main algorithm */
-bool
-pack_bin(struct output out[], struct input r[], const size_t length, unsigned *bin_width, unsigned *bin_height, struct mbin mb)
+bool
+pack_bin(const size_t length, struct output out[], struct mbin mb, struct input r[])
{/* initialize bins */
struct bins bin[100];
@@ -141,7 +153,7 @@
}
/* default bin */
- bin[0] = (struct bins){ 0, 0, *bin_width + mb.gaps, *bin_height + mb.gaps};+ bin[0] = (struct bins){ 0, 0, mb.x, mb.y};size_t bin_count = 1;
bool rect_fits;
@@ -151,8 +163,7 @@
/* loop through each bin */
for (size_t j = 0; j < bin_count; j++) {- /* rect fits in current bin */
- if (r[i].min_w + mb.gaps <= bin[j].w && r[i].min_h + mb.gaps <= bin[j].h) {+ if ((r[i].min_w + r[i].max_w) / 2 <= bin[j].w && (r[i].min_h + r[i].max_h) / 2 <= bin[j].h) {rect_fits = true;
save_rect(bin, out, r, i, j, mb);
create_bins(bin, out, i, j, &bin_count, mb);
@@ -161,45 +172,43 @@
}
}
if (rect_fits == false)
- return true;
+ return true;
}
return false;
}
bool
-resize(struct output out[], struct input r[], const size_t length, unsigned *bin_width, unsigned *bin_height, struct mbin mb, size_t index)
+resize(const size_t length, struct output out[], struct mbin mb, struct input r[])
{- for (size_t i = index; i < length; i++) {- unsigned limitcheck = 0;
+ size_t packed_bin = 0;
+ for (size_t i = 0; i < length; i++) {- while (pack_bin(out, r, length, bin_width, bin_height, mb)) {- if (limitcheck == mb.x)
- return false;
- limitcheck++;
+ /* If we're within 1, bin is fully packed */
+ if (r[i].max_h - r[i].min_h < 2 && r[i].max_w - r[i].min_w < 2) {+ packed_bin++;
+ continue;
}
- /* If rect can grow */
- if (out[i].h < r[i].max_h)
- r[i].min_h += 1;
- if (out[i].w < r[i].max_w)
- r[i].min_w += 1;
+ /* if binpack succeeds, we can grow --> set min as current, else set max as current */
+ if(pack_bin(length, out, mb, r) && r[i].max_w - r[i].min_w > 1) {+ r[i].max_w = (r[i].min_w + r[i].max_w) / 2;
+ } else {+ r[i].min_w = (r[i].min_w + r[i].max_w) / 2;
+ }
- sort_input(r, length);
+ if(pack_bin(length, out, mb, r) && r[i].max_h - r[i].min_h > 1) {+ r[i].max_h = (r[i].min_h + r[i].max_h) / 2;
+ } else{+ r[i].min_h = (r[i].min_h + r[i].max_h) / 2;
+ }
}
- /* max_h to handle cases of smaller windows */
- unsigned w = 0, h = 0;
-
- for (size_t i = index; i < length; i++) {- if (w < (out[i].w + out[i].x))
- w = out[i].w + out[i].x + mb.gaps;
- if (h < (out[i].h + out[i].y))
- h = out[i].h + out[i].y + mb.gaps;
- }
-
- return ((h < mb.y + (mb.gaps / 2)) && (w < mb.x + (mb.gaps / 2)));
+ if (packed_bin == length)
+ return false;
+ return true;
}
+
int
main(int argc, char *argv[])
{@@ -240,55 +249,16 @@
sort_input(r, length);
- unsigned bin_width = mb.x;
- unsigned bin_height = mb.y;
- /* TODO: We're going to instead use a binary search approach
- * to find a size for each bin, so the large windows optimization
- * can be omitted
- */
- /* Test if we can use maximums on all windows */
- bool no_large_windows = true;
- for (size_t i = 0; i < length; i++) {- struct input temp = r[i];
- r[i].min_w = r[i].max_w;
- r[i].min_h = r[i].max_h;
+ /* Initial pack to establish out bins */
+ pack_bin(length, out, mb, r);
- if (pack_bin(out, r, length, &bin_width, &bin_height, mb)) {- r[i] = temp;
- no_large_windows = false;
- }
- }
+ while(resize(length, out, mb, r));
- unsigned limitcheck = 0;
-
- if (no_large_windows == false) {- bin_width = r[0].min_w;
- bin_height = r[0].min_h;
-
- while (pack_bin(out, r, length, &bin_width, &bin_height, mb)) {- /* if we've ran this long, something is up */
- if (limitcheck == mb.x)
- return EXIT_FAILURE;
-
- limitcheck++;
- }
-
- limitcheck = 0;
- for (size_t i = 0; i < length; i++) {- /* Square out the blob as best as we can */
- while (resize(out, r, length, &bin_width, &bin_height, mb, i)) {- if (limitcheck == mb.x)
- return EXIT_FAILURE;
- limitcheck++;
- }
- }
- }
-
center(length, out, mb);
for (size_t i = 0; i < length; i++) { printf("%d %d %d %d %lx\n", out[i].x, out[i].y, out[i].w, out[i].h, out[i].wid);}
-
+
return EXIT_SUCCESS;
}