Fuzzy Direction Matching

Let’s say you have some interactive items on a web page that aren’t set out in a neat grid; perhaps they are markers on a map:

In the spirit of good accessibility, you want users to be able to navigate between them with the four arrow keys, not just the mouse. Is there a way, given a currently selected point and a direction, to find a sensible new point to move to?

The Problem of
Distance vs. Direction

The first issue we run into is what we even mean by, “sensible”. A good starting approach would be to search for all points in a 90° arc of the currently selected point, and to pick the closest one.

In this example, the user has selected to go right. Of the four other points, only B and C fall within the cone of vision. B is closer in terms of absolute distance, so that is chosen as the nearest rightward neighbour.

There is something that doesn’t feel quite right about this.

• C should be prioritised over B: it is clearly more in the intended direction, despite only being a little further away.
• Both A and D are to the right of the current point and are by far the closest, yet are completely ignored as candidates.

I propose a better solution:

By changing the shape of the search area from a cone to a circle, it creates a much better balance between distance and direction. By this new metric, B is now the furthest away. While C is still closer than A, D is now the closest rightward neighbour.

The idea of measuring how far two points are from one another in this manner, I will refer to as their circle distance. Given a set of points, one of which is selected, and a direction, we want to find which other point has the shortest circle distance in that direction.

Calculating Circle Distance

In the following example, we want to find the circle distance from the red point to the blue point, given that the user has selected to go right.

We currently know their horizontal distance, u; and their vertical distance, v. We want to find r, the radius of the circle.

From the diagram, using the Pythagoream theorem, we can see that:

$$(u - r)^2 + v^2 = r^2$$

Rearranging gives $r$ in terms of $u$ and $v$.

$$u^2 - 2ur + r^2 + v^2 = r^2$$ $$u^2 + v^2 = 2ur$$ $$\frac{u^2 + v^2}{2u} = r$$

This generalises for all directions; u is the distance parallel to the direction of travel and v is the perpendicular distance. Turning the above into code:

/**
 * @param {number} u - The parallel distance
 * @param {number} v - The perpendicular distance
 */
function circleDistance(u, v) {
  return u > 0 ? (u * u + v * v) / (2 * u) : Infinity;
}

I also added in a check for when $u$ is negative, which represents a point that is in entirely the wrong direction. In these cases, we can treat it as if it were infinitely far away.

Applying the Circle Distance to Pairs of Points

I then extended this function so that it could take a current point, a target point, and the target direction as an angle in radians. From there, it can derive $u$ and $v$.

function circleDistance(p1, p2, theta) {
  // get the x and y distance between p1 and p2
  const x = p2.x - p1.x;
  const y = p2.y - p1.y;

  // treating [x, y] as a vector, rotate it by negative theta degrees
  // see: https://en.wikipedia.org/wiki/Rotation_matrix
  const x2 = x * Math.cos(theta) - y * Math.sin(theta);
  const y2 = x * Math.sin(theta) + y * Math.cos(theta);

  // this aligns `u` with the horizontal axis and `v` with the vertical
  const u = x2;
  const v = y2;

  // same formula as before
  return u > 0 ? (u * u + v * v) / (2 * u) : Infinity;
}

From here, there’s a tiny bit of tidying up we can do:

Firstly, we can get rid of x1 and x2, and replace them with u and v.

Secondly, one key observation is that $u^2 + v^2 = x^2 + y^2$. This relates to the fact that rotating a vector does not change its length. This lets us replace that portion of code, which in turn means that we can get rid of v entirely.

function circleDistance(p1, p2, theta) {
  const x = p2.x - p1.x;
  const y = p2.y - p1.y;
  
  const u = x * Math.cos(theta) - y * Math.sin(theta);
  return u > 0 ? (x * x + y * y) / (2 * u) : Infinity;
}

Conclusion

Putting everything into practice, here is how you’d use this function:

const points = document.querySelectorAll('.point');
let currentPoint = 0; // index of the currently selected point

points.forEach(point => {
  point.addEventListener('keydown', selectNextPoint)
});

function getAngleForDirection(direction) {
  const quarterTurn = return Math.PI / 2;
  return quarterTurn * (
    direction === 'ArrowRight' ? 0 :
    direction === 'ArrowUp' ? 1 :
    direction === 'ArrowLeft' ? 2 :
    direction === 'ArrowDown' ? 3 : NaN
  );
}

function selectNextPoint(e) {
  // get the direction from the key pressed
  const theta = getAngleForDirection(e.key);
  // don't do anything if not a valid direction
  if (isNaN(theta)) return;

  let closestPoint = -1;
  let minDistance = Infinity;

  for (let i = 0; i < points.length; i++) {
    // don't compare current point with itself
    if (i === currentPoint) continue;
    const distance = circleDistance(points[currentPoint], points[i], theta);
    if (distance < minDistance) {
      minDistance = distange;
      closestPoint = i;
    }
  }

  if (closestPoint >= 0) {
    currentPoint = closestPoint;
    // exercise for the reader: handle this change in your UI
  }
}

Demo

Using this function I put together a simple demo to show it in action.

The dots below have been generated at random. Click into the region and use the arrow keys to navigate between them.