Re: Additional issues to address for the constraints_experiments branch?

[Soren Sandmann Pedersen <sandmann redhat com>]

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
> > interactions.
> >
> > For example, if you have something like:
> >           |Strut
> >           |_____
> > _________  ____
> > |  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*
> > perhaps?
> >    
>
> 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()).
>
> Cheers,
> Elijah
>
> [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
> http://mail.gnome.org/mailman/listinfo/metacity-devel-list
>  
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.


Soren