Ближайший край к прямоугольнику в плоскости прямоугольников

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

array[N,4] # N rectangles, with X coordinate, Y coordinate, width and heigth
distance = inf # Initialize distance with high value    
i = chosenRectangle
closest = 0 # Initialize index of closest rectangle

# Vertical colliding
for j=1,N
    if (i/=j) and (array[j,1] > array[i,1] - array[j,3]) and (array[j,1] < array[i,1] + array[i,3]) then
        evaluate distanceTemp # Distance between rectangles i and j
        if distanceTemp < distance then
            distance = distanceTemp 
            closest = j
        end if
    end if
end for

# Same for horizontal colliding, without reinitialization

Кажется, задач много.

• Во-первых, игнорируйте тот факт, что это находится в 2D-плоскости.
• Представьте, у нас есть линия с несколькими точками на ней.
• Решите задачу «пересечение» прямой. Назовем это x_axis.
• Повторите то же решение для второй оси y.
• Мы хотим найти «пересечения» каждых двух линий с общим пересечением.

• Предположим, вы выбрали для сравнения один «исходный» прямоугольник.
• Давайте сейчас добавим все остальные прямоугольники во вторую группу.
• Обратите внимание: порядок не имеет значения. Кроме того, это алгоритм выше O(N^2), поэтому мы всегда сортируем, как прямоугольники, так и пересечения.

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

import random


def get_intersections(A, B):
    get_sorted_by_element(A, 1)
    get_sorted_by_element(A, 0)
    get_sorted_by_element(B, 1)
    get_sorted_by_element(B, 0)
    res = []
    a, b = 0, 0
    if A and B:
        while a < len(A) and b < len(B):
            lo = max(A[a][0], B[b][0])
            hi = min(A[a][1], B[b][1])
            if lo <= hi:
                res.append((lo, hi))

            if A[a][1] < B[b][1]:
                a += 1
            else:
                b += 1
    return res


def get_random_rects(n):
    random.seed(1)
    rects = []
    for i in range(n):
        a = c = random.randint(31, 60)
        b = random.randint(70, 90)
        d = random.randint(70, 110)
        rects.append((a, b, c, d))
    return rects


def get_sorted_by_element(A, i):
    return sorted(A, key=lambda x: x[i])


rects_a = get_random_rects(1)
rects_b = get_random_rects(20)
x_axis = get_intersections([(a, b) for a, b, _, _ in rects_a],
                           [(a, b) for a, b, _, _ in rects_b])
y_axis = get_intersections([(c, d) for _, _, c, d in rects_a],
                           [(c, d) for _, _, c, d in rects_b])


print(f"rectangle to compare: {rects_a}")
print(f"other rectangles: {rects_b}")
print(f"x_axis intersections: {x_axis}")
print(f"y_axis intersections: {y_axis}")

x_axis = get_sorted_by_element(x_axis, 0)
y_axis = get_sorted_by_element(y_axis, 1)
print(f"sorted x_axis intersections: {x_axis}")
print(f"sorted y_axis intersections: {y_axis}")

print(x_axis, y_axis)

Принты

прямоугольник для сравнения: [(35, 88, 35, 74)] другие прямоугольники: [(35, 88, 35, 74), (39, 73, 39, 101), (55, 84, 55, 100), (51, 82, 51, 83), (34, 85, 34, 71), (59, 82, 59, 97), (50, 70, 50, 98), (39, 77, 39, 107), (34, 80, 34, 71), (31, 70, 31, 104), (31, 82, 31, 83), (44, 70, 44, 103), (38, 84, 38, 101), (48, 77, 48, 92), (38, 77, 38, 99), (40, 70, 40, 96), (57, 87, 57, 76), (36, 90, 36, 88), (34, 80, 34, 102), (60, 83, 60, 102)] пересечения оси x: [(35, 88), (39, 73), (55, 84), (51, 82), (35, 85), (59, 82), (50, 70), (39, 77), (35, 80), (35, 70), (35, 82), (44, 70), (38, 84), (48, 77), (38, 77), (40, 70), (57, 87), (36, 88)] пересечения оси y: [(35, 74), (39, 74)] отсортированы по оси x пересечения: [(35, 88), (35, 85), (35, 80), (35, 70), (35, 82), (36, 88), (38, 84), (38, 77), (39, 73), (39, 77), (40, 70), (44, 70), (48, 77), (50, 70), (51, 82), (55, 84), (57, 87), (59, 82)] отсортировано по оси y пересечения: [(35, 74), (39, 74)] [(35, 88), (35, 85), (35, 80), (35, 70), (35, 82), (36, 88), (38, 84), (38, 77), (39, 73), (39, 77), (40, 70), (44, 70), (48, 77), (50, 70), (51, 82), (55, 84), (57, 87), (59, 82)] [(35, 74), (39, 74)]

• Обычно мы определяем прямоугольник с двумя точками: верхней правой и нижней левой точками.

• Здесь я использовал три пункта:

Примечание

• На первый взгляд эта проблема может показаться простой, но, на мой взгляд, это сложный вопрос.

• По сути, мы здесь делаем зеркальное отображение прямоугольников по осям x и y.

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

• Затем у нас есть третий или главный прямоугольник для сравнения с любым из этих двух прямоугольников. Здесь мы сравниваем оси Y и X и видим, что наш основной прямоугольник ближе к расстоянию X или Y.

Примечание

• Дерево сегментов используется для суммы диапазона:

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        self.build(nums)

    def build(self, nums):
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
        print(self.tree)

    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx > 1:
            idx //= 2
            self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]

    def query(self, l, r):
        l += self.n
        r += self.n
        sums = 0
        while l <= r:
            if l % 2 == 1:
                sums += self.tree[l]
                l += 1
            if r % 2 == 0:
                sums += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return sums


nums = [1, 3, 5, 7, 9, 11]
segment_tree = SegmentTree(nums)
queries = [(0, 2), (1, 4), (2, 5)]
for query in queries:
    left, right = query
    result = segment_tree.query(left, right)
    print(result)

Принты

[0, 36, 32, 4, 12, 20, 1, 3, 5, 7, 9, 11]

9

24

32

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

Из дерева отрезков

Аналогично проверить бинарный поиск?

Сортировка

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

• Поэтому, если вы отсортируете, нам не придется проверять каждый прямоугольник. Нам нужно проверить только «ближние» прямоугольники, если хотите. Эти прямоугольники, находящиеся рядом друг с другом, могут иметь только «пересечения».