algorithm geometry computational-geometry

Closest edge to a rectangle in a plane of rectangles

I have a 2D plane (with discrete points) that contains arbitrary-sized rectangles and all rectangles are axis aligned. I have their coordinates (upper-left) and sizes (length and breadth).

Suppose I pick a rectangle in this plane and I want to find the closest edge to this rectangle (which also intersects with at least one of the projections of the adjacent side of the rectangle). Here is an example:

My first solution was to check each side of each rectangle one by one and calculate its distance to each side of the given rectangle. But this seems very computationally expensive (especially considering this in a graphical context i.e. every frame of input)

Second was to check if this rectangle is colliding with another (with AABB) if not then by the relative position of their top-left coordinate I can determine which will be the closest edge for this pair.

Can someone propose a better solution to this?

Note 1: You can assume no other rectangles can intersect (with any other) apart from the given rectangle.

EDIT: Thank you @user24714692 and @Clement44 for the answers. I was able to learn a lot from this problem. And I am thankful to you that I was able to build this snap feature in my project:

Solution

It seems a lot of tasks to perform.

First, ignore the fact that this is in a 2D plane.
Imagine, we have a line with some points on it.
Solve the "intersection" problem for the line. Let's call this x_axis.
Repeat the same solution for the second y_axis.
We want to find the "intersections" of every two lines with a shared intersection.

Let's imagine you pick one "original" rectangle to compare.
Let's add all the other rectangles in a second group for now.
Note that, the order does not matter. Besides, this is a higher than O(N ^ 2) algorithm, therefore we always sort, both rectangles and intersections.

Once you found the intersections, all you need, is to find the one rectangle with the minimum distance from your "original" rectangle. I'll leave this part to you.

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)

Prints

rectangle to compare: [(35, 88, 35, 74)] other rectangles: [(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_axis intersections: [(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_axis intersections: [(35, 74), (39, 74)] sorted x_axis intersections: [(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)] sorted y_axis intersections: [(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)]

We usually define a rectangle with two points, top right and bottom left points.
Here I used three points though:

Note

This problem may look easy at the first glance, but it is a hard question, in my opinion.
What we basically do here, we mirror the rectangles on the x and y axis first.
We find every two lines that have intersections. This technically belongs to those two rectangles. If any two rectangles have intersections, they are in our search space.
Then we have our third or main rectangle to compare with any of these two rectangle. Here we make the comparisons in both Y and X axis and see, our main rectangle is closer to distance, X or Y.

Note

Segment tree is used for range sum:

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)

Prints

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

Check to see how you can use segment tree for this problem to improve the efficiency? Look at the green lines below.

From Segment Tree

Similarly, check out binary search?

Sorting

Sorting is required. For instance, imagine your two rectangles that you want to check for shared intersections are too far from each other. Therefore, the two rectanlges are not in your search space to be compared with your main rectangle.
Therefore, if you sort, we don't have to check every single rectangle. We only need to check the "near" rectangles, if you will. Those rectangles in the vicinity of each others can only have "intersections".