Hacker News new | ask | show | jobs
by thesystemis 3460 days ago
there's actually no backend! the matching is done client side.

here's a technical write up:

https://developers.google.com/web/showcase/2016/land-lines

the trick for making it fast is vantage point trees (https://en.wikipedia.org/wiki/Vantage-point_tree) which help with nearest neighbor searching through extremely large data sets.

1 comments

are there natural limits to what kinds of lines are supported? For example drawing a Z doesn't work at all (whereas a C works well)

When drawing a Z the top bar of the Z is consistently ignored (I draw from the top down) and doesn't match anything in the picture, just randomly cuts into whatever is there. Whereas the remaining two strokes line up nicely. I think I don't need to screenshot it as it's quite consistent and you should see this yourself too. I wonder why this is...

the matching is based on the input (lines from the line detection) and we do some tricks to try to get better matches if the results aren't great. One trick is for matches that aren't super great, we start to trim the line slight from the start so if the first pass is a bad match, we try 95% of the line (ie, the last 95%) then trim is some more, etc.

another thing to note is that the app progressively loads data in the background so you get better results after the first minute or so once all the data is loaded -- the app launches with only 20% of the overall data.

But how can it be that you have extremely detailed photos matching all sorts of lines of all shapes (great job by the way! for normal curves I'm super impressed), but you don't have any with a natural Z in them? Zigzags aren't that uncommon - I can see some visually but your algorithm ignores them. I think it's not just due to the fact that you ignore the beginning of my line - it's that you somehow don't detect zigzags in the photos... Try drawing some capital Z's to see what I mean :)

I want to make sure to be positive, this is a super amazing result for almost all the curves I drew :) Just curious about that one.

no it's a really good question! I think this just has to do with the line detection algorithm and it tending to find more curves than sharp angle lines -- this is what the matches look like when you draw a Z:

http://imgur.com/a/YErmM

they are not as good as when you draw a curve and I think it's just trimming based on general poor matches. I've found if I round the Z or make the angle less extreme I can get better results.

interesting! thanks. Yes, most of the matches you linked are poor matches so what you said earlier about starting to trim the start of it must have applied.

I don't have more questions :) Thanks again for sharing this project - the result is fantastic, really shockingly good :) - goes to show...algorithms ftw :)

Your link to the image doesn't work.

Great work BTW

fixed! thanks!