algorithmgeometrycomputational-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: enter image description here

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:

enter image description here

Solution

  • It seems a lot of tasks to perform.

    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)]

    enter image description here

    Note

    enter image description here

    Note

    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]

    9

    24

    32

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

    enter image description here

    From Segment Tree

    Similarly, check out binary search?

    Sorting