spatial_navigation module

Introduction

Spatial navigation is used for navigating through links and forms elements (and in the future possibly other elements as well). All these navigable elements will be referred to as links, except when it obviously is not.

Spatial navigation roughly consists of three parts:

Module wiki page.

Memory

Memory documentation.

API

See the API documentation

The Algorithm

The main goal for the algorithm is to select the best link to navigate to. It also has to make sure that we can reach all links, and not get trapped in a loop. We also determine an alternative link that we use if no link is found using the primary algorithm. Below I make the assumption that we are always navigating down.

EvaluateLink()

Returns if the link is better (lower rank) than the previous best link. It can return one of BEST_ELEMENT, BEST_ELEMENT_BUT_CLOSE, NOT_BEST_BUT_CLOSE, NOT_BEST, ALTERNATIVE_ELEMENT or NOT_IN_SECTOR. BEST_ELEMENT, NOT_BEST and NOT_IN_SECTOR are what you would expect. The *_BUT_CLOSE ones are like the previous but they are close to the current best link. That is, a NOT_BEST_BUT_CLOSE link just not made it to be the best link (determined by SN_FUZZY_MARGIN). The reason we are doing this is because of dynamic pop-up menus used on many sites. We can then chose to navigate to a NOT_BEST_BUT_CLOSE link if it closer to the current link by some other measure (here distance in the document tree). Hence, we stay in the menu instead of navigating to a link that is closer but (partly) hidden by the menu.

LinkInSearchSector()

Returns if a link is in the search sector related to the current link. The search sector is starting at the lower corners of the current and widens down - like a cone. If we are navigating left or right the cone is narrower than if we are navigating up or down. The rationale behind this is that links are often wider than they are high (think text links). Since links sometimes overlap we need to take care of this case as well.

LinkValue()

Returns a rank of the link compared to the current link. The rank consists of a rank and a sub-rank. The rank represents the euclidean distance between the link and the current link, and small ranks are better. For the same reason we use different search sectors depending on if we are navigating vertically or horizontally we use a weighted euclidean distance (the level curve becomes an ellipse instead of circle). Sub-rank is only used when links are overlapping or when the links are close each other.

When we have no overlap and the links are far away from each other, the distance is measured from the middle of the lower edge of the current link to the closest part of the link.

This does not work well when the link is close to the current link, where a link right under the current link will get a big advantage compared to a link which is slightly on the side (but still below the current link). So we use a smooth transition, adjusting the coefficient to make the level curve ellipse (where links have the same rank) flatter and always including the lower corners of the current link. We are also treating overlapping links different.