new simplex-method constraint solver
Adam Megacz <[email protected]> Sat, 03 Apr 2004 19:35:37 -0800
| Newsgroups | gmane.comp.java.xwt.core |
|---|---|
| Organization | Myself |
| Message-ID | <[email protected]> |
Wow, I should've done this a long time ago. Way less places to make
stupid mistakes.
wget http://www.megacz.com/tmp/ibex.jar
wget http://www.megacz.com/tmp/main.t
java -jar ibex.jar main.t
Will commit shortly. Basically, the rules come down to this:
Unbreakable rules:
- Obey minwidth
- Columns must line up (ie if boxes 'a' and 'b' occupy the same
set of columns, their left and right edges must line up)
Optimize for these goals, in order of decreasing priority:
1. Try to make the sum of the column sizes equal the parent's size
2. Try not to make the sum of the columns any box occupies wider
than that box's maxwidth
3. Try to make all the columns as close to the same width as
possible
Using a linear constraint solver let me come up with specifications
this vague ("try not to ...") and actually code them the way they read
(check out the patch).
There's a TON of room for performance improvement in the constraint
solver (statically allocated arrays and fixedpoint math being at the
top of my list), but it's already decently fast. I don't anticipate
serious problems. There is also a new class of algorithms called
Interior Point Methods which perform way better in the "worst case",
but in the average case (aka real life) they're not outrageously
better:
http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/continuous/constrained/linearprog/section2_1_2.html
This also means that in Oxygen we can expose the full power of the
constraint solver to the programmer -- so you can say stuff like "the
area occupied by this box must be 400 square pixels" and its height
will grow as its width shrinks... ;)
- a
--
"It's lucky," he added, after a pause, "that there are such a lot of
islands in the world. I almost envy you, Mr. Watson."
-- Mustapha Mond