interpolate points on a height map

Question

I have some values (bytes) over a plane evenly distributed (the come from real measures) like for instance temperature. I'm trying to generate the whole surface. But I'm not successful.

The main condition is that the number and position of the points will not be known and that the surface MUST keep the value in the points where is measured and the points in between will be interpolated.

Ideally, if only one point is set the final surface should be a mountain.

By the way, and just in the case that it may help. Im coding it on WPF (C#) and it would nice to not involve heavy libraries or whatever for such an small job

Thanks in advance !

Answer 1

The typical way is to build a Delaunay triangulation of the sample set in the domain (a rectangle in your case), then use the triangles found as the surface.

---

The delaunay triangulation of a general set of points is defined as the set of triangles whose circumcircles does not contain any other point.

The trivial algorithm for computing the Delaunay triangulation (pick all triangles to see if any point is within their circumcircle) is O(n^4).

The incremental algorithm runs in O(n log n) expected time:

• Generate a triangulation of three points (in your case, four - the corners of the room).
• For each point
  • add it to the triangulation.
  • for every edge opposite the new point recursively
  • if the edge is not a part of the Delaunay triangulation of the current set of points, flip it.

The divide and conquer algorithm offers O(n log n) as well, but offers O(n log log n) for some point sets as well.

---

Once you have the triangulation, you just need to find the measured value by intersecting a vertical line with the surface:

• find the triangle ABC on which the point lies.
• express the point coordinates as A + k(B-A) + l(C-A)
• then the point value is given as A.value + k(B.value-A.value) + l(C.value-A.value) (treat the triangle as a plane in the [domain x range] space.