# Creating overlapping, square patches for rectangular images

Given be a rectangular image `img` and patch `s`. Now I would like to cover the whole image with square patches of side length `s`, so that every pixel in `img` is in at least one patch using the minimal number of patches. Furthermore I want neighboured patches to have as little overlap as possible.

Thus far: I have included my code below and worked out an example. However it does not work yet perfectly. Hopefully, someone finds the error.

Example: Given is `img` of shape: `(4616, 3016)` and `s = 224` That means I will 21 patches on the longer side, 14 patches on the smaller the width, 21*14 = 294 patches in total.

Now I try to figure out patches how to distribute the overlap between the patches. My patches can cover an image of size: `(4704, 3136)`, thus my patches in the height have to cover 88 overlapping pixels `missing_h = ht * s - h`, width is analogous.

Now I try to figure out, how to distribute 88 pixels on 21 patches. 88 = 4* 21 + 4 Thus I will have `hso = 17` patches with overlap `shso = 4` and `hbo = 4` patches with overlap 5, width is analogous.

Now I simply loop over the whole image and keep track on my current position `(cur_h, cur_w)`. After each loop I adjust, `cur_h, cur_w`. I have `s`, my current patch number `i, j`, that indicates if the patch has a small or big overlap.

```import numpy as np

def part2(img, s):
h = len(img)
w = len(img[0])

ht = int(np.ceil(h / s))
wt = int(np.ceil(w / s))

missing_h = ht * s - h
missing_w = wt * s - w
hbo = missing_h % ht
wbo = missing_w % wt
hso = ht - hbo
wso = wt - wbo
shso = int(missing_h / ht)
swso = int(missing_w / wt)

patches = list()
cur_h = 0

for i in range(ht):
cur_w = 0
for j in range(wt):
patches.append(img[cur_h:cur_h + s, cur_w: cur_w + s])
cur_w = cur_w + s
if j < wbo:
cur_w = cur_w - swso - 1
else:
cur_w = cur_w - swso
cur_h = cur_h + s
if i < hbo:
cur_h = cur_h - shso - 1
else:
cur_h = cur_h - shso

if cur_h != h or cur_w != w:
print("expected (height, width)" + str((h, w)) + ", but got: " + str((cur_h, cur_w)))

if wt*ht != len(patches):
print("Expected number patches: " + str(wt*ht) + "but got: " + str(len(patches)) )

for patch in patches:
if patch.shape[0] != patch.shape[1] or patch.shape[0] != s:
print("expected shape " + str((s, s)) + ", but got: " + str(patch.shape))
return patches

def test1():
img = np.arange(0, 34 * 7).reshape((34, 7))
p = part2(img, 3)
print("Test1 successful")

def test2():
img = np.arange(0, 4616 * 3016).reshape((4616, 3016))
p = part2(img, 224)
print("Test2 successful")

test1()
test2()
```

```hbo = missing_h % (ht-1)