Computer vision: Sample between pixels

Rotations, zooms and warps all need the image's value at positions between pixels.

What to build

A program that answers bilinear interpolation queries.

Requirements

  • A query gives x (column) and y (row) as decimal numbers. Clamp them into the image.
  • With x0, x1, fx and y0, y1, fy as in the hints, the value is ((1 − fx) p(y0, x0) + fx p(y0, x1)) × (1 − fy) + ((1 − fx) p(y1, x0) + fx p(y1, x1)) × fy.
  • Print each value with two decimal places.

Input

Line 1: H and W. Then H rows of W values. Then N and N lines x y.

Output

N lines.

Constraints

1 ≤ H, W ≤ 50; N ≤ 100.

Example

Input:

2 2
0 100
100 200
3
0.5 0.5
0 0
1 0.25

Output:

100.00
0.00
125.00

Why it works

Interpolating along x on the two surrounding rows and then along y weights each of the four neighbours by how close the position is to it.

Examples

Example 1 · Input
2 2
0 100
100 200
3
0.5 0.5
0 0
1 0.25
Expected output
100.00
0.00
125.00
Example 2 · Input
1 3
10 20 40
2
1.5 0
0.25 0
Expected output
30.00
12.50

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Clamp x into 0 to W − 1 and y into 0 to H − 1 first. Then x0 = int(x), x1 = min(x0 + 1, W − 1) and fx = x − x0; the same for y.

Hint 2

Blend along the top row and the bottom row, then blend those two results by fy.

Solution

Show one correct solution (try it yourself first)
h, w = map(int, input().split())
img = [list(map(float, input().split())) for _ in range(h)]
for _ in range(int(input())):
    x, y = map(float, input().split())
    x = min(max(x, 0.0), w - 1.0)
    y = min(max(y, 0.0), h - 1.0)
    x0, y0 = int(x), int(y)
    x1, y1 = min(x0 + 1, w - 1), min(y0 + 1, h - 1)
    fx, fy = x - x0, y - y0
    top = img[y0][x0] * (1 - fx) + img[y0][x1] * fx
    bottom = img[y1][x0] * (1 - fx) + img[y1][x1] * fx
    print(f"{top * (1 - fy) + bottom * fy:.2f}")

Lesson: Resizing and interpolation →