[LAD] OT-ish: realtime 2d placement algorithms :-/

James Morris james at jwm-art.net
Fri Apr 30 22:10:12 UTC 2010


Hello,

I'm still trying to develop my boxy-sequencer idea. Basically, I've tried
out a couple of algorithms for window-manager-like box placement within a
grid and run into big problems.

Because I need help/advice/ideas, I'm posting here as it has some
relevance, and I've also posted to

http://stackoverflow.com/questions/2746590/fast-block-placement-algorithm-advice-needed

A quick run down of what's happened so far, the two algorithms:

The first I directly based on Fluxbox's Row Smart placement algorithm.
Testing only the data structures, (and with gcc -O0) jack kicked out my
client after around 200 boxes were placed in a 128x128 grid. I then
counted how many times the algorithm looped through the entire list of
boxes and discovered (not in RT for this) that the 256th box placement
required around 14000 scans through the list of 255 previously placed
boxes (i've decided 256 boxes will be the worst-case-scenario).

The second algorithm consists of a freebox data structure which represents
a rectangular area of free unused space. It also forms a node in a doubly
linked list, as well as four directional links to other freeboxes touching
it (with a maximum of one freebox touching each side of a freebox)...
turns out rather complex to implement fully: 700+ loc for a partial
implementation of row-smart left-to-right top-to-bottom placement - theres
also col-smart, r-to-l, b-to-t and all combinations.

Through stackoverflow, I've come across spatial hashing.

I wondered if anyone here uses this technique for the display of data
(would scrollable window views use such a thing?). worth it for a 128x128
grid etc?

I'm just after any general thoughts/insights you might have as to what
might or might not work. Anything worth pursuing.

I'm afraid there's all sorts of little things to be considered so if you
do have something to suggest, please read the stackoverflow post first.

Cheers for any help, if possible,
James.






More information about the Linux-audio-dev mailing list