Re: [AD] new GUI focus selection algorithm

[Sven Sandberg <svens@xxxxxxxxxx>]

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