Bug 50120 – Spatial Navigation: I would like to submit some improvements

• Status: UNCONFIRMED
• Component: WebCore Misc.

[Elias Politakis]

I have been working on Spatial Navigation for a while and found some improvements I would like to share with this community, hoping that they would help. I am not a developer on this project, just passing-by and thought of leaving some hints (that work).

1. I suggest a different distance function taking into account overlays and the centers of the rectangles.
2. The euclidean distance is "hacked" to bypass an ambiguity problem appearing with symmetrically positioned rects.
3. entryAndExitPointsForDirection has been edited to get rid of max(). Works better is use centers instead.
4. sameDirection has different implementation when rects overlap (uses centers).
5. sameAxis is using projections in order to determine if two rects are on the same axis.
6. The solution returns a negative is euclidean distance to "favor" rects on the same axis instead of zero. This hack requires a decimal shift at the end. I used const POSITIVE_RANGE = 10000.
7. You will notice the code is Java.. J2ME to be exact, for mobile phones, so sorry for the integers and lack of floats but I program CLDC1.0 which has no floats. Still, it works.
8. The code has been tested excessively with several rect formations explicitly designed for this purpose, and it works.

I hope this helps.

Elias Politakis


////////////////////////////////////////////////////////////////////////////
private static int distanceFunction(int direction, fxRect currentRect, fxRect nodeRect)
{
    int D,ED,OV,DX,DY,HX,HY,SA=0,OA=0;
        
    if(currentRect==null || nodeRect==null) return MAX_DISTANCE;
    if(!sameDirection(direction, currentRect, nodeRect)) return MAX_DISTANCE;
    
    ED = eucledianDistance(direction, currentRect, nodeRect, true, ClosestEdges);
    OV = overlayDistance(direction, currentRect, nodeRect);
    DX = displacement(direction, AxisX, currentRect, nodeRect, ClosestEdges);
    DY = displacement(direction, AxisY, currentRect, nodeRect, ClosestEdges);
    HX = displacement(direction, AxisX, currentRect, nodeRect, Centers);
    HY = displacement(direction, AxisY, currentRect, nodeRect, Centers);
            
    switch(direction)
    {
    case FocusDirectionLeft:    OA = DY; break;
    case FocusDirectionRight:   OA = DY; break;
    case FocusDirectionUp:      OA = DX; break;
    case FocusDirectionDown:    OA = DX; break;
    }
    
    D = POSITIVE_RANGE + ED + (DX + DY) + (HX + HY) + 2 * (OA + SA) - OV;
    
    return D;
}

////////////////////////////////////////////////////////////////////////////
private static int eucledianDistance(int direction, fxRect rectA, fxRect rectB, boolean sameAxisCheat, int calculation)
{
    if(sameAxisCheat)
    {
        if(sameAxis(direction, rectA, rectB))
        {
            // We apply an ambiguity-hack to bypass a selection problem
            // that appears when 4 rectangles are symetrically positioned arround
            // a fifth rectangle, and all rectangles having the same dimensions.
            // The hack makes up/down skiping rectangles that are not on the same
            // axis by setting ED to its negative.
            
            switch(direction)
            {
            case FocusDirectionUp:
            case FocusDirectionDown:
                return - eucledianDistance(direction, rectA, rectB, false, Centers);
            }
        }
    }
    
    int DX,DY,D,i,s=0;
    
    switch(calculation)
    {
    case Centers:
    
    	DX = (rectA.cx() - rectB.cx());
    	DY = (rectA.cy() - rectB.cy());
        return fxMath.sqrt(DX*DX+DY*DY);
    
    case ClosestEdges:
    
        fxPoint ptA = new fxPoint();
        fxPoint ptB = new fxPoint();
        entryAndExitPointsForDirection(direction, rectA, rectB, ptA, ptB);
        return fxMath.sqrt((ptA.X - ptB.X) * (ptA.X - ptB.X) + (ptA.Y - ptB.Y) * (ptA.Y - ptB.Y));
        
    case AllEdges:
        
        for(i=0; i<3; i++)
        {
            DX = rectA.pointX(i) - rectB.pointX(i);
            DY = rectA.pointY(i) - rectB.pointY(i);
            D = fxMath.sqrt(DX * DX + DY * DY);
            s += D;
        }
        return (s / 4);
    }
    
    return 0;
}

////////////////////////////////////////////////////////////////////////////
private static int displacement(int direction, int Axis, fxRect rectA, fxRect rectB, int calculation)
{
    int D=0;
    
    switch(calculation)
    {
    case Centers:
    
        D = (Axis==AxisX ? (rectA.cx() - rectB.cx()) : (rectA.cy() - rectB.cy()));
    	break;
    	
    case ClosestEdges:
    
        fxPoint ptA = new fxPoint();
        fxPoint ptB = new fxPoint();
        entryAndExitPointsForDirection(direction, rectA, rectB, ptA, ptB);
        
        D = (Axis==AxisX ? (ptA.X - ptB.X) : (ptA.Y - ptB.Y));
      	break;
    }
    
    return Math.abs(D);
}

////////////////////////////////////////////////////////////////////////////
private static int overlayDistance(int direction, fxRect rectA, fxRect rectB)
{
    if(sameAxis(direction, rectA, rectB))
    {
        switch(direction)
    	{
        case FocusDirectionLeft:
            if(rectA.intersects(rectB) && (rectB.right > rectA.left))
                return (Math.abs(rectB.right - rectA.left));
            break;
            
        case FocusDirectionRight:
            if(rectA.intersects(rectB) && (rectA.right > rectB.left))
                return (Math.abs(rectA.right - rectB.left));
            break;
            
        case FocusDirectionUp:
            if(rectA.intersects(rectB) && (rectA.top > rectB.bottom))
                return (Math.abs(rectA.top - rectB.bottom));
            break;
            
        case FocusDirectionDown:
            if(rectA.intersects(rectB) && (rectA.bottom > rectB.top))
            	return (Math.abs(rectA.bottom - rectB.top));
            break;
        }
    }
    return 0;
}

////////////////////////////////////////////////////////////////////////////
private static void entryAndExitPointsForDirection(int direction, fxRect startingRect, fxRect potentialRect, fxPoint exitPoint, fxPoint entryPoint)
{
    switch(direction)
    {
    case FocusDirectionLeft:
        exitPoint.X = (startingRect.left);
        entryPoint.X = (potentialRect.right);
        break;
    
    case FocusDirectionUp:
        exitPoint.Y = (startingRect.top);
        entryPoint.Y = (potentialRect.bottom);
        break;
        
    case FocusDirectionRight:
        exitPoint.X = (startingRect.right);
        entryPoint.X = (potentialRect.left);
        break;
        
    case FocusDirectionDown:
        exitPoint.Y = (startingRect.bottom);
        entryPoint.Y = (potentialRect.top);
        break;	        
    }

    switch(direction)
    {
    case FocusDirectionLeft:
    case FocusDirectionRight:
    
        if((below(startingRect, potentialRect)))
        {
            exitPoint.Y = (startingRect.top);
            entryPoint.Y = (potentialRect.bottom);
        }
        else if((below(potentialRect, startingRect)))
        {
            exitPoint.Y = (startingRect.bottom);
            entryPoint.Y = (potentialRect.top);
        }
        else
        {
            exitPoint.Y = startingRect.cy();
            entryPoint.Y = (exitPoint.Y);
        }
        break;
    
    case FocusDirectionUp:
    case FocusDirectionDown:
    
        if((rightOf(startingRect, potentialRect)))
        {
            exitPoint.X = (startingRect.left);
            entryPoint.X = (potentialRect.right);
        }
        else if((rightOf(potentialRect, startingRect)))
        {
            exitPoint.X = (startingRect.right);
            entryPoint.X = (potentialRect.left);
        }
        else
        {
            exitPoint.X = startingRect.cx();
            entryPoint.X = (exitPoint.X);
    	}
    	break;
    }
}

////////////////////////////////////////////////////////////////////////////
private static boolean sameDirection(int direction, fxRect rectA, fxRect rectB)
{
    if(rectA.intersects(rectB))
    {
        switch(direction)
        {
        case FocusDirectionLeft:    return (rectB.cx() < rectA.cx());
        case FocusDirectionRight:   return (rectB.cx() > rectA.cx());
        case FocusDirectionUp:      return (rectB.cy() < rectA.cy());
        case FocusDirectionDown:    return (rectB.cy() > rectA.cy());
    	}
	}
    else
    {
        switch(direction)
        {
        case FocusDirectionLeft:    return (rectB.left < rectA.left);
        case FocusDirectionRight:   return (rectB.right > rectA.right);
        case FocusDirectionUp:      return (rectB.top < rectA.top);
        case FocusDirectionDown:    return (rectB.bottom > rectA.bottom);
        }
    }
    
    return false;
}

////////////////////////////////////////////////////////////////////////////
private static boolean sameAxis(int direction, fxRect rectA, fxRect rectB) 
{
    int a1;
    int a2;
    int b1;
    int b2;
        
    switch(direction)
    {
    case FocusDirectionLeft:
    case FocusDirectionRight:
    
        a1 = rectA.top;
        a2 = rectA.bottom;
        b1 = rectB.top;
        b2 = rectB.bottom;
        return ((a1 <= b1 && b1 <= a2) || (b1 <= a1 && a1 <= b2));
            
    case FocusDirectionUp:
    case FocusDirectionDown:
        
        a1 = rectA.left;
        a2 = rectA.right;
        b1 = rectB.left;
        b2 = rectB.right;
        return ((a1 <= b1 && b1 <= a2) || (b1 <= a1 && a1 <= b2));
    }
    
    return false;
}

////////////////////////////////////////////////////////////////////////////
private static boolean below(fxRect A, fxRect B)
{
	return A.top > B.bottom;
}

////////////////////////////////////////////////////////////////////////////
private static boolean rightOf(fxRect A, fxRect B)
{
    return A.left > B.right;
}

[Yael]

Please follow the instructions at http://webkit.org/coding/contributing.html to submit a patch.
Also, please add test cases that show the improvement that will result from these changes.
thanks!

[Antonio Gomes]

You also better create separated bug for each issue.