Re: Additional issues to address for the constraints_experiments branch?

[Elijah Newren <newren gmail com>]

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