# 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, r1)
r2v = range(r2, r2)
r1h = range(r1, r1)
r2h = range(r2, r2)
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

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)

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)

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],
,
[1, 4],
,
,
,
[2, 8, 16],
[9, 19],
[10, 16],
,
[12, 17],
,
,
,
[2, 8, 10, 16],
[0, 12, 17],
,
[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).tolist() for i in overlapcheck.tolist()]
print(vectorizedoverlaps)

[[0, 17],
[1, 4],
[2, 16],
,
[1, 4],
,
,
,
[2, 8, 16],
[9, 19],
,
,
[12, 17],
,
,
,
[10, 16],
[0, 17],
,
]
```

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

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:
```

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