Учитывая ряд различной ширины и точку, найдите ширину, содержащую точку

Question

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

Мне нужен быстрый путь чтобы найти прямоугольник, точка находится в заданной координате X. Для изображения выше, две красные точки вернут черный и желтый прямоугольники соответственно. Исходное решение У меня были пряжки под очень большим количеством прямоугольников:

    Rect getRectFor(float x) {
        float totalSum = 0.0f;

        // For each rect (in order)
        for (Rect rect : rects) {
            // Add the rect's width
            totalSum += rect.getWidth();

            // If the end of the rect is beyond us, return
            if (totalSum >= x) {
                return rect;
            }
        }

        // We are beyond the end of all rects
        return null;
    }

Существуют ли какие-либо методы или структуры данных, которые будут работать лучше в этом сценарии и позволят мне выполнять тысячи поисков в секунду?

Answer 1

Самый быстрый способ, который я могу придумать, это создать массив:

E[0] = 0
E[i] = x-coordinate indicating where the i-th ends.

В вашем примере это будет E = {0, 100, 150, 225, 350, 375, ...}.

Чтобы найти положение любой точки, вы можете просто выполнить бинарный поиск в этом массиве, давая вам время O (lg (n)) на запрос.

---

Просто, чтобы помочь, добавил небольшой кусочек кода:

int bs(int[] m, int l, int r, int dot){
    int i = (l + r) / 2;
    if(m[i - 1] < dot && dot < m[i]) return i;
    if(m[i - 1] == dot) return max(1, i - 1);
    if(m[i] == dot) return i;

    if(dot < m[i]) return bs(m, l, i, dot);
    else return bs(m, i + 1, r, dot);        
}

Аргументы bs:

• m: ваш массив.
• l: вы всегда должны использовать 1.
• r: вы всегда должны использовать n - 1, где n - длина m.
• dot: координата x вашей точки.

Пример: если вы хотите найти позицию вашей второй точки (в позиции x = 230), вам следует позвонить

bs(E, 1, E.length - 1, 230)

, и она вернет 4.

Если вы попытаетесь запустить этот метод с x-координатой, которая выходит за границы массива (например, если последний прямоугольник заканчивается в позиции x = 100, и вы ищете точку в x = 101 ), могут случиться странные вещи.