Re: Additional issues to address for the constraints_experiments branch?

Elijah Newren wrote:

On 11/14/05, Rob Adams <readams readams net> wrote:
Things to worry about:
Solving constraints for partial-width struts can introduce interesting

For example, if you have something like:
_________  ____
|  Strut | |Wnd|

if you make the strut on the right taller so that it intersects the
window, it will push the window over to the left, which then violates
the other strut constraint.

Right, this one was a royal pain in the butt to figure out, and I
completely changed my method a few different times to get it right. :-)

So you need to have a pretty powerful constraints solver to be able to
handle cases like this.  The while (!satisfied) try to satisfy loop
implements a technique called heuristic repair.  This is a search
technique used to constraint satisfaction problems that are generally
not too tightly constrained; that is relatively easy problems.  The idea
is to simply move the window around so as few constraints are violated
as possible, then iterate to try to find a feasible position.  The
advantage of heuristic repair is that it is blazing fast, which it needs
to be in the metacity constraint solver since it runs a lot when
moving/resizing windows.  The disadvantage is that it's not a complete
search algorithm, i.e. it's not guaranteed to find a solution in the
general case.  However, given the way the constraints in metacity work,
it will nearly always find a solution if one exists (though its possible
that there is no solution).

So I'd be interested to hear what search algorithm you use to solve the
constraint satisfaction problem in your branch.  Iterative deepening A*

Nope, it's not iterative at all.  Whenever any struts are modified, I
generate what I've called a minimal rectangle spanning set.  This set
is a list of rectangles with the property that a window will fit "on
the screen" (meaning screen minus struts) if and only if it fits
inside one of those rectangles.  While generating this list is
definitely more costly than a single iteration of your heuristic
repair, it's something I only have to generate once instead of once
every heuristic repair iteration of every meta_window_constrain[1].

The relevant function is
meta_rectangle_get_minimal_spanning_set_for_region() from boxes.c
(plus other *_region() functions) and is thoroughly tested in
testboxes.c:test_regions_okay() (and with related functionality
thoroughly tested by test_region_fitting(), test_clamping_to_region(),
test_clipping_to_region(), and test_shoving_into_region()).


[1] Okay, I fibbed a little about the once thing.  I have to do it
number_xineramas + 1 times inside the update struts stuff, since that
is the number of spanning sets I generate -- one for the whole screen
plus one for each xinerama.  (I do one for each xinerama because I've
also added a constrain-to-single-xinerama constraint for
non-user-movement in order to fix Davyd's gripe about windows stupidly
positioning themselves split across xineramas).
metacity-devel-list mailing list
metacity-devel-list gnome org
I am probably missing something, but what about:

- Generate a GdkRegion "strut_region" of all the struts
- rects = strut_region.get_rectangles();
- for each r in rects:
add r.x and r.x + r.width to list of x coordinates unless they are there already add r.y and r.y + r.height to list of y coordinates unless they are there already
- for each x in x coordinates
      for each y in y coordinates
           add (x, y) to list of intersection points
- for each point in list of intersection points
      for each corner of the window
if positioning the window corner at the point doesn't conflict,
             then we have found a possible window position
- look at all the generated window positions, and take the one closest to the desired position. Then move the corner that was attached to an intersection point as far
 towards the desired position as possible.

So it's O(n^2) in the number of struts, but completely simple and guaranteed to
find the optimal solution if a solution exists at all.


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]