Mechanical steps for the natural-neighbor interpolation

[maistral]

TL;DR

The 2D interpolation variant; without the abstractions please.

So I have a massive (I mean, 1000-point) three-column 2D data series (z = f(x,y)) and at some point, I need intermediate values. An option that I thought of is to fit the entire data series in a surface, which is somewhat out of the question due to the nature of the experiments I'm working with (I mean, repeatedly deriving empirical equations is somewhat inefficient).

Another method I thought of is bilinear/cubic interpolation, which temporarily solved my problems, until I saw this certain 'natural-neighbor interpolation' which presents itself as a more efficient and accurate alternative. So I began searching and searching for materials, and the best I could see was this:
https://www.powershow.com/view/1223a7-MDczZ/2D_Interpolation_methods_powerpoint_ppt_presentation
(The slides on natural-neighbor interpolation start at slide 21) While I understood the concept of the method thanks to the slides, I have no idea how to execute it. Thanks to Wiki I have an idea on how to form the circumcircles, but I have no idea on how to generate the triangles to begin with.

Can someone show me to a resource that mechanically shows the steps in doing the method? A code that I can study is much more preferrable, if it is possible. thanks!

 

[maistral]

Update:

I saw this thing: https://excel-works.com/manual/interpxyz and quite frankly this is what I wanted. Apparently it also uses the natural-neighbor interpolation scheme. I tried looking for things and I also saw this:http://xongrid.sourceforge.net/ which apparently demonstrates how it is done. I looked at the source code and it was incomprehensible

Does someone know of a resource that can teach how the interpolation method is done at its most basic form, then from there I will try and build it up myself. Thank you!