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.

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...

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.

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.