В 2D, как мне эффективно найти ближайший объект к точке?

У меня большой игровой движок, и мне нужна функция для нахождения ближайшего списка пунктов.

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

У меня также есть система столкновений, где я, по сути, превращаю объекты в меньшие объекты в меньшей сетке (вроде мини-карты), и только если объекты существуют в одном и том же сетке, я проверяю наличие столкновений. Я мог бы сделать это, только увеличив расстояние между сетками, чтобы проверить на близость. (Вместо того, чтобы проверять каждый отдельный объект.) Однако это потребовало бы дополнительных настроек в моем базовом классе и засорение уже загроможденного объекта. Стоит ли оно того?

Есть ли что-то эффективное и точное, что я мог бы использовать, чтобы определить, какой объект ближе всего, основываясь на списке точек и размеров?

Проблема с quad / octree в поисках ближайших соседей заключается в том, что ближайший объект может находиться прямо через деление между узлами. Для коллизий это нормально, потому что если его нет в узле, нас это не волнует. Но рассмотрим этот 2D-пример с квадродеревом:

Здесь, даже если черный элемент и зеленый элемент находятся в одном узле, черный элемент находится ближе всего к синему элементу. Ответ ultifinitus может гарантировать только то, что ближайший сосед - только каждый элемент в вашем дереве размещен в наименьшем возможном узле, который может его содержать, или в уникальном узле - это приводит к более неэффективным квадродеревам. (Обратите внимание, что существует много разных способов реализации структуры, которую можно назвать quad / octree - более строгие реализации могут работать лучше в этом приложении.)

Лучшим вариантом будет kd-дерево . Kd-деревья имеют очень эффективный алгоритм поиска ближайших соседей , который вы можете реализовать, и могут содержать любое количество измерений (отсюда и «k» измерения).

Отличная и информативная анимация из Википедии:

Самая большая проблема с использованием kd-деревьев, если я правильно помню, заключается в том, что с ними сложнее вставлять / удалять элементы при сохранении баланса. Поэтому я бы рекомендовал использовать одно kd-дерево для статических объектов, таких как дома и деревья, которое хорошо сбалансировано, и другое, которое содержит игроков и транспортные средства, которые требуют регулярной балансировки. Найдите ближайший статический объект и ближайший мобильный объект и сравните эти два.

Наконец, kd-деревья относительно просты в реализации, и я уверен, что вы можете найти множество библиотек C ++ с ними. Из того, что я помню, R-деревья намного сложнее и, вероятно, излишни, если все, что вам нужно, это простой поиск ближайших соседей.

sqrt() является монотонным, или сохраняющим порядок, для неотрицательных аргументов так:

sqrt(x) < sqrt(y) iff x < y

Наоборот.

Поэтому, если вы хотите сравнить только два расстояния, но не интересуетесь их фактическими значениями, вы можете просто вырезать sqrt()-step из вашего Pythagoras-материала:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)²
pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)²
if (pseudoDistanceB < pseudoDistanceC)
{
    A is closest to B!
}
else
{
    A is closest to C!
}

Он не так эффективен, как объект oct-tree, но его легче реализовать и он увеличивает скорость, по крайней мере, немного

Вы должны сделать пространственное разделение, в этом случае вы создаете эффективную структуру данных (обычно октре). В этом случае каждый объект находится внутри одного или нескольких пробелов (кубов). И если вы знаете, в каких пробелах вы находитесь, вы можете посмотреть O (1), какие пробелы являются вашими соседями.

В этом случае ближайший объект может быть найден путем первой итерации по всем объектам в вашем собственном пространстве с поиском того, какой из них находится ближе всего. Если там никого нет, вы можете проверить своих первых соседей, если там никого нет, вы можете проверить их соседей и т.д ...

Таким образом, вы можете легко найти ближайший объект без необходимости перебирать все объекты в вашем мире. Как обычно, это увеличение скорости требует небольшого учета, но это действительно полезно для всех видов вещей, поэтому, если у вас большой мир, определенно стоит реализовать пространственное разделение и октри.

Как обычно, см. Также статью в Википедии: http://en.wikipedia.org/wiki/Octree

Может быть, попробуйте организовать ваши пространственные данные в RTree, который похож на btree для вещей в пространстве и позволяет выполнять запросы типа «ближайших N соседей» и т. Д. Http://en.wikipedia.org/wiki/Rtree

Вот моя реализация Java, чтобы получить самую близкую от quadTree. Это касается проблемы, которую описывает dlras2:

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

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

public T getClosest(float x, float y) {

    Closest closest = new Closest();
    getClosest(x, y, closest);

    return closest.item;
}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

protected void getClosest(float x, float y, Closest closestInfo) {


    if (hasQuads) {

        // we have no starting point yet
        // so get one
        if (closestInfo.item == null) {
            // check all 4 cause there could be a empty one
            for (int i = 0; i < 4; i++) {
                quads[i].getClosest(x, y, closestInfo);
                if (closestInfo.item != null) {
                    // now we have a starting point
                    getClosest(x, y, closestInfo);
                    return;
                }

            }
        }
        else {

            // we have a item set as closest
            // we should check if this quad is
            // closer then the current closest distance
            // let's start with the closest from index

            int closestIndex = getIndex(x, y);

            float d = quads[closestIndex].bounds.distToPointSQ(x, y);

            if (d < closestInfo.dist) {
                quads[closestIndex].getClosest(x, y, closestInfo);
            }

            // check the others
            for (int i = 0; i < 4; i++) {
                if (i == closestIndex) continue;

                d = quads[i].bounds.distToPointSQ(x, y);

                if (d < closestInfo.dist) {
                    quads[i].getClosest(x, y, closestInfo);
                }

            }

        }

    }
    else {

        for (int i = 0; i < items.size(); i++) {

            T item = items.get(i);

            float dist = distSQ(x, y, getXY.x(item), getXY.y(item));

            if (dist < closestInfo.dist) {
                closestInfo.dist = dist;
                closestInfo.item = item;
                closestInfo.tree = this;
            }

        }
    }

}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


class Closest {

    QuadTree<T> tree;
    T item;
    float dist = Float.MAX_VALUE;

}