Extract a Patch and Its Validity Mask

Task

Write extract_patch(image, origin, patch_shape, fill_value). image is a two- or three-dimensional NumPy array; its first two axes are height and width. origin may lie partly outside the image. patch_shape is a positive (height, width) pair.

Return (patch, mask). patch has the requested first two dimensions and the same trailing dimensions and dtype as the image. Fill positions outside the image with fill_value; copy valid source values into aligned positions. mask is a two-dimensional boolean array, true exactly where a source pixel was copied. Both outputs must own their storage and must not change the input.

Example

From a 3 x 3 image, origin (-1, 1) and patch (3, 3) copy source rows 0..1 and columns 1..2 into patch rows 1..2 and columns 0..1; all other positions use the fill value and a false mask.

Your implementation

You may import NumPy as np. Do not modify the image, print, or ask for input.