Алгоритм: Как найти ближайший элемент, имеющий координаты и размеры

У меня есть массив с объектами, каждый объект содержит x, y, ширину и высоту. например arr[{10,20,200,300},{20,30,100,200},…] Теперь я хотел бы найти ближайший объект в этом массиве к заданному объекту с учетом его границ. Как я мог добиться этого, имея, например, х-приоритет справа (нахождение ближайшего объекта по оси х, расположенного прямо от данного объекта)?


sorting algorithm bounds
person algro    schedule 22.11.2014    source источник
comment
Вам нужно будет определить метрику и как учитывать частичное перекрытие (пересечение границ) и ограждение. Начните с грубой силы. Если затраченное время действительно беспокоит вас, взгляните на развертку строки. .   -  person greybeard    schedule 23.11.2014

Ответы (1)


arrow_upward
1
arrow_downward

Допустим, центр вашего объекта (x,y), ширина w, высота h.

Объекты (я полагаю, прямоугольники) в массиве имеют центр (xi, yi) и ширину wi, hi.

Ваш объект будет соединяться с другими либо с правого края, либо с верхнего края, либо с нижнего края, чьи координаты:

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

Объекты в массиве могут иметь кратчайшее расстояние, начиная с их левого края, верхнего края или нижнего края, которые аналогичны

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

Затем,

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

Вы можете пропустить некоторые из этих вычислений в соответствии с относительным положением объектов в массиве по отношению к вашему объекту. Например, если Ti1 < B1, вам не нужно вычислять [Bi1,Bi2] line частей.

Я чувствую, что это решение очень простое и фиктивное и выдержит грубую критику со стороны математиков, но я хотел попытаться увидеть приемы.

person Yigitalp Ertem    schedule 22.11.2014
comment
Принимая ваше последнее предложение за чистую монету: это объясняет ограждение? - person greybeard; 23.11.2014
comment
Думаю, нет. Я думал, что в этом нет необходимости, поскольку OP заявил, что находит ближайший объект по оси x, расположенный прямо от данного объекта, но я не уверен. - person Yigitalp Ertem; 23.11.2014
comment
Спасибо за ответ, знаете ли вы какую-либо библиотеку/реализацию javascript? Я думаю, было бы также интересно, как это можно было бы реализовать, находя ближайших, расширяя границы. Ограждения/перекрытия не нужны для начала, но их желательно иметь в будущем. - person algro; 23.11.2014