The problem
Positioning labels on a map, a chart, a plan is a problem every UI developer face at one time or another if he has the chance to work on rich business app. This problem is NP-Hard for non-trivial cases. I faced that issue twice. First while building a silverlight charting library, and then very recently for positioning labels around a pin on a plan. This post isn't about how we solved those two cases. For the charting problem, we went for an algorithmic solution which was working but not optimal. For the second, I don't know how they solved it as I didn't took the job.
Solution by Physics system
But the other night, as I contributed Chipmunk bindings to monotouch, one of the reply I got was roughly "I'm not into gaming stuffs, I don't really care. but it looks nice". That got me thinking. First, I'm not a game developer[1][2] neither, and second, you probably should care. One of the most elegant solution I was able to come with for solving a label-positioning problem is to use recipes normally used by game developers. It involves a physics engine, some bodies and some springs.
Let's say every label you want to position is a physics body with a mass (the same for all the labels), a shape (the rectangle bounding box is a good approximation). Let's say then than all those bodies are attached with a (sampling) spring to the pin. If we run a physics engine on this setup, let the springs pull, let the shapes collide, and it'll stabilise itself to a local optimum. With a some luck, or the right amount of initial entropy, you might even reach the global optimum, but that's not important. Multiples pins with labels close to each other? Check. A lot of labels ? Check. Restrict the labels to a zone or avoid some other? Check, just add constraints or shapes to help the collision algorithms.Implementation
But then, how hard is this to implement? If you have a physics engine you can use, this is probably shorter and cleaner to implement than any other method (except the obvious place-at-random-retry-if-it-overlaps). Here's my implementation. It uses monotouch and the chipmunk bindings (What next
Now you can play with the spring parameters and the number of iteration to get the results you expect. You can also use ellipses instead of rectangular bounding boxes. Expect smoother and more natural placement in this case. If you have a lot of labels, use different restLength for the labels you want close to the labels and the one you want a bit farther. A more complex system will take more time (more iterations) to stabilise, so adapt the number of steps, but in any case, keep the dt (time delta) parameter low, experience shows good results between 1/60 and 1/20.Want more than this from me ? Contact me, I'm open for contracting.
[1] I don't like categorisation. Nor being categorised. I'm not an UI dev, I'm not C# dev, I'm not a mobile dev. I'm not even a developer. I have a bagful of hats and wear the ones that gets the job done.
[2] But still, I wrote and tested most of the cocos2d and chipmunk bindings for mono touch, I ported a few games to those platform, and very recently wrote my first game with my 6 y.o. in a day (more on this later).
Wow, thank you very much for sharing this and for porting the necessary methods to c#! This is a great solution to "positioning stuff which other wise overlaps"-problem.
ReplyDeleteAt the time of the blog entry, it was indeed only the required parts to make it works. But expect a complete binding quite soon (missing at this point: other constraints and collisions handling).
ReplyDelete