Re: [AD] new GUI focus selection algorithm

[Elias Pschernig <elias@xxxxxxxxxx>]

On Wed, 2003-11-12 at 13:32, Sven Sandberg wrote:
> Eric Botcazou wrote:
> > I think a better algorithm could be:
> > - partition the screen into two parts (using the upper edge of the object for 
> > the up key and so on...); only objects fully contained within the part not 
> > containing the origin object are to be considered,
> > - take the middle of the upper edge of the object as the base point and the 
> > middle of the lower edge of the other objects as the target point for the up 
> > arrow,
> > - calculate a distance between the base point and all tentative target 
> > points,
> > - choose the valid object corresponding to the minimal distance.
> 
> Interesting, but there are still counterexamples: in the following 
> example, A can't be reached:
> 
>               B
>           I       C
> 
>         H     A     D
> 
>           G       E
>               F
> 
> :-)
> 
> I don't think there is an algorithm that works with all examples though.
> 
> More seriously though, the following might be a problem with your way of 
> computing distances:
> 
>     BBBBBBBBBBBBBBBBBBBBBBBBBB C
> 
>                          A
> 
> If you use distances between the middle of the top of A, and the middle 
> of the bottoms of B and C, then B is closer than C to A, which seems 
> unnatural.
> 
> Here is a suggestion of another way of computing distance: the distance 
> between A and B is the minimum, taken over all points a inside A and all 
> points b inside B, of the distance between a and b. Intuitively, if you 
> wanted to build a bridge between islands shaped as A and B, this would 
> give the length of the shortest possible such bridge. It can be computed 
> with this algorithm (assuming B's bottom is above A's top):
> 
>     dy = A.top - B.bottom
>     if (A.left > B.right)
>        return sqrt((A.left-B.right)^2 + dy^2)
>     else if (A.right < B.left)
>        return sqrt((B.left-A.right)^2 + dy^2)
>     else
>        return dy
> 
> (Here x^2 means the square of x.)
> 
> /Sven
> 

Yeah, I was just thinking a bit, and it seems to be the best solution
(Heh, actually, just finished a long mail discussing my algorithm and
Erics suggestion, gradually meething at it :) I was using this example:

A D
B Extremely long
C F

Where going up down from F/D wouldn't work. So, basically, just take the
original algorithm, and use the 'closest distance'. I'll try and
implement it until sometime in the weekend - should be much more simple
than my collision approach :P

-- 
Elias Pschernig <elias@xxxxxxxxxx>