Finding element nearest to clicked point

Question

Need some help here. I'm a UI designer who isn't good at numbers doing an experimental web form design and I need to know which input element is closest to a clicked point on a web page. I know how to do nearest neighbor with points but the input elements are rectangles not points so I'm stuck.

I'm using jQuery. I just need help with this little algo. Once I'm done with my experiment I'll show you guys what I'm doing.

UPDATE

I thought about how it can work. Look at this diagram:

Each rectangle has 8 points (or rather 4 points and 4 lines) which are significant. Only the x value is significant for horizontal points (red dot) and only the y value is significant for vertical points (green dot). Both x and y are significant for the corners.

Orange crosses are the points to be measured against – mouse clicks in my use case. The light purple lines are the distances between the orange cross and it's possible nearest point.

So… for any given orange cross, loop through each of the 8 points n every rectangle to find the nearest edge or corner closest of each rectangle to the orange cross. The rectangle with the lowest value is the nearest one.

I can conceptualize and visualize it but can't put it into code. Help!

Iodine

Use the 4 points that represent a rectangle in your nearest neighbor algorithm. Or use the center point of the rectangle cx = (left + width)/2, cy = (top + height)/2. – Perce

any chance you could post some code or do something in jsfiddle.net? it's all a bit hypothetical otherwise... – Enchantment

Added an illustration to explain the problem and how it might be solved. – Iodine

Answer 1

Your algorithm is correct. Since you need help in code, and not in the algorithm, here's the code:

It may not be the most efficient. But it works.

// Define the click
var click = Array(-1, -2); // coodinates in x,y

// Define the buttons
// Assuming buttons do not overlap
var button0 = Array(
    Array(0, 0), // bottom-left point (assuming x is horizontal and y is vertical)
    Array(6, 6) // upper-right point
);

var button1 = Array(
    Array(10, 11),
    Array(17, 15)
);

var button2 = Array(
    Array(-8, -5),
    Array(-3, -1)
);

// Which button to trigger for a click
i = which(click, Array(button0, button1, button2));
alert(i);


function which(click, buttons){
    // Check if click is inside any of the buttons
    for (i in buttons){
        var button = buttons[i];
        var bl = button[0];
        var tr = button[1];

        if ( (click[0] >= bl[0] && click[0] <= tr[0]) &&
             (click[1] >= bl[1] && click[1] <= tr[1]) ){
            return i;
        }
    }

    // Now calculate distances
    var distances = Array();

    for (i in buttons){
        var button = buttons[i];
        var bl = button[0];
        var tr = button[1];

        if ( (click[0] >= bl[0] && click[0] <= tr[0])) {
            distances[i] = Math.min( Math.abs(click[1]-bl[1]), Math.abs(click[1]-tr[1]) );
        }
        else if ( (click[1] >= bl[1] && click[1] <= tr[1])) {
            distances[i] = Math.min( Math.abs(click[0]-bl[0]), Math.abs(click[0]-tr[0]) );
        }
        else{
            distances[i] =  Math.sqrt(
                                (Math.pow(Math.min( Math.abs(click[0]-bl[0]), Math.abs(click[0]-tr[0]) ), 2)) +
                                (Math.pow(Math.min( Math.abs(click[1]-bl[1]), Math.abs(click[1]-tr[1]) ), 2))
                            );
        }
    }

    var min_id = 0;
    for (j in distances){
        if (distances[j] < distances[min_id]){
            min_id = j;
        }
    }

    return min_id;
}

Beekeeping

Great. Just what I need. How would I make the code adaptable to any width and height? – Iodine

It is adaptable to any width and height. You'll just have to define the dimensions of the buttons and the click's coordinate on the top part of the JavaScript. – Beekeeping

Answer 2

The addition of the relatively new elementFromPoint() API lets us take an alternative, potentially lighter approach: we can hit test around the mouse cursor, going in larger circles until we find the nearest element.

I put together a quick, non-production example here: http://jsfiddle.net/yRhhs/ (Chrome/Safari only due to use of webkitMatchesSelector). The performance can get laggy due to the dots used in visualizing the algorithm.

The core of the code, outside of the light performance optimizations and event bindings, is this bit:

function hitTest(x, y){
    var element, i = 0;
    while (!element){
        i = i + 7; // Or some other threshold.

        if (i > 250){ // We do want some safety belts on our while loop.
            break;
        }

        var increment = i/Math.sqrt(2);
        var points = [
            [x-increment, y-increment], [x+increment, y-increment],
            [x+increment, y+increment], [x-increment, y+increment]
        ];

        // Pop additional points onto the stack as the value of i gets larger.
        // ...

        // Perhaps prematurely optimized: we're using Array.prototype.some to bail-out
        // early once we've found a valid hit target.
        points.some(function(coordinates){
            var hit = document.elementFromPoint.apply(document, coordinates); 
            // isValidHit() could simply be a method that sees whether the current
            // element matches the kinds of elements we'd like to see.
            if (isValidHit(hit)){
                element = hit;
                return true;
            }
       });
}

Cummerbund

Answer 3

You could look for the nearest corner point of all rectangles. This works in the most cases, is fast and easy to implement. As long as your rectangles are aligned on a regular grid this method gives you the nearest rectangle.

Rundlet

Answer 4

The way I'd do it is not with numbers, but with logic.

I'm assuming that you want to end up with something that says, "if x is the nearest element then do something when I clicked elsewhere then do something to x"

You could do this if each of the elements you want to do something with were in simple <div> containers that were larger than the element you want to treat, but no larger than halfway between the object it contains and it's next nearest object. A grid in fact.

give all the containers the same class.

Then you could say, "if y is clicked go do something to x", you would already know which element is in each container.

I'd write the code but I'm leaving work...

Enchantment

Answer 5

If you want to find the distance between two points on a 2D grid, you can use the following formula:

(for 2D points A & B)

distanceX = A.x - B.x

distanceY = A.y - B.y

totalDistance = squareRoot ((distX * distX) + (distY * distY))

Once you can check the distance between two points you can pretty easily figure out which rectangle corner your mouse click is closest too. There are numerous things you can do to optimise your intended algorithm, but this should give you a good start.

Ambur

Answer 6

lol, the question is why are you thinking of shapes? your question really is "if i click a coordinate, find me the nearest node/point to my click" which is a matter of going through the various nodes and calculating distances.

If same X, use y difference

If same y, use x difference

otherwise use hypotheneuse

Once you find the nearest point you can get the parent shape right? This will work because you're trying to snap to nearest point. So it'll even work with fancy shapes like stars.

Whomever

Answer 7

I wanted to allow users to add content between paragraphs. So for my use case I only cared about nearby paragraph tags above or below a click.

As such, I used this code:

const MAX_TRIES_PER_DIR = 10;
const PX_SHIFT_EACH_TRY = 2;

function findClosestPToClick(e) {
  const above_res = checkNearbyPosForP(e.pageX, e.pageY, -PX_SHIFT_EACH_TRY, MAX_TRIES_PER_DIR);
  const above_dist = above_res ? Math.abs(e.pageY - above_res.y) : Infinity;
  const below_res = checkNearbyPosForP(e.pageX, e.pageY, PX_SHIFT_EACH_TRY, MAX_TRIES_PER_DIR);
  const below_dist = below_res ? Math.abs(e.pageY - below_res.y) : Infinity;
  
  if (above_dist <= below_dist) {
    if (above_dist === 0) {
      const el_height = above_res.el.offsetHeight;
      if (Math.sign(e.offsetY - el_height / 2) < 0) {
        return {
          el: above_res?.el,
          place_before: true,
        }
      }
      return {
        el: above_res?.el,
        place_before: false,
      }
    }
    return {
      el: above_res?.el,
      place_before: false,
    }
  } 
  return {
    el: above_res?.el,
    place_before: true,
  };
}

function checkNearbyPosForP(x, y, shift, num_tries) {
  const p = document.elementFromPoint(x, y)?.closest('p');
  if (p) return { el: p, y };
  if (num_tries > 1) {
    return checkNearbyPosForP(x, y + shift, shift, --num_tries);
  }
  return;
}

document.addEventListener('click', function(e) {
  const res = findClosestPToClick(e);
  if (res.el) {
    return console.log(res.el.innerText, res.place_before);
  }
  console.log('No p found near click');
});

Demo

Beecham