This is not exactly what you ask for but if it is about interpolation, you can use ListInterpolation with an InterpolationOrder of your choice:
f = ListInterpolation[rdata, InterpolationOrder -> 3];
Now you can use as a function from the plane to the reals, e.g. Map it over other lists of points in the plane.
Here is a plot with the data points in order to show how the list gets interpolated:
{m, n} = Dimensions[rdata]; pts = Join[Outer[List, Range[m], Range[n]], Map[List, rdata, {2}], 3]; w0 = Graphics3D[Sphere[Flatten[pts, 1], 0.1]]; w3 = Plot3D[f[s, t], {s, 1, m}, {t, 1, n}, PlotPoints -> 5 {m, n}, Mesh -> {m - 2, n - 2}]; Show[w0, w3]

When interpolating 3D points that are supposed to lie one a graph, then Interpolation can be used. If the $(x,y)$-points do not live on a regular quad grid then only InterpolationOrder->1 is supported. Note that the syntax {{x,y},z} has to be used.
n = 2000; x = RandomReal[{0, 1}, n]; y = RandomReal[{0, 1}, n]; z = Sin[2 Pi x + Pi y]/5.; rdata = Transpose[{Transpose[{x, y}], z}]; f = Interpolation[rdata, InterpolationOrder -> 1];
This interpolates the data over a triangle mesh, proabably the 2D-DelaunayMesh". This is how you can draw the resulting function:
R = DelaunayMesh[Transpose[{x, y}]]; Show[ Graphics3D[Sphere[Flatten /@ rdata, 0.01]], Plot3D[f[s, t], {s, t} ∈ R, Mesh -> All] ]

While the interpolation in the interior parts of the domain deem to be good, be cautious when using the interpolating function f close to the boundary of the domain.
ReliefPlot also expects the height values to lie on a quad grid; you can generate such a grid and sample f over it to create data that ReliefPlot can eat:
m = 200; n = 200; heights = Apply[f, Outer[ List, Subdivide[0.2, 0.8, m], Subdivide[0.2, 0.8, n] ], {2}]; ReliefPlot[heights, ColorFunction -> "GreenBrownTerrain"]
