A little project of mine

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

elminster
Posts: 1560
Joined: Mon Feb 26, 2007 1:56 pm UTC
Location: London, UK, Dimensions 1 to 42.
Contact:

A little project of mine

Postby elminster » Wed Jan 14, 2009 5:53 pm UTC

Just thought I'd share something I was doing recently.
So... after reading THIS thread, I was enthused by Dropzone's attempt at the problem. I thought I could better it. The problem is to try pack all the xkcd comics into as small square/rectangle as possible. So effectively it's a sort of 2d box packing problem. Now, I have little experience (if not none) with these kind of algorithms, but I trying to make my own. So far it's around 500 lines in C#.

It works by searching for the closest point to the centre via a square spiral pattern, then, depending which direction it's headed, it will search either right/down/left/up for N/S/E/W respectively. Since it's a spiral, the outside edge will always have space and the largest that can fit in there will be placed. If not, if will find the largest rectangle that would contact 3 sides* and invalidate it so the search misses that area next time. Little hard to explain and, annoyingly, it's a bit hard to find descriptive comments.
*I've not taken into account ones that contact 2 sides (e.g. The spiral is at the bottom left going clockwise and just about to go north, there may not be an edge downward in a few cases), which only matters for very few cases, but wouldn't provide optimal packing without it.

My head's hurting just working out the maths of it. Working out what x/y location would be for the Nth step of a square spiral was hard enough (An optimisation rather than incrementing the spiral from the start hundreds of thousands of times) since I haven't done maths for 5 years (Also, I nearly failed it back then).

Here is the most recent test done on only a selection of 112 of the 500+ comics (Note: I only left it to do some)...
Spoiler:
BMPTest.gif
BMPTest.gif (198.73 KiB) Viewed 2574 times
Unfortunately, the bitmap class in C# seems to crap out around 10000x12000 pixels (Oddly, only about 1/4 of the times). That's about a 460mb bitmap at 32bpp, which I wouldn't have thought is too much of a problem since I have 4gb of ram and a 4.5gb paging file. So looks like I'm need to do it in parts separately and stitch them on my own.
Image

elminster
Posts: 1560
Joined: Mon Feb 26, 2007 1:56 pm UTC
Location: London, UK, Dimensions 1 to 42.
Contact:

Re: A little project of mine

Postby elminster » Thu Jan 15, 2009 6:19 pm UTC

So, with a few more optimisations, I manage to get the run time down from several hours (without finishing mind you) using only 112 of the comics to 50 seconds using 527 of the comics.
The final picture is 12005x12065 that's 144840325pixels (144.8mp) in around 480mb uncompressed png, the total number of pixels in all the comics is 128853984 (128.9mp). So an approximate packing efficiency of 89%.

Here's a preview of all the comics together (1200x1206pixels):
Spoiler:
Image
The odd patterns at the edge are probably due to the gaps that only contact 2 sides while searching I mentioned (Usable spaces, rendered unusable because the way it searches), which, if taken into account, could improve efficiency a few more %. I can see that I could manually do some of the outside ones better than the program did. However, it is designed so that worst case is on the very outer edge.

Also, never try stitch a grid of 4x4 images at 5000x5000 each in photoshop... The total I/O (Measured in task manager) topped out over 10tb before I decided it was going too slow; by then I knew I could do it in 13k*13k in a 2x2 grid which wasn't too long to stitch.
Image

User avatar
Cytoplasm
Posts: 1310
Joined: Tue Oct 23, 2007 1:00 am UTC
Location: EE.UU.(+ Cheese)

Re: A little project of mine

Postby Cytoplasm » Thu Jan 15, 2009 6:44 pm UTC

this is quite a time consuming and tricky task. Good luck! I would become quite obsessed and crazed over this sort of idea.
¡No tengo miedo a fantasmas!

Spoiler:
Cytoplasm: I have catoragized some of my family into lolcats.
Felstaff: For a drudging Thursday afternoon, that level of cuteness has really made my day. Can... Can I keep you?

Felstaff wrote:
Cytoplasm wrote:shannonigans

<3

Filius Nullius
Posts: 72
Joined: Sat Apr 05, 2008 12:24 am UTC

Re: A little project of mine

Postby Filius Nullius » Thu Jan 15, 2009 7:55 pm UTC

This is the coolest thing I've seen on the forums in a few days, I think the image that your able to generate would make for a wonderful (large-scale) poster

Tyr_oathkeeper
Posts: 30
Joined: Tue Mar 18, 2008 4:03 am UTC

Re: A little project of mine

Postby Tyr_oathkeeper » Fri Jan 16, 2009 3:35 am UTC

Very nifty. Is it just me or are the comics on the right cut off?
Nice project.

pastrybot
Posts: 24
Joined: Sat Dec 27, 2008 4:32 pm UTC
Contact:

Re: A little project of mine

Postby pastrybot » Fri Jan 16, 2009 5:04 am UTC

Do you have a copy of the full 12k by 12k image? I might be able to get access to a poster version of it...
Vecheeso wrote:Mount Rushmore is my porn name

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: A little project of mine

Postby Qoppa » Fri Jan 16, 2009 5:10 am UTC

Tyr_oathkeeper wrote:Very nifty. Is it just me or are the comics on the right cut off?
Nice project.
Right click on the picture and go 'view image'. It's the forum software cutting it off.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

elminster
Posts: 1560
Joined: Mon Feb 26, 2007 1:56 pm UTC
Location: London, UK, Dimensions 1 to 42.
Contact:

Re: A little project of mine

Postby elminster » Sat Jan 17, 2009 10:34 am UTC

pastrybot wrote:Do you have a copy of the full 12k by 12k image? I might be able to get access to a poster version of it...
Sure. I uploaded a copy with a white background to here [LINK].
It's an 83mb PNG file, compressed in a rar file to 73.5mb, 11995x12065. It's pretty big, so you maybe waiting a while for it to do anything in picture editing applications. It uses over 1gb of ram when loaded in photoshop CS4 on mine and took over a minute to save, even though I have reasonably high end pc.
I'll upload the one with the black background (a 91.9mb PNG file) later (Saving the monthly bandwidth cap).

p.s. By fixing a bug and flipping the spiral around, was able to get size down to 11963x11864. I'm going to sleep before it gets too late to.

p.p.s. Wait... wait... one more. Down to 11861x11892 by fixing an optimisation. Here's a preview (Click it for 1186x1189 version):
Image
Image

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: A little project of mine

Postby Carnildo » Sat Jan 17, 2009 10:54 am UTC

elminster wrote:
pastrybot wrote:Do you have a copy of the full 12k by 12k image? I might be able to get access to a poster version of it...
Sure. I uploaded a copy with a white background to here [LINK].
It's an 83mb PNG file, compressed in a rar file to 73.5mb, 11995x12065.

Nice job. Open it up, zoom to 100%, and scroll at random -- it's better than an archive dive.

It's pretty big, so you maybe waiting a while for it to do anything in picture editing applications. It uses over 1gb of ram when loaded in photoshop CS4 on mine and took over a minute to save, even though I have reasonably high end pc.

The nice thing about having a 64-bit OS and more RAM than I know what to do with: the image opened almost instantly, and the GIMP isn't having any trouble with me scrolling around at random.

User avatar
Emu*
Posts: 689
Joined: Mon Apr 28, 2008 9:47 am UTC
Location: Cardiff, UK
Contact:

Re: A little project of mine

Postby Emu* » Sat Jan 17, 2009 5:23 pm UTC

Just an idea, but could this be combined with Silverlight's download-different-levels-of-zoom hardrock cafe site?

think googlemaps incremental downloading, but looking at toons :-)
Cosmologicon wrote:Emu* implemented a naive east-first strategy and ran it for an hour, producing results that rivaled many sophisticated strategies, visiting 614 cells. For this, Emu* is awarded Best Deterministic Algorithm!

pastrybot
Posts: 24
Joined: Sat Dec 27, 2008 4:32 pm UTC
Contact:

Re: A little project of mine

Postby pastrybot » Sat Jan 17, 2009 10:15 pm UTC

Hmm, so should I shell out $50 and get this printed large format?
Vecheeso wrote:Mount Rushmore is my porn name

Bassoon
Posts: 476
Joined: Wed Nov 28, 2007 10:58 pm UTC
Location: Wisconsin

Re: A little project of mine

Postby Bassoon » Sat Jan 17, 2009 11:57 pm UTC

This is really neato. Perhaps a version two will be able to group comics that follow a vague storyline and then optimize space.

elminster
Posts: 1560
Joined: Mon Feb 26, 2007 1:56 pm UTC
Location: London, UK, Dimensions 1 to 42.
Contact:

Re: A little project of mine

Postby elminster » Sun Jan 18, 2009 9:24 am UTC

After a lot of stressing while trying to figure out why some images were overlapping. I found out that the new comics that I downloaded manually (Rather than through a program) had a DPI of 66.7 rather than 96 and, despite everything being measured in pixels, it decided to draw them larger than the others. *sigh* Typical...

Anyway, through some further optimisations and improvements, I managed to get the new picture with all the comics upto now (Totalling 130102425 pixels) into an image of 11923x11880 (141645240 pixels) meaning an efficiency of approximately 91.9%, which finishes in 10secs. Preview (Same images, just black is easy to see the gaps. Click for larger):
Image . Image
Full version with white background here (As above): [LINK]
Image

sparr
Posts: 6
Joined: Wed Feb 20, 2008 6:03 am UTC

Re: A little project of mine

Postby sparr » Wed Mar 11, 2009 12:41 am UTC

The way your algorithm is described sounds rotationally symmetric... Why is it that the stair stepping gap pattern seems to appear more often on the right and bottom?


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 5 guests