Найдите прямоугольник наименьшей площади, охватывающий точку запроса

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

Чтобы избежать наихудшего случая O (n) для поиска прямоугольника, вы можете использовать своего рода троичное пространственное дерево, в котором вы неоднократно проводите вертикальную линию через пространство и делите прямоугольники на три группы: те, что слева (синие ), те, которые пересекаются (красный), и те, которые находятся справа (зеленый) от линии. Для группы пересекающихся прямоугольников (или после того, как вертикальная линия пересечет большую часть или все прямоугольники), вы переключаетесь на горизонтальную линию и делите прямоугольники на группы выше, пересекаются и ниже линии.

Затем вы должны неоднократно проверять, находится ли точка слева / справа или выше / ниже линии, и переходите к проверке прямоугольников с той же стороны и прямоугольников, пересекаемых линией.

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

Если мы используем следующую нумерацию прямоугольников в примере:

тогда троичное пространственное дерево будет примерно таким:

Вы можете разделить область от xMin до xMax и от yMin до yMax по краям прямоугольников. Это дает не более (2n - 1) ^ 2 полей. Каждое из полей либо полностью пусто, либо занято видимым (частью) одиночным прямоугольником. Теперь вы можете легко создать древовидную структуру со ссылками на верхний прямоугольник (например, подсчитать количество разделов в направлении x и y, где больше разделений посередине и создать узел ... действовать рекурсивно). Таким образом, поиск займет O (log n ^ 2), что является сублинейным. И структура данных занимает пространство O (n ^ 2).

Это лучшая реализация с точки зрения сложности, потому что поиск индексов может быть разделен, поиск прямоугольника вверху составляет только O (log n), независимо от конфигурации прямоугольников и довольно просто реализовать :

private int[] x, y;
private Rectangle[][] r;

public RectangleFinder(Rectangle[] rectangles) {
    Set<Integer> xPartition = new HashSet<>(), yPartition = new HashSet<>();
    for (int i = 0; i < rectangles.length; i++) {
        xPartition.add(rectangles[i].getX());
        yPartition.add(rectangles[i].getY());
        xPartition.add(rectangles[i].getX() + rectangles[i].getWidth());
        yPartition.add(rectangles[i].getY() + rectangles[i].getHeight());
    }
    x = new int[xPartition.size()];
    y = new int[yPartition.size()];
    r = new Rectangle[x.length][y.length];
    int c = 0;
    for (Iterator<Integer> itr = xPartition.iterator(); itr.hasNext();)
        x[c++] = itr.next();
    c = 0;
    for (Iterator<Integer> itr = yPartition.iterator(); itr.hasNext();)
        y[c++] = itr.next();
    Arrays.sort(x);
    Arrays.sort(y);
    for (int i = 0; i < x.length; i++)
        for (int j = 0; j < y.length; j++)
            r[i][j] = rectangleOnTop(x[i], y[j]);
}

public Rectangle find(int x, int y) {
    return r[getIndex(x, this.x, 0, this.x.length)][getIndex(y, this.y, 0, this.y.length)];
}

private int getIndex(int n, int[] arr, int start, int len) {
    if (len <= 1)
        return start;
    int mid = start + len / 2;
    if (n < arr[mid])
        return getIndex(n, arr, start, len / 2);
    else
        return getIndex(n, arr, mid, len - len / 2);
}

Практически любой индекс может ухудшиться до наихудшего O (n).

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

Рассмотрим n перекрывающихся прямоугольников одинакового размера и точку на пересечении ... здесь у вас не будет много шансов на оптимизацию.

R-дерево - неплохой выбор. Вы можете выполнить приоритетный поиск и предпочитать меньшие прямоугольники.

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

Как насчет PH-дерева? PH-Tree - это, по сути, квадродерево в форме квадродерева, но с некоторыми уникальными свойствами, которые могут быть идеальными для вашего случая, такими как очень эффективные обновления и высокая вероятность локализации небольших прямоугольников.

Основы:

• PH-Tree - это попытка битового уровня, что означает, что оно разбивается по всем измерениям в каждой битовой позиции. Это означает, что для 64-битных данных с плавающей запятой максимальная глубина дерева равна 64.
• Дерево неявно упорядочено по оси Z
• Скорость запроса обычно сравнима с R * Tree или STR-Tree, в вашем случае это может быть значительно быстрее, см. Ниже.
• Скорость вставки / удаления равна или лучше, чем у STR-деревьев, и лучше, чем у любого другого типа R-Tree, о котором я знаю.
• Форма дерева определяется только данными, а не порядком вставки. Это означает, что никакой дорогостоящей перебалансировки никогда не будет. Фактически, дерево гарантирует, что любая вставка или удаление никогда не затронет более двух узлов (с отношениями дочерний / родительский).

Сохранение прямоугольников: PH-Tree может хранить только векторы данных, т.е. точки. Чтобы хранить (выровненные по оси) прямоугольники, по умолчанию он принимает «нижний левый» и «верхний правый» углы, но они находятся в одном векторе. Например, двухмерный прямоугольник (2,2) - (4,5) сохраняется как четырехмерный вектор (2,2,4,5). Это может быть неочевидно, но это представление по-прежнему позволяет выполнять эффективные запросы, такие как запросы окна и запросы ближайшего соседа, увидеть некоторые результаты здесь и еще несколько объяснений здесь.

Дерево не может напрямую хранить один и тот же прямоугольник дважды. Вместо этого вы бы связали счетчик с каждым «ключом». Для особого случая с n идентичными прямоугольниками это фактически имеет то преимущество, что результирующее дерево будет содержать только один ключ, поэтому перекрытие с наименьшим прямоугольником может быть определено почти за постоянное время.

Производительность запроса: как видно из результатов производительности, PH-Tree (в зависимости от набора данных) является самым быстрым с небольшими окнами запросов, которые возвращают мало результатов (здесь, рисунок 16). Я не уверен, связано ли повышение производительности с небольшим размером окна запроса или небольшим размером результата. Но если он подключен к первому, тогда ваши запросы должны быть очень быстрыми, потому что, по сути, ваше окно запроса - это точка.

Оптимизация для небольшого размера прямоугольника: из-за кодирования прямоугольников в один вектор наименьший прямоугольник, скорее всего (гарантированно ??), будет находиться в том же листовом узле, который также будет содержать вашу точку поиска. Обычно запросы обрабатываются в z-порядке, поэтому, чтобы использовать локальность маленьких прямоугольников, вам нужно написать специальный запрос. Это не должно быть сложно, я думаю, я мог бы просто использовать реализацию k-ближайшего соседа PH-Tree и предоставить настраиваемую функцию расстояния. Текущая kNN начинается с определения местоположения узла с точкой поиска, а затем расширяет область поиска до тех пор, пока не будут найдены все ближайшие соседи. Я действительно считаю, что использования настраиваемой функции расстояния должно быть достаточно, но вам, возможно, придется провести некоторое исследование, чтобы доказать это.

Полный код (Java) PH-Tree доступен по ссылке выше. Для сравнения вы можете посмотреть мои другие реализации индекса здесь (R * Tree, quadtrees , STR-дерево).