spatial-navigation

Improve the distance function for selecting the best candidate

Background

Selecting the best candidate step in the spec

To select the element which will gain the focus from the search origin, the distance value is calculated for each candidate with following steps:

(1) Find the point P1 within the edges of the boundary box of the search origin and the point P2 within that of a candidate which will make the smallest Euclidean distance between P1 and P2.

(2) With P1 and P2, the distance value is measured by the function as follows:

distance: A + B + C - D

(3) Among the candidates, the one which has the smallest distance value is selected as the best candidate.

NOTE:

Problem

When the spatial navigation is used for the real pages, there are unexpected behavior in UX point of view because of the distance function above.

Case 1

The focus moves to the unexpected element with the smallest Euclidean distance but not aligned with the search origin in the navigation direction.

e.g.) Related test case

Case 2

The focus moves to the unexpected candidate when there are multiple candidates which have the same Euclidean distance.

e.g.) Related test case

Case 3

The focus moves to the unexpected candidate when the Euclidean distances of candidates are slightly different (about 1px), but the degree of alignment with the search origin are significantly different.

e.g.) Related test case

Approach

The distance formula needs to change as below:

1. Remove the factor about calculating the absolute distance in the navigation direction between a candidate and the search origin.

In Case 1, the aligned elements are more desirable element to gain the focus. But calculating the absolute distance in the navigation direction (B Factor of the distance formula in the spec) penalizes elements which are aligned, so it’s the reason for the unexpected behavior.

See the test result

2. Add the factor about calculating the degree of alignment between a candidate and the search origin.

This aims to deal with the issues of Case 2 and Case 3.

As in Case 2, when there are multiple candidates which have the same Euclidean distance from the search origin, it’s ambiguous to decide where the focus will move to.

To avoid ambiguity, the factor for calculating degree of alignment in the navigation direction between a candidate and the search origin is suggested. It is calculated as

Factor = degree of alignment * alignWeight

degree of alignment = (length of the edge of the area of intersection between a candidate and the search origin / length of the edge of the search origin)

Also, considering Case 3, alignWeight is decided as 5.

See the test result

Summary of the proposal

As-Is To-Be
Point Selection Closest point from another element on the each element's edge Closest point from another element on the each element's edge
Distance formula Distance formula = A + B + C - D
  • A: The Euclidean distance between points
  • B: The absolute distance in the navigation direction between points
  • C: The absolute distance in the direction which is orthogonal to the navigation direction between points
    • Orthogonal weight for LEFT and RIGHT direction: 30
    • Orthogonal weight for UP and DOWN direction: 2
  • D: The square root of the area of intersection between the boundary box of a candidate and the search origin
Distance formula = A - B + C - D
  • A: The Euclidean distance between points
  • B: The degree of alignment in the navigation direction between a candidate and the search origin
    • Align weight: 5
  • C: The absolute distance in the direction which is orthogonal to the navigation direction between points
    • Orthogonal weight for LEFT and RIGHT direction: 30
    • Orthogonal weight for UP and DOWN direction: 2
  • D: The square root of the area of intersection between the boundary box of a candidate and the search origin

General Rules (of To-Be)

Additional Experiment

Also the most appropriate way to select the point from each element for measuring distance is considered.
Selecting the point from the center of an element was considerable, but it didn’t solve the problem when candidates are aligned with the same Euclidean distance from the search origin. (Case 2 and Case 3)

The conclusion is keeping the method in the spec, which is choosing the point from each element’s edges which is the closest point from another element.

See the test result

Test

We’ve collected the test cases which show the expected result of the spatial navigation behavior.
See the list of ux test cases here.

1. Selection of points

For investigating the proper result about selecting the best candidate, there are four ways to select the points for calculating the distance as below:

NOTE: The distance formula is (A + B + C - D ) as in the spec.

Method Expected Spec
Closest points on edges Closest points among vertices Center points Center points on edges
Grid Layout 2 1 / 1 1 / 1 1 / 1 0 / 1 0 / 1
Grid Layout 3 2 / 2 0 / 2 0 / 2 2 / 2 2 / 2
Grid Layout 4 4 / 4 4 / 4 4 / 4 4 / 4 4 / 4
Grid Align 1 1 / 1 0 / 1 0 / 1 1 / 1 1 / 1
Grid Align 2 1 / 1 0 / 1 0 / 1 1 / 1 1 / 1
Grid Align 3 1 / 1 1 / 1 0 / 1 1 / 1 1 / 1
Grid Align 4 1 / 1 1 / 1 1 / 1 0 / 1 0 / 1
Element Intersect 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1
Element Intersect 2 1 / 1 1 / 1 1 / 1 0 / 1 0 / 1
Transformed elements 1 / 1 1 / 1 0 / 1 1 / 1 1 / 1
Fragmented elements 3 / 3 1 / 3 0 / 3 1 / 3 1 / 3
Total 17 / 17 11 / 17 8 / 17 12 / 17 12 / 17

2. Remove redundant distance value

  • Distance function
  • Method Expected Spec
    A + B + C - D A + C - D
    Grid Layout 1 1 / 1 0 / 1 0 / 1
    Grid Layout 2 1 / 1 1 / 1 1 / 1
    Grid Layout 3 2 / 2 0 / 2 0 / 2
    Grid Layout 4 4 / 4 4 / 4 4 / 4
    Grid Align 1 1 / 1 0 / 1 0 / 1
    Grid Align 2 1 / 1 0 / 1 0 / 1
    Grid Align 3 1 / 1 1 / 1 1 / 1
    Grid Align 4 1 / 1 1 / 1 1 / 1
    Element Intersect 1 1 / 1 1 / 1 1 / 1
    Element Intersect 2 1 / 1 1 / 1 1 / 1
    Total 16 / 16 12 / 16 12 / 16

    3. Considering the degree of alignment

  • Distance function
  • Method Expected Spec
    Original formula Proposed formula
    Grid Layout 1 1 / 1 0 / 1 1 / 1
    Grid Layout 2 1 / 1 1 / 1 1 / 1
    Grid Layout 3 2 / 2 0 / 2 2 / 2
    Grid Layout 4 4 / 4 4 / 4 4 / 4
    Grid Align 1 1 / 1 0 / 1 1 / 1
    Grid Align 2 1 / 1 0 / 1 0 / 1
    Grid Align 3 1 / 1 1 / 1 1 / 1
    Grid Align 4 1 / 1 1 / 1 1 / 1
    Element Intersect 1 1 / 1 1 / 1 1 / 1
    Element Intersect 2 1 / 1 1 / 1 1 / 1
    Total 16 / 16 12 / 16 16 / 16