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

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