*From*: Soren Sandmann Pedersen <sandmann redhat com>*To*: Elijah Newren <newren gmail com>*Cc*: metacity-devel-list gnome org*Subject*: Re: Additional issues to address for the constraints_experiments branch?*Date*: Tue, 15 Nov 2005 12:01:33 -0500

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 Icompletely 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:

- 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

then we have found a possible window position

towards the desired position as possible.

find the optimal solution if a solution exists at all. Soren

**Follow-Ups**:**Re: Additional issues to address for the constraints_experiments branch?***From:*Elijah Newren

**References**:**Additional issues to address for the constraints_experiments branch?***From:*Elijah Newren

**Re: Additional issues to address for the constraints_experiments branch?***From:*Rob Adams

**Re: Additional issues to address for the constraints_experiments branch?***From:*Elijah Newren

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