Improve spatial navigation on overlapping elements.

Source/core/page/SpatialNavigation.cpp

 /*
  * Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies)
  * Copyright (C) 2009 Antonio Gomes <tonikitoo@webkit.org>
  *
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
@@ skipping 31 matching lines @@
 
 namespace WebCore {
 
 static RectsAlignment alignmentForRects(FocusDirection, const LayoutRect&, const LayoutRect&, const LayoutSize& viewSize);
 static bool areRectsFullyAligned(FocusDirection, const LayoutRect&, const LayoutRect&);
 static bool areRectsPartiallyAligned(FocusDirection, const LayoutRect&, const LayoutRect&);
 static bool areRectsMoreThanFullScreenApart(FocusDirection, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize);
 static bool isRectInDirection(FocusDirection, const LayoutRect&, const LayoutRect&);
 static void deflateIfOverlapped(LayoutRect&, LayoutRect&);
 static LayoutRect rectToAbsoluteCoordinates(Frame* initialFrame, const LayoutRect&);
-static void entryAndExitPointsForDirection(FocusDirection, const LayoutRect& startingRect, const LayoutRect& potentialRect, LayoutPoint& exitPoint, LayoutPoint& entryPoint);
 static bool isScrollableNode(const Node*);
 
 FocusCandidate::FocusCandidate(Node* node, FocusDirection direction)
     : visibleNode(0)
     , focusableNode(0)
     , enclosingScrollableBox(0)
     , distance(maxDistance())
     , parentDistance(maxDistance())
     , alignment(None)
     , parentAlignment(None)
@@ skipping 72 matching lines @@
 // operations.
 // * a = Current focused node's rect.
 // * b = Focus candidate node's rect.
 static bool areRectsFullyAligned(FocusDirection direction, const LayoutRect& a, const LayoutRect& b)
 {
     LayoutUnit aStart, bStart, aEnd, bEnd;
 
     switch (direction) {
     case FocusDirectionLeft:
         aStart = a.x();
-        bEnd = b.maxX();
+        bEnd = b.x();
         break;
     case FocusDirectionRight:
         aStart = b.x();
-        bEnd = a.maxX();
+        bEnd = a.x();
         break;
     case FocusDirectionUp:
         aStart = a.y();
         bEnd = b.y();
         break;
     case FocusDirectionDown:
         aStart = b.y();
         bEnd = a.y();
         break;
     default:
@@ skipping 19 matching lines @@
     //  ****************************  *****************************
     //  *  _          *   _ _ _ _  *  *         _   *      _ _    *
     //  * |_|     _   *  |_|_|_|_| *  *  _     |_|  *     |_|_|   *
     //  * |_|....|_|  *      .     *  * |_|....|_|  *       .     *
     //  * |_|    |_| (1)     .     *  * |_|    |_| (2)      .     *
     //  * |_|         *     _._    *  *        |_|  *    _ _._ _  *
     //  *             *    |_|_|   *  *             *   |_|_|_|_| *
     //  *             *            *  *             *             *
     //  ****************************  *****************************
 
-    //     Horizontal    Vertical        Horizontal     Vertical
-    //  ****************************  *****************************
-    //  *  _......_   *   _ _ _ _  *  *  _          *    _ _ _ _  *
-    //  * |_|    |_|  *  |_|_|_|_| *  * |_|     _   *   |_|_|_|_| *
-    //  * |_|    |_|  *  .         *  * |_|    |_|  *           . *
-    //  * |_|        (3) .         *  * |_|....|_| (4)          . *
-    //  *             *  ._ _      *  *             *        _ _. *
-    //  *             *  |_|_|     *  *             *       |_|_| *
-    //  *             *            *  *             *             *
-    //  ****************************  *****************************
-
-    return ((bMiddle >= aStart && bMiddle <= aEnd) // (1)
-            || (aMiddle >= bStart && aMiddle <= bEnd) // (2)
-            || (bStart == aStart) // (3)
-            || (bEnd == aEnd)); // (4)
+    return (bMiddle >= aStart && bMiddle <= aEnd) // (1)
+        || (aMiddle >= bStart && aMiddle <= bEnd); // (2)
 }
 
-// This method checks if |start| and |dest| have a partial intersection, either
-// horizontally or vertically.
+// This method checks if rects |a| and |b| are partially aligned either vertically or
+// horizontally. In general, rects whose either of edges falls between the top or
+// bottom of each other are considered partially-aligned.
+// This is a separate set of conditions from "fully-aligned" and do not include cases
+// that satisfy the former.
 // * a = Current focused node's rect.
 // * b = Focus candidate node's rect.
 static bool areRectsPartiallyAligned(FocusDirection direction, const LayoutRect& a, const LayoutRect& b)
 {
     LayoutUnit aStart  = start(direction, a);
     LayoutUnit bStart  = start(direction, b);
-    LayoutUnit bMiddle = middle(direction, b);
     LayoutUnit aEnd = end(direction, a);
     LayoutUnit bEnd = end(direction, b);
 
     // Picture of the partially aligned logic:
     //
     //    Horizontal       Vertical
     // ********************************
     // *  _            *   _ _ _      *
     // * |_|           *  |_|_|_|     *
     // * |_|.... _     *      . .     *
     // * |_|    |_|    *      . .     *
     // * |_|....|_|    *      ._._ _  *
     // *        |_|    *      |_|_|_| *
     // *        |_|    *              *
     // *               *              *
     // ********************************
     //
     // ... and variants of the above cases.
-    return ((bStart >= aStart && bStart <= aEnd)
-            || (bEnd >= aStart && bEnd <= aEnd)
-            || (bMiddle >= aStart && bMiddle <= aEnd));
+    return (bStart >= aStart && bStart <= aEnd)
+        || (bEnd >= aStart && bEnd <= aEnd);
 }
 
 static bool areRectsMoreThanFullScreenApart(FocusDirection direction, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize)
 {
     ASSERT(isRectInDirection(direction, curRect, targetRect));
 
     switch (direction) {
     case FocusDirectionLeft:
         return curRect.x() - targetRect.maxX() > viewSize.width();
     case FocusDirectionRight:
         return targetRect.x() - curRect.maxX() > viewSize.width();
     case FocusDirectionUp:
         return curRect.y() - targetRect.maxY() > viewSize.height();
     case FocusDirectionDown:
         return targetRect.y() - curRect.maxY() > viewSize.height();
     default:
         ASSERT_NOT_REACHED();
         return true;
     }
 }
 
 // Return true if rect |a| is below |b|. False otherwise.
+// For overlapping rects, |a| is considered to be below |b|
+// if both edges of |a| are below the respective ones of |b|
 static inline bool below(const LayoutRect& a, const LayoutRect& b)
 {
-    return a.y() > b.maxY();
+    return a.y() >= b.maxY()
+        || (a.y() >= b.y() && a.maxY() > b.maxY());
 }
 
 // Return true if rect |a| is on the right of |b|. False otherwise.
+// For overlapping rects, |a| is considered to be on the right of |b|
+// if both edges of |a| are on the right of the respective ones of |b|
 static inline bool rightOf(const LayoutRect& a, const LayoutRect& b)
 {
-    return a.x() > b.maxX();
+    return a.x() >= b.maxX()
+        || (a.x() >= b.x() && a.maxX() > b.maxX());
 }
 
 static bool isRectInDirection(FocusDirection direction, const LayoutRect& curRect, const LayoutRect& targetRect)
 {
     switch (direction) {
     case FocusDirectionLeft:
-        return targetRect.maxX() <= curRect.x();
+        return rightOf(curRect, targetRect);
     case FocusDirectionRight:
-        return targetRect.x() >= curRect.maxX();
+        return rightOf(targetRect, curRect);
     case FocusDirectionUp:
-        return targetRect.maxY() <= curRect.y();
+        return below(curRect, targetRect);
     case FocusDirectionDown:
-        return targetRect.y() >= curRect.maxY();
+        return below(targetRect, curRect);
     default:
         ASSERT_NOT_REACHED();
         return false;
     }
 }
 
 // Checks if |node| is offscreen the visible area (viewport) of its container
 // document. In case it is, one can scroll in direction or take any different
 // desired action later on.
 bool hasOffscreenRect(Node* node, FocusDirection direction)
@@ skipping 240 matching lines @@
     return rect;
 }
 
 LayoutRect frameRectInAbsoluteCoordinates(Frame* frame)
 {
     return rectToAbsoluteCoordinates(frame, frame->view()->visibleContentRect());
 }
 
 // This method calculates the exitPoint from the startingRect and the entryPoint into the candidate rect.
 // The line between those 2 points is the closest distance between the 2 rects.
+// Takes care of overlapping rects, defining points so that the distance between them
+// is zero where necessary
 void entryAndExitPointsForDirection(FocusDirection direction, const LayoutRect& startingRect, const LayoutRect& potentialRect, LayoutPoint& exitPoint, LayoutPoint& entryPoint)
 {
     switch (direction) {
     case FocusDirectionLeft:
         exitPoint.setX(startingRect.x());
-        entryPoint.setX(potentialRect.maxX());
+        if (potentialRect.maxX() < startingRect.x())
+            entryPoint.setX(potentialRect.maxX());
+        else
+            entryPoint.setX(startingRect.x());
         break;
     case FocusDirectionUp:
         exitPoint.setY(startingRect.y());
-        entryPoint.setY(potentialRect.maxY());
+        if (potentialRect.maxY() < startingRect.y())
+            entryPoint.setY(potentialRect.maxY());
+        else
+            entryPoint.setY(startingRect.y());
         break;
     case FocusDirectionRight:
         exitPoint.setX(startingRect.maxX());
-        entryPoint.setX(potentialRect.x());
+        if (potentialRect.x() > startingRect.maxX())
+            entryPoint.setX(potentialRect.x());
+        else
+            entryPoint.setX(startingRect.maxX());
         break;
     case FocusDirectionDown:
         exitPoint.setY(startingRect.maxY());
-        entryPoint.setY(potentialRect.y());
+        if (potentialRect.y() > startingRect.maxY())
+            entryPoint.setY(potentialRect.y());
+        else
+            entryPoint.setY(startingRect.maxY());
         break;
     default:
         ASSERT_NOT_REACHED();
     }
 
     switch (direction) {
     case FocusDirectionLeft:
     case FocusDirectionRight:
         if (below(startingRect, potentialRect)) {
             exitPoint.setY(startingRect.y());
-            entryPoint.setY(potentialRect.maxY());
+            if (potentialRect.maxY() < startingRect.y())
+                entryPoint.setY(potentialRect.maxY());
+            else
+                entryPoint.setY(startingRect.y());
         } else if (below(potentialRect, startingRect)) {
             exitPoint.setY(startingRect.maxY());
-            entryPoint.setY(potentialRect.y());
+            if (potentialRect.y() > startingRect.maxY())
+                entryPoint.setY(potentialRect.y());
+            else
+                entryPoint.setY(startingRect.maxY());
         } else {
             exitPoint.setY(max(startingRect.y(), potentialRect.y()));
             entryPoint.setY(exitPoint.y());
         }
         break;
     case FocusDirectionUp:
     case FocusDirectionDown:
         if (rightOf(startingRect, potentialRect)) {
             exitPoint.setX(startingRect.x());
-            entryPoint.setX(potentialRect.maxX());
+            if (potentialRect.maxX() < startingRect.x())
+                entryPoint.setX(potentialRect.maxX());
+            else
+                entryPoint.setX(startingRect.x());
         } else if (rightOf(potentialRect, startingRect)) {
             exitPoint.setX(startingRect.maxX());
-            entryPoint.setX(potentialRect.x());
+            if (potentialRect.x() > startingRect.maxX())
+                entryPoint.setX(potentialRect.x());
+            else
+                entryPoint.setX(startingRect.maxX());
         } else {
             exitPoint.setX(max(startingRect.x(), potentialRect.x()));
             entryPoint.setX(exitPoint.x());
         }
         break;
     default:
         ASSERT_NOT_REACHED();
     }
 }
 
@@ skipping 32 matching lines @@
 
     LayoutRect nodeRect = candidate.rect;
     LayoutRect currentRect = current.rect;
     deflateIfOverlapped(currentRect, nodeRect);
 
     if (!isRectInDirection(direction, currentRect, nodeRect))
         return;
 
     LayoutPoint exitPoint;
     LayoutPoint entryPoint;
-    LayoutUnit sameAxisDistance = 0;
-    LayoutUnit otherAxisDistance = 0;
     entryAndExitPointsForDirection(direction, currentRect, nodeRect, exitPoint, entryPoint);
 
+    LayoutUnit xAxis = exitPoint.x() - entryPoint.x();
+    LayoutUnit yAxis = exitPoint.y() - entryPoint.y();
+
+    LayoutUnit navigationAxisDistance;
+    LayoutUnit orthogonalAxisDistance;
+
     switch (direction) {
     case FocusDirectionLeft:
-        sameAxisDistance = exitPoint.x() - entryPoint.x();
-        otherAxisDistance = absoluteValue(exitPoint.y() - entryPoint.y());
+    case FocusDirectionRight:
+        navigationAxisDistance = xAxis.abs();
+        orthogonalAxisDistance = yAxis.abs();
         break;
     case FocusDirectionUp:
-        sameAxisDistance = exitPoint.y() - entryPoint.y();
-        otherAxisDistance = absoluteValue(exitPoint.x() - entryPoint.x());
-        break;
-    case FocusDirectionRight:
-        sameAxisDistance = entryPoint.x() - exitPoint.x();
-        otherAxisDistance = absoluteValue(entryPoint.y() - exitPoint.y());
-        break;
     case FocusDirectionDown:
-        sameAxisDistance = entryPoint.y() - exitPoint.y();
-        otherAxisDistance = absoluteValue(entryPoint.x() - exitPoint.x());
+        navigationAxisDistance = yAxis.abs();
+        orthogonalAxisDistance = xAxis.abs();
         break;
     default:
         ASSERT_NOT_REACHED();
         return;
     }
 
-    float x = (entryPoint.x() - exitPoint.x()) * (entryPoint.x() - exitPoint.x());
-    float y = (entryPoint.y() - exitPoint.y()) * (entryPoint.y() - exitPoint.y());
+    double euclidianDistancePow2 = (xAxis * xAxis + yAxis * yAxis).toDouble();
+    LayoutRect intersectionRect = intersection(currentRect, nodeRect);
+    double overlap = (intersectionRect.width() * intersectionRect.height()).toDouble();
 
-    float euclidianDistance = sqrt(x + y);
+    // Distance calculation is based on http://www.w3.org/TR/WICD/#focus-handling
+    candidate.distance

[tkent, 2013/12/06 01:16:11]

nit: I don't think we need to break this into two lines. The expression is not
very long.

[Krzysztof Olczyk, 2014/04/04 11:52:15]

Done.

+        = sqrt(euclidianDistancePow2) + navigationAxisDistance+ orthogonalAxisDistance * 2 - sqrt(overlap);
 
-    // Loosely based on http://www.w3.org/TR/WICD/#focus-handling
-    // df = dotDist + dx + dy + 2 * (xdisplacement + ydisplacement) - sqrt(Overlap)
-
-    float distance = euclidianDistance + sameAxisDistance + 2 * otherAxisDistance;
-    candidate.distance = roundf(distance);
     LayoutSize viewSize = candidate.visibleNode->document().page()->mainFrame()->view()->visibleContentRect().size();
     candidate.alignment = alignmentForRects(direction, currentRect, nodeRect, viewSize);
 }
 
 bool canBeScrolledIntoView(FocusDirection direction, const FocusCandidate& candidate)
 {
     ASSERT(candidate.visibleNode && candidate.isOffscreen);
     LayoutRect candidateRect = candidate.rect;
     for (Node* parentNode = candidate.visibleNode->parentNode(); parentNode; parentNode = parentNode->parentNode()) {
         LayoutRect parentRect = nodeRectInAbsoluteCoordinates(parentNode);
@@ skipping 46 matching lines @@
     LayoutRect rect = virtualRectForDirection(direction, rectToAbsoluteCoordinates(area->document().frame(), area->computeRect(area->imageElement()->renderer())), 1);
     return rect;
 }
 
 HTMLFrameOwnerElement* frameOwnerElement(FocusCandidate& candidate)
 {
     return candidate.isFrameOwnerElement() ? toHTMLFrameOwnerElement(candidate.visibleNode) : 0;
 };
 
 } // namespace WebCore