Vectorizing a Rectangle Overlap Determination in Numpy

This question has only been asked for individual instances. I’m trying to vectorize this operation for rectangles in a coordinate system.

I have a list of rectangle coordinates, and I have this function to determine which ones, by index, are overlapping.

def range_overlap(r1, r2):
    r1v = range(r1[0], r1[1])
    r2v = range(r2[0], r2[1])
    r1h = range(r1[2], r1[3])
    r2h = range(r2[2], r2[3])
    verticaloverlap = set(r1v).intersection(r2v)
    horizontaloverlap = set(r1h).intersection(r2h)
    if verticaloverlap and horizontaloverlap:
        return True
    else:
        return False

I’m attempting to replace it with this process, done twice (each for top-bottom and left-right):

def innercheck(x, y):
    return np.logical_or(
            np.logical_and(y <= x.reshape(-1,1), y >= y.reshape(-1,1)),
            np.logical_and(x <= y.reshape(-1,1), x >= x.reshape(-1,1)))

def outercheck(x, y):
    return np.logical_or(
        np.logical_and(y <= y.reshape(-1,1), x >= x.reshape(-1,1)),
        np.logical_and(x <= x.reshape(-1,1), y >= y.reshape(-1,1)))

def overlap_check(x,y):
    return np.logical_or(innercheck(x, y), outercheck(x, y))

Data generation:

import numpy as np
n = 20
#s = np.random.randint(0, 1000)
s = 352
initmax = 10
multiplier = 5
addermax = 200

np.random.seed(s)
lefts = np.random.randint(low=0, high=initmax, size=n)
np.random.seed(s)
rights = np.random.randint(low=lefts+1, high=initmax*multiplier, size=n)
np.random.seed(s)
adder = np.random.randint(0, addermax, size=n)
lefts += adder
rights += adder

np.random.seed(s)
bottoms = np.random.randint(low=0, high=initmax, size=n)
np.random.seed(s)
tops = np.random.randint(low=bottoms+1, high=initmax*multiplier, size=n)
np.random.seed(s*2)
adder = np.random.randint(0, addermax, size=n)
bottoms += adder
tops += adder

plt.hlines(bottoms, xmin=lefts, xmax=rights)
plt.hlines(tops, xmin=lefts, xmax=rights)
plt.vlines(lefts, ymin=tops, ymax=bottoms)
plt.vlines(rights, ymin=tops, ymax=bottoms)
for n, (l, r, t) in enumerate(zip(lefts, rights, tops)):
    plt.text(np.mean([l, r]), t, n, fontsize=12)
plt.show()

rectangles = np.vstack((bottoms, tops, lefts, rights)).transpose().tolist()

Each rectangle’s index in rectangles is printed above itself plot of rectangles listed by image

Using my original approach:

overlapsbyindex = []
holder = rectangles.copy()
for a in rectangles:
    midlist = []
    for h in holder:
        overlap = range_overlap(a, h)
        if overlap:
            midlist.append(rectangles.index(h))
    overlapsbyindex.append(midlist)
print(overlapsbyindex)

[[0, 17], #this list at index 0 represents the rectangle at index 0, it overlaps with the rectangles at indices 0, and 17, and so on
 [1, 4],
 [2, 8, 16],
 [3],
 [1, 4],
 [5],
 [6],
 [7],
 [2, 8, 16],
 [9, 19],
 [10, 16],
 [11],
 [12, 17],
 [13],
 [14],
 [15],
 [2, 8, 10, 16],
 [0, 12, 17],
 [18],
 [9, 19]]

My new process is failing to find everything though:

rectangles = np.array(rectangles)
verticaloverlap = overlap_check(rectangles[:,0], rectangles[:,1])
horizontaloverlap = overlap_check(rectangles[:,2], rectangles[:,3])
overlapcheck = np.logical_and(verticaloverlap, horizontaloverlap)
vectorizedoverlaps = [np.where(i)[0].tolist() for i in overlapcheck.tolist()]
print(vectorizedoverlaps)

[[0, 17],
 [1, 4],
 [2, 16],
 [3],
 [1, 4],
 [5],
 [6],
 [7],
 [2, 8, 16],
 [9, 19],
 [10],
 [11],
 [12, 17],
 [13],
 [14],
 [15],
 [10, 16],
 [0, 17],
 [18],
 [19]]

I’ve filled this example with each of 3 scenarios for overlap:

  • Total encompassment: one within another/one encompassing another.
  • Side overlap: A longer side of one goes through 2 sides of another.
  • Corner overlap: 2 sides of one each go through one side of another.

It looks to me that it’s failing to find corner overlaps in a few instances, but not all of them. I’m having trouble grasping why.

Also: For my use-case, bordering = overlapping

Answer

This website has a nice interactive visualization for the criteria that you need:
https://silentmatt.com/rectangle-intersection/

Starting with the arrays of the corners you already generated:

# apply criteria
c1 = lefts < rights[:, None]
c2 = rights > lefts[:, None]
c3 = bottoms < tops[:, None]
c4 = tops > bottoms[:, None]

# extract indices where all criteria are `True`:
overlaps = np.argwhere(c1 & c2 & c3 & c4)

# remove "self-intersecting" polygons
overlaps = overlaps[overlaps[:, 0] != overlaps[:, 1]]

You could collect the results with something like:

from collections import defaultdict
results = defaultdict(set)

for src_id, tar_id in overlaps:
    results[src_id].add(tar_id)

Which shows:

defaultdict(set,
            {0: {17},
             1: {4},
             2: {8, 16},
             4: {1},
             8: {2, 16},
             9: {19},
             10: {16},
             12: {17},
             16: {2, 8, 10},
             17: {0, 12},
             19: {9}})