Extrapolation delaunay triangulation

Question

Shown Figure (1) is a typical Delaunay triangulation (blue) and it has a boundary line (black rectangle).

Each vertex in the Delaunay triangulation has a height value. So I can calculate the height inside convex hull. I am figuring out a method to calculate the height up to the boundary line (some sort of extrapolation). There are two things associated with this task

1. Triangulate up to the boundary point

2. Figuring out the height at newly created triangle vertices

Anybody come across this issue?

Figure 1:

Answer 1

I'd project the convex hull points of the triangulation to the visible box segments and then insert the 4 box corners and the projected points into the triangulation.

There is no unique correct way to assign heights to the new points. One easy and stable method would be to assign to each new point the height of the closest visible convex hull vertex. Be careful with extrapolation: Triangles of the convex hull tend to have unstable slopes, see the large triangles in front of the below terrain image. Their projection to the xy plane has almost 0 area but due to the height difference they are large and almost 90 degrees to the xy plane.

Answer 2

I've had some luck with the following approach:

1. Find the segment on the convex hull that is closet to the extrapolation point
2. If I can drop a perpendicular onto the segment, interpolate between the two vertices of the segment.
3. If I can not construct the perpendicular, just use the closest vertex

This approach results in a continuous surface, but does not provide 1st derivative continuity.

You can find some code that might be helpful at TriangularFacetInterpolator.java. Look for the interpolateWithExteriorSupport method.