Rotating or zooming an image by moving pixels forward leaves holes. Map every output pixel backwards instead.
What to build
A program that warps an image with an affine matrix, using backward mapping and nearest-neighbour sampling.
Requirements
- The matrix maps input positions to output positions: x' = a x + b y + tx, y' = c x + d y + ty, with x the column and y the row. Its determinant is not 0.
- The output has the same size as the input. For each output pixel (x, y), apply the inverse matrix to get the source position, round each coordinate to the nearest whole number (halves up), and copy that pixel; if it lies outside the image, write 0.
- Print H rows of W values.
Input
Line 1: H and W. Then H rows of W values. Then two lines: a b tx and c d ty.
Output
H rows.
Constraints
1 ≤ H, W ≤ 40.
Example
Input:
2 3
1 2 3
4 5 6
1 0 1
0 1 0
Output:
0 1 2
0 4 5
Why it works
Because every output pixel asks the inverse transform where it comes from, each one receives exactly one value, and pixels whose source is outside the image are filled with 0.
Examples
2 3 1 2 3 4 5 6 1 0 1 0 1 0
0 1 2 0 4 5
4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 0 0 0 2 0
1 2 2 3 5 6 6 7 5 6 6 7 9 10 10 11
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Invert the matrix: with det = a d − b c, the inverse's 2 × 2 part is [[d, −b], [−c, a]] / det and its shift is −(that part) × (tx, ty).
Hint 2
Round a source position with `math.floor(v + 0.5)`; positions outside the image give 0.
Solution
Show one correct solution (try it yourself first)
import math
h, w = map(int, input().split())
img = [input().split() for _ in range(h)]
a, b, tx = map(float, input().split())
c, d, ty = map(float, input().split())
det = a * d - b * c
ia, ib, ic, id_ = d / det, -b / det, -c / det, a / det
itx, ity = -(ia * tx + ib * ty), -(ic * tx + id_ * ty)
for y in range(h):
row = []
for x in range(w):
sx = math.floor(ia * x + ib * y + itx + 0.5)
sy = math.floor(ic * x + id_ * y + ity + 0.5)
row.append(img[sy][sx] if 0 <= sx < w and 0 <= sy < h else "0")
print(" ".join(row))