Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The algorithm for a perfectly balanced photo gallery

crispymtn.com

Post reply on HN
Print view View original

51–60 of 104 posts

Re: The algorithm for a perfectly balanced photo gallery

#51

Post by Mgccl »

Since I'm a CS theory person, I can offer some theoretical improvements on the running time and make the problem even more general...

Instead of minimize the linear difference of partition, we might want to minimize the standard deviation, or basically any convex function, and still do it in the same time bound.

One can reduce this problem to find a k-edge path of minimum weight on a complete DAG. The naive algorithm will run in O(kn^2), but we can improve the running time to O(kn) by realize the weight on this DAG has the Monge property. This is very practical to implement.

I posed it as a problem on daily haskell exercise http://dailyhaskellexercise.tumblr.com/post/58060450750/the-....

In this application, k is very large. n is just a constant multiple of k. We can use a theoretically better algorithm that takes n2^O(sqrt(log n loglog n)) time. (this is almost O(n^(3/2))). I doubt it will ever be implemented with speed comparible to the O(kn) solution. See http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/sdarticle_...

I shall post a solution tomorrow since I'm currently touring NYC with my gf...

Re: The algorithm for a perfectly balanced photo gallery

#54

Post by quarterto »

hobbsy wrote: post #28
quarterto wrote: post #6

I just implemented pretty much the same thing from scratch for my wedding gallery¹. For each row, it tries 3-10 images, sums their aspect ratios, divides the total row width by the sum to get a candidate height, then picks the height that's closest to the average of the existing rows. To make things look a bit nicer, it rejects candidate rows with the same number of images as the last row. I might release the code on…

For me it displayed white rectangles initially - but disabling Adblock extension on Chrome worked (looks great). However if you then resize the window it seems to make all the images disappear (?)

It's lazy-loading the images (otherwise, BAM 30MB download). The blank screen thing is the resize handler breaking. I'm looking into it.

Re: The algorithm for a perfectly balanced photo gallery

#55

Post by EGreg »

This is why I always preferred vertical masonry. Sites such as VKontakte, Google Image Search, and the recent Flickr app tile things horizontally, but this sometimes means you have to crop the images to fit into your masonry. Not so with vertical masonry, which you can just resize to have constant width.

Re: The algorithm for a perfectly balanced photo gallery

#56

Post by mcgwiz »

It looks nice (much like Google Image results) but IMO it's not "equally distributed". For example, an image that has dimensions 800x531 gets ~2.3x the space as one with dimensions 531x800. That arbitrarily incentivizes/rewards landscape photos w.r.t. portraits. "Equally-distributed" would probably require an algorithm that works mosaically (without row constraints) and couldn't achieve "taking up all the space available [in a rectangular region]".

Still, looks nice.

Re: The algorithm for a perfectly balanced photo gallery

#57

Post by hadem »

nkuttler wrote: post #42

Can sombody tell me why this uses the photos as background images for divs? It seems to me like this gallery could also use img tags (which is semantic, crawlable, yadda..)

Perhaps to avoid easily right clicking the image and saving it to your machine? I know it is still easily downloadable, but not so much for a lot of users.

Re: The algorithm for a perfectly balanced photo gallery

#58

Post by uptown »

gbog wrote: post #50

Since when it is ok to suppose visitors know to click the escape key to go back. And where is the link to go up to the gallery. I had to mess with the url or I was gone for a long back button session. Morevoer it is very slow. Just to add some negativeness to the generaly positive comments here.

By "go back" i'm assuming you're referring to closing a full-size image. I've found three ways they can do this. They can press ESC. Click the image itself. Or click in the negative space surrounding the image excluding the "Previous" and "Next" regions.

Doesn't really seem like a huge issue since there are multiple ways to accomplish the objective, though I suppose a small "X" could be added if you wanted a visual cue.

Re: The algorithm for a perfectly balanced photo gallery

#59

Post by coldtea »

bane wrote: post #53

Side-topic. Shooting Holi [1] without putting your camera in an airtight sealed enclosure is a good way to ruin your equipment. http://en.wikipedia.org/wiki/Holi http://www.lensrentals.com/blog/2013/05/how-to-ruin-your-gea...

You must be fun at coloured powder throwing parties...

Re: The algorithm for a perfectly balanced photo gallery

#60

Post by ynniv »

coldtea wrote: post #59
bane wrote: post #53

Side-topic. Shooting Holi [1] without putting your camera in an airtight sealed enclosure is a good way to ruin your equipment. http://en.wikipedia.org/wiki/Holi http://www.lensrentals.com/blog/2013/05/how-to-ruin-your-gea...

You must be fun at coloured powder throwing parties...

Ruining your camera isn't especially fun either.
Post reply on HN