*From*: Elijah Newren <newren gmail com>*To*: Rob Adams <readams readams net>*Cc*: metacity-devel-list gnome org*Subject*: Re: Additional issues to address for the constraints_experiments branch?*Date*: Mon, 14 Nov 2005 14:51:14 -0700

On 11/14/05, Rob Adams <readams readams net> wrote: > Ok so you take your spanning set of safe regions, then given a window > position, find the closest region that will contain your window, either > completely for placement, or partially for repairing a violated > constraint while moving/resizing? Yes. > Another interesting question: one thing that I couldn't really hack into > the constraints.c stuff when I hacked in all my other fixes was that I > really wanted the titlebar visibility constraint to only apply if there > was no contiguous region of sufficient width. For example, in the > current code a top or bottom strut will push up a window if even one > pixel intersects the strut, but what I really wanted to do was make it > so that it would only push it up too much of the titlebar was covered, > but it was really not feasible to do it with the separate constraints > generated by each strut, since multiple struts could individually cover > parts of the titlebar. It sounds like you'd be able to get the behavior > I wanted with your algorithm, perhaps. You could (you first just expand the spanning rectangles by a certain amount in each direction and then do the shove_onscreen bit, very similar to how the partially_onscreen_constraint is currently done), but it might conflict with requirements from bug 122196, bug 143145, bug 136307, and bug 156699. > Example: > ______ ______ > Strut| | Strut > > Put a window into that tiny gap between two struts, it should get pushed > up, but make the gap wider than some minimum, and you'd be able to shove > it down there, ideally. > > Another thing that I'd be concerned about with your general approach is > simply to make sure you don't end up with perhaps unnecessarily > fragmented regions. For example, say you have an somewhat odd-sized > "safe zone" like this: > ____ > ___| | > | | > |_____| > > There's 3 sensible ways to break this into rectangles, which your > algorithm would do, either as 3 small rectangles or as 2 rectangles in > one of 2 ways. Regardless, it's necessary to make a choice in advance > as to how you break it up. But its possible that, depending how you > break it up, a window could fit into the "real" region but not fit into > any of the spanning rectangles. There are 3 intuitive ways to break this into rectangles (which you listed), none of which satisfy the property I listed before ("a window fits onscreen if and only if it fits in _one_ of these rectangles"). There is exactly 1 way to break this region up into rectangles that satisfies that property and contains no more rectangles than needed. My naming likely introduced the confusion, though. "minimal spanning set" makes people think of things like "linear independence" and quite possibly "orthogonality" (assuming a sufficient mathematics background of the person, of course), for which the natural assumption to extend to rectangles would imply "non-overlapping". I'd really like to pick a better name that doesn't imply that, because these rectangles must overlap in most partial-strut cases in order to satisfy the property I want. > So if your algorithm chose: > ____ > ___| | > | | | > |__|__| > > or > ____ > ___|__| > | | > |_____| > > or > ____ > ___|__| > | | | > |__|__| > > Your malicious adversary could make either a wider window (for the > first) or a taller window (for the second) such that it would fit into > the full region but not into 2 of those 3 possible subdivisions. The minimal set of spanning rectangles in this case would be exactly two rectangles which overlap: ____ | | | | |__| _______ | | |_____| > Also, I'm curious how your algorithm would behave in the case where > there exists no solution to the constraint satisfaction problem (or, as > above, your algorithm doesn't find it). The heuristic repair technique As far as I have been able to test (and I did have a number of testcases like this in the testboxes.c program I wrote), my algorithm will find the correct answer if it exists for this onscreen constraint (and will find the closest possible answer if no answer exists--see below) > would iterate for a bit before finally settling on some vaguely > ill-defined "best guess" solution that will satisfy some, though not > all, constraints. Ideally there'd be a scheme to relax certain "less > important" constraints and try again, but there isn't currently. Not in HEAD, but there is in the constraints_experiments branch. Basically, all constraints are prioritized. If all constraints can't simultaneously be satisfied, the less important ones are dropped. The priority might need some tweaking as I kind of just quickly picked some values; see the ConstraintPriority enum in constraints.c if you want to have a look (ignore the _huge_ comment above it, though, as that comment was just a brain dump from about two months ago and is now horribly dated and misleading) > But > with the region-finding solution you'd probably have to worry about it a > bit more, since you probably don't want to leave the window totally > non-constrained in such cases. Not an insurmountable problem. When shoving a window to the "onscreen" region, my algorithm looks for two things as it loops over the minimal spanning rectangle set: (a) how much the given rectangle can hold of the window, (b) how far the window would have to move to get there. The first property is more important--it must be able to hold all of the window in order for the constraint to not be violated (though, if no such rectangle exists, I can just pick the one which can hold the most). In the event that multiple rectangles from the spanning set can hold the window (or the same amount of the window if none can hold it), I choose the one that would require less movement of the window. See boxes.c:meta_rectangle_shove_into_region() if you want the full details. Cheers, Elijah

**Follow-Ups**:**Re: 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

**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

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

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