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!

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;
}

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;
            }
       });
}

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.