CODEWITHSUNDEEP
algorithmsortingbounds
algro
algro

Reputation: 637

Algorithm: How to find closest element, having coordinates and dimension

I got an Array with objects, each object contains x,y,width and height. e.g. arr[{10,20,200,300},{20,30,100,200},…] Now I would like to find the closest object in this array to a given object, taking its boundaries into account. How could I achieve that, having for example an x-precedence to the right(finding the closest object on the x-axis situated right from the given object)?

Upvotes: 1

Views: 239

Answers (1)

Yigitalp Ertem
Yigitalp Ertem

Reputation: 2049

Let's say your object's center is (x,y) with width w, height h.

The objects (rectangles, I suppose) in the array has center (xi, yi) and width wi, hi.

Your object will connect to the others either from right-edge, top-edge or bottom-edge whose coordinates are:

R1 - R2: ((x+(w/2)), (y-(h/2))) - ((x+(w/2))), ((y+(h/2)))

T1 - T2: ((x-(w/2)), (y+(h/2))) - ((x+(w/2))), ((y+(h/2)))

B1 - B2: ((x-(w/2)), (y-(h/2))) - ((x+(w/2))), ((y-(h/2)))

Objects in array may have shortest distance starting from their left-edge, top-edge or bottom-edges which are similar

Li1 - Li2: ((xi-(wi/2)), (yi-(hi/2))) - ((xi-(wi/2))), ((yi+(hi/2)))

Ti1 - Ti2: ((xi-(wi/2)), (yi+(hi/2))) - ((xi+(wi/2))), ((yi+(hi/2)))

Bi1 - Bi2: ((xi-(wi/2)), (yi-(hi/2))) - ((xi+(wi/2))), ((yi-(hi/2)))

Then,

distance = infinite;
shortest = null;
for all object in array
    find min distance for
        R2 to [Li1,Li2] line
        R1 to [Li1,Li2] line
        R2 to [Bi1,Bi2] line
        R1 to [Bi1,Bi2] line
        R2 to [Ti1,Ti2] line
        R1 to [Ti1,Ti2] line

        T2 to [Li1,Li2] line
        T1 to [Li1,Li2] line
        T2 to [Bi1,Bi2] line
        T1 to [Bi1,Bi2] line
        T2 to [Ti1,Ti2] line
        T1 to [Ti1,Ti2] line

        B2 to [Li1,Li2] line
        B1 to [Li1,Li2] line
        B2 to [Bi1,Bi2] line
        B1 to [Bi1,Bi2] line
        B2 to [Ti1,Ti2] line
        B1 to [Ti1,Ti2] line

    if minDistance < distance
        distance = minDistance
        shortest = i
end for

You can skip some of these calculations according to the relative position of the objects in the array to your object. For example, if Ti1 < B1, you don't need to calculate [Bi1,Bi2] line parts.

I feel that this solution is very straight-forward&dummy and will take rough criticisms from the mathematicians, but I wanted to try to see the receptions.

Upvotes: 1

Related Questions