Search
Close this search box.

Data Interpolation with SPLINE in C#

Often, when dealing with mathematical models for hazard estimation, one has to make the most out of just a handful of experimental data, and try to extract a rule or a behavioural function. While the use of lookup charts printed on paper may sometimes be a viable option, we won’t be able to rely on it when we want to implement a software solution.

When this is the case, soft-computing may look like the perfect solution; neural networks can process data, learn their trend, and elaborate new samples to fill the gaps; but this would involve a considerable use of computational resources (and a lot more time). So, how can we find a good compromise?

A simple and fast solution for the approximation of a function, is to interpolate it using a list of known samples and the Spline algorithm.

A possible application of this algorithm comes from the world of environmental hazard analysis. Let’s have a look at the “scaled distance/overpressure“ diagram, relating to the explosion of a given mass of TNT:

Using this diagram, we can estimate, given a mass of TNT, what kind of damage will be caused by its detonation. That is, given a scaled distance (function of the mass of exploding TNT and the distance of the considered point from the origin of the explosion), we can evaluate the corresponding overpressure, which can be easily translated to an extent of caused damage.

This diagram is often used in hazard analysis to predict the explosive effects of a given chemical agent, based on the “well-known” effects of an equivalent quantity of TNT. In fact, it is always possible to trace back a given quantity of an explosive to an equivalent mass of TNT.

But we are digressing 😉 Let’s get back on topic!

With a great deal of patience we’re able to extract a limited quantity of significant points from the diagram; these points can be close to a requested “Z”, but “close” isn’t nearly enough to assure a reliable result for any requested “Z”. We need to interpolate.

Many interpolation algorithms exist, but most of them introduce huge errors, often causing terrible results.

For example, here you can see that a polynomial interpolation is ineffective, as it completely changes the curve’s shape according to what samples are considered. The Spline, on the other hand, is able to determine an approximating curve, that avoids sharp shifts between two known values

To apply this algorithm I adapted Marco Roello’s implementation of a C# spline interpolator to my needs.

Here’s the resulting code:

public
static double SpLine(List<KeyValuePair<double, double>> knownSamples, double z)

{
  int np = knownSamples.Count;

  if (np > 1)

  {
    double[] a = new double[np];

    double x1;

    double x2;

    double y;

    double[] h = new double[np];

    for (int i = 1; i <= np - 1; i++)

    {
      h[i] = knownSamples[i].Key - knownSamples[i - 1].Key;
    }

    if (np > 2)

    {
      double[] sub = new double[np - 1];

      double[] diag = new double[np - 1];

      double[] sup = new double[np - 1];

      for (int i = 1; i <= np - 2; i++)

      {
        diag[i] = (h[i] + h[i + 1]) / 3;

        sup[i] = h[i + 1] / 6;

        sub[i] = h[i] / 6;

        a[i] = (knownSamples[i + 1].Value - knownSamples[i].Value) / h[i + 1] -

               (knownSamples[i].Value - knownSamples[i - 1].Value) / h[i];
      }

      // SolveTridiag is a support function, see Marco Roello's original code

      // for more information at

      // http://www.codeproject.com/useritems/SplineInterpolation.asp

      SolveTridiag(sub, diag, sup, ref a, np - 2);
    }

    int gap = 0;

    double previous = 0.0;

    // At the end of this iteration, "gap" will contain the index of the
    // interval

    // between two known values, which contains the unknown z, and "previous"
    // will

    // contain the biggest z value among the known samples, left of the unknown
    // z

    for (int i = 0; i < knownSamples.Count; i++)

    {
      if (knownSamples[i].Key < z && knownSamples[i].Key > previous)

      {
        previous = knownSamples[i].Key;

        gap = i + 1;
      }
    }

    x1 = z - previous;

    x2 = h[gap] - x1;

    y = ((-a[gap - 1] / 6 * (x2 + h[gap]) * x1 + knownSamples[gap - 1].Value) *
             x2 +

         (-a[gap] / 6 * (x1 + h[gap]) * x2 + knownSamples[gap].Value) * x1) /
        h[gap];

    return y;
  }

  return 0;
}

private
static void SolveTridiag(double[] sub, double[] diag, double[] sup,

                         ref double[] b, int n)

{
  .....
}

The SpLine() method receives two parameters: a List<KeyValuePair<double, double>> containing a list of known samples, and a double, containing the unknown value of for which we want to compute the function image.

In our case, we need to pass a list of known samples manually extracted from the diagram as first argument, and the given value of “Z” (on the X-axis) for which we want to compute the overpressure (on the Y-axis).

The list of known samples might be hard-coded, read from a database, or anything else. In our implementation, we decided to use an XML file to achieve the maximum flexibility and scalability. Modifying or inserting samples couldn’t be easier than editing an XML file.

So here’s an example of what our XML might look like:

<?xml version="1.0" encoding="utf-8" ?>

<tnt>

  <overPressure>

    <sample id="1" x="2" y="3"/>

    <sample id="2" x="3" y="2"/>

    <sample id="3" x="4" y="0.7"/>

    <sample id="4" x="5" y="0.49"/>

    <sample id="5" x="6" y="0.45"/>

    <sample id="6" x="7" y="0.28"/>

    <sample id="7" x="8" y="0.22"/>

    <sample id="8" x="9" y="0.18"/>

    <sample id="9" x="10" y="0.16"/>

    <sample id="10" x="20" y="0.06"/>

    <sample id="11" x="30" y="0.045"/>

    <sample id="12" x="40" y="0.023"/>

    <sample id="13" x="50" y="0.017"/>

    <sample id="14" x="60" y="0.015"/>

    <sample id="15" x="70" y="0.013"/>

  </overPressure>

  <otherFunction1>

    .... more samples ....

  </otherFunction1>

</tnt>

}

This file can be easily read using the .NET Xml classes. We chose to use the XmlReader because we only need a fast sequential forward-only view of our XML file.

So here’s a simple XML reader that scans our file and returns its content as an ordered List of KeyValuePairs which we can directly feed to the SpLine() method. The ReadValues() method takes the root name as an argument, so that we can put different sample lists (for different functions) in a file.

public
static List<KeyValuePair<double, double>> ReadValues(string xmlUri,
                                                     string rootName)

{
  XmlReaderSettings settings = new XmlReaderSettings();

  settings.IgnoreWhitespace = true;

  List<KeyValuePair<double, double>> dic =
      new List<KeyValuePair<double, double>>();

  using(XmlReader reader = XmlReader.Create(xmlUri, settings))

  {
    while (reader.Read())

    {
      if (reader.Name == rootName)

      {
        reader.ReadToDescendant("sample");

        while (reader.Name == "sample")

        {
          double key = Convert.ToDouble(reader.GetAttribute("x"),

                                        CultureInfo.InvariantCulture);

          double value = Convert.ToDouble(reader.GetAttribute("y"),

                                          CultureInfo.InvariantCulture);

          dic.Add(new KeyValuePair<double, double>(key, value));

          reader.Read();
        }

        break;
      }
    }

    reader.Close();
  }

  return dic;
}
}

Using this method we will be able to obtain an acceptable interpolation with small error and small computational effort.

JSON in ASP.NET Ajax: Part 2. Calling a remote JSON Web Service from client script

Now, after the very futile example which accompanied the introduction to JavaScript Object Notation in my last post (by the way, I forgot to mention that this is what the fancy acronym stands for, but I’m sure you already knew that), let’s go straight to the fun part, and see how we can leverage the flexibility of JSON (and ASP.NET AJAX, of course) to achieve some less trivial result. When developing a web application, we often need to aggregate data from different sources. You might argue this is no big news, as we’ve all used web services in a way or the other, and “mashup” is surely not an uncommon word these days. But probably, for most of us, the natural way to think of data returned from a web service call is XML. But XML is not exactly the easiest thing to parse on the client, nor a very succinct format. That’s why a number of JSON web services have flourished lately. Probably the first that comes to mind is Google Maps’ Geocoder (see here), but there are a lot more. If you are looking for inspiration you can have a look at xmethods. But today, we are focusing on some very, very interesting web methods kindly offered by Geonames.

In fact, as I’ve always mantained that an example is worth a googolplex words, in this post I’m going to describe a specific problem I had to solve recently, and the rather simple solution I found, using JSON and ASP.NET AJAX.
So, let’s get this started: enter

The Problem.

Let’s imagine we want to retrieve the most recent weather information for a specific location, given its geographic coordinates. In particular, let’s imagine that we let the user input the coordinates directly on the client (for example by clicking on a Virtual Earth map) and we want to visualize the latest weather data observed at the nearest weather station, avoiding the user the annoyance of the much dreaded postback.

The Solution.

Luckily, the findNearByWeatherJSON web service at Geonames does exactly what we need. It takes a longitude and latitude as parameters, and returns a JSON object describing the weather conditions gathered at the nearest observing site.

Although you could directly call this service from the client using classic AJAX patterns (see here for a simple example or  have a look at ajaxpatterns), we’ll focus on how to do that by using a proxy ASP.NET web service to avoid security problems and allow for more flexibility, and, as a nice bonus, have more readable and maintainable code. In fact, rather than following a RESTful approach, and call the web service directly from javascript, we’ll leverage the ASP.NET AJAX infrastructure and use the more concise and readable RPC-style generated for us by the framework.

But the question is: how? When faced with the necessity to create a server-side proxy for a remote JSON service, one might be tempted to try and find something like the “Add Web Reference” wizard Visual Studio has been spoiling us with for years… well, no luck this time, there’s nothing like that for JSON. In fact, while the wizard would help us if we had to consume a SOAP web service, there’s nothing like WSDL which can describe the results and help generate a proxy class for JSON services.

But the good news is, we don’t need any! In fact, unless you want to elaborate in some way the results returned from the web service (and I’ll cover that topic in one of my next posts), all you need to do is create a simple local ASP.NET web service whose only duty, when called, is to make a request to the remote web service and forward the result to the client. So, let’s see how to implement all this!

First of all, let’s see how to implement the ASP.NET proxy web service:

using System;

using System.Web.Script.Services;

using System.Web.Services;

 

namespace Mashup

{

    /* To allow this Web Service to be called from script using ASP.NET AJAX, 

    * we need to set the following attribute. */

    [ScriptService]

    [WebService(Namespace = "Mashup")]

    [WebServiceBinding(ConformsTo = WsiProfiles.BasicProfile1_1)]

    public class WeatherService : WebService

    {

        [WebMethod]

        public string GetWeatherByLocation(double lat, double lng)

        {

            return GeonamesWeather.GetWeatherByLocation(lat, lng);

        }

    }

}

As you can see, the web service we’re publishing takes two parameters, latitude and langitude of a location, and returns a string. We’ll see that this string is going to contain exactly the content of the response received from the Geonames Web Service. What we have to notice now, is that we decorated the WeatherService class with the [ScriptService] attribute. This is all we have to do to instruct the ASP.NET engine to create a Javascript helper class that will let us call this method very easily from client code.

NOTE: If you want to have a look at what the generated Javascript proxy class looks like, all you have to do is requesting the .asmx web service from your browser, and append /js to the url. (e.g. http://localhost:2687/JsonTest/WeatherService.asmx/js)

Now, let’s delve deeper into the implementation of the GetWeatherByLocation() method:

using System;

using System.Net;

using System.Globalization;

using System.IO;

 

namespace Mashup

{

    public class GeonamesWeather

    {

        private readonly static string FindNearbyWeatherUrl =

            "http://ws.geonames.org/findNearByWeatherJSON?lat={0}&lng={1}";

 

        public static string GetWeatherByLocation(double lat, double lng)

        {

            string formattedUri = String.Format(CultureInfo.InvariantCulture,

                                  FindNearbyWeatherUrl, lat, lng);

 

            HttpWebRequest webRequest = GetWebRequest(formattedUri);

            HttpWebResponse response = (HttpWebResponse)webRequest.GetResponse();

            string jsonResponse = string.Empty;

            using (StreamReader sr = new StreamReader(response.GetResponseStream()))

            {

                jsonResponse = sr.ReadToEnd();

            }

            return jsonResponse;

        }

 

        private static HttpWebRequest GetWebRequest(string formattedUri)

        {

            // Create the request’s URI.

            Uri serviceUri = new Uri(formattedUri, UriKind.Absolute);

 

            // Return the HttpWebRequest.

            return (HttpWebRequest)System.Net.WebRequest.Create(serviceUri);

        }

    }

}

As you can see, what the GetWeatherByLocation() method does is simply act as a proxy. We call the remote web service in a RESTful manner, retrieve the response, write it into a string and finally return the string to the caller method. The response returned from the findNearByWeatherJSON service will be something like this:

"{"weatherObservation":{

    "clouds":"few clouds",

    "weatherCondition":"n/a",

    "observation":"LICC 231720Z 29009KT 9999 FEW035 SCT070 16/07 Q1009",

    "windDirection":290,

    "ICAO":"LICC",

    "elevation":17,

    "countryCode":"IT",

    "lng":15.05,

    "temperature":"16",

    "dewPoint":"7",

    "windSpeed":"09",

    "humidity":55,

    "stationName":"Catania / Fontanarossa",

    "datetime":"2007-10-23 17:20:00",

    "lat":37.4666666666667,

    "hectoPascAltimeter":1009 }}"

NOTE: Carriage returns have been inserted only to improve readability, but the response stream won’t contain any.

As you can see, the similarity between this string and a Javascript object is quite evident. We’ll see in a moment how to leverage this – not so coincidental – fact.

Now, our server infrastructure is almost complete. The last step we have to take is referencing the Web Service we just created from the page that is actually going to use it.

To do this, we simply add a ScriptManager to the page, and add a reference to the web service in its <Services> section:

<asp:ScriptManager ID="ScriptManager1" runat="server">

    <Services>

        <asp:ServiceReference Path="~/WeatherService.asmx" />

    </Services>

</asp:ScriptManager>

Now we can start to set up a very simple test page to try our flaming new web service!

For now, we’ll only add a couple of textboxes to input latitude and longitude, and a button to start the Web Request. We’ll do it AJAX style, so we’ll use the HTML controls rather than their heavier ASP.NET counterparts. We’ll also add a div where we’re going to visualize the weather info retrieved from the web service. Note that we are giving id’s to all the controls so that we can reference them from the Javascript code that we are going to write.

<label for="txtLat">Latitude:</label><input type="text" id="txtLat" />

<label for="txtLng">Longitude:</label><input type="text" id="txtLng" />

<input type="button" value="Get Weather Info" onclick="callService();" />

<div id="divResult">

</div>

Now all that’s left to do is write the Javascript code to wire up everything.

We’ll start by implementing the callService() function that will be fired when clicking on the button. Please note that in a real scenario, clicking the button would trigger some sort of validation of the input data. We won’t do any of that here in order to keep the code as simple and streamlined as possible.

function callService() { 
    var latitude = $get('txtLat').value; 
    var longitude = $get('txtLng').value; 
    Mashup.WeatherService.GetWeatherByLocation(latitude, longitude,
    GetWeather_success, onFailed); 
}

Let’s see what we are doing here. First of all we are creating two variables, latitude and longitude, which contain the value of the two textboxes.

NOTE: Those of you who haven’t put their hands on the client side ASP.NET AJAX library yet, might wonder what the $get function does. Actually, not much, except sparing you some keystrokes, as it is a mere shortcut for the Javascript getElementById function. In particular, when called passing only one parameter, the $get alias resolves to document.getElementById, while when called like this: $get(id, element), it resolves to element.getElementById(id).

After that, we’re finally ready to call our proxy service. We do that by calling the Javascript proxy method generated for us care of the ASP.NET AJAX framework. As you can see, we can find our WeatherService.GetWeatherByLocation() method inside the Mashup namespace. Please note we have to use the fully qualified name to invoke the service.

Besides the two parameters defined in the web method signature in the server side code, we see that the generated Javascript method takes some additional parameters: onSuccessonFailed and userContext. As you have probably already realised, they take the name of two callbacks, one that will be executed upon successful completion of the remote method invocation, the other that will be called in the unfortunate event something went wrong. The third parameter, which we are not using here, would let you pass a custom user context to the callback.

Now, if everything works as expected, the GetWeather_success function will be called (asynchronously) when the web service response is ready, and will get as an argument the web method’s return value, in our case, a string containing our JSON-serialized weather observation object.

Now the very last thing we need to do is deserialize such string into a real Javascript object. To do that, we might simply call the Javascript eval() function, as I anticipated in my previous post:

function GetWeather_success(e) { 
    var result = eval('(' + e + ')'); 
    var weatherData = new Sys.StringBuilder(); 
    var line; 
    for(var property in result.weatherObservation) 
    { 
        line = String.format("<b>{0}:</b> {1}<br/>", property, 
        result.weatherObservation[property]); weatherData.append(line); 
    } 
    $get('divResult').innerHTML = weatherData.toString(); 
}
function onFailed() { 
    $get('divResult').innerHTML = 'Something went terribly wrong!'; 
}

As I just said, when this function is called, it is passed the web method response, thus e contains the JSON representation of a Javascript object containing all the relevant weather data retrieved from our remote Web Service. As you can see, calling eval() deserializes the string and returns an object we can readily use.

From now on, what we are going to do with this native Javascript object is entirely up to us. Here, as a mere example, I’m enumerating all its properties and displaying them inside the div we created for this purpose.

What’s worth noting here is the use of two very interesting and useful ASP.NET AJAX features: the Sys.StringBuilder class that mimics its server-side homonym and greatly improves string concatenation performance over the “+” overload, and the String.format() function, which endows Javascript with the very useful .NET String.Format() method we are all used to.

For those of you concerned with security, as I said earlier, eval() is probably not the safest option to deserialize JSON, so you might decide to resort to a JSON parser (you can find one here on json.org), or once again leverage the power of ASP.NET AJAX, by using the built-in JavaScriptSerializer. If you simply substitute the first line in GetWeather_success() with the following line:

var result = Sys.Serialization.JavaScriptSerializer.deserialize(e, true);

the string returned from the web method will be checked against a regular expression to ensure it is actually a valid JSON string.

Well, that’s all for now! I hope that this short introduction to the use of JSON with ASP.NET has been useful to some of you!

You can see a live Demo here or download the Source Code of this project here.

Enjoy!

Marco

JSON in ASP.NET Ajax: First words

If you are a web developer, and you haven’t been living under a rock for most of the past year, you must at least have heard of JSON. In the wake of the tremendous hype relating to everything even vaguely AJAX-related, JSON has climbed in record time the list of the top 10 technologies a web developer has to master.

Let’s make it clear from the start: JSON does deserve a top spot in such a list, if nothing else because it’s the skeleton that keeps the whole AJAX paradigm on its feet. Even more so for us .NET programmers. In fact, we’d be more accurate if we called it AJAJ, although I agree that would feel quite stupid 

. As a matter of fact, when using ASP.NET AJAX, most of the communication between client and server is serialized in JSON format rather than XML, at least when using the default settings. And there’s good reason for that.

In fact, JSON is a very simple human-readable, easily-parsable data-interchange format, like XML, but unlike the latter, it is very concise, and, more importantly, it is immediately convertible to a Javascript object. That is, if you simply eval() a JSON expression, you get returned the actual object that was serialized in the first place.

For those of you who might not know it, eval() is a built-in javascript function that evaluates a string and executes it as a line of code (see here for more info).

For example, you might serialize a very simple “Person” object that has properties “firstName”, “lastName”, and “age” as follows:

{"firstName":"Marco","lastName":"Anastasi","age":27}

Note that property names are always enclosed in double quotes, while values follow the usual javascript syntax.

In Javascript, you would then be able to use code like this:

var json = '{"firstName":"Marco", "lastName":"Anastasi", "age":27}';
var person = eval('(' + json + ')'); 
alert(person.firstName);

Note that we enclose the json expression we are evaluating in parentheses, to instruct eval() to treat the string as an expression rather than a block of code.

WARNING: what you see here is merely used as an example. You should avoid resorting to the eval() function in a production environment, because of potential security breaches. There are valid alternatives out there, and a good place to start looking for them is, of course www.json.org.

In my next posts I’ll talk profusely about one of the possible solutions to this problem (and probably the one that ASP.NET developers are keener to use), i.e. ASP.NET AJAX’s built-in client side JSON serializer/deserializer.

What you’ve seen so far is obviously a very simplified introduction to JSON, and doesn’t show much of what you might achieve by leveraging its power and simplicity. In my next post, I’ll delve deeper into its inner workings and how to use it to manage the communication between client side script and a server-side application, and finally to retrieve information from web services, shape it into different formats and serve it to the client browser.

For more information to get you started with JSON, visit www.json.org

Marco

Our First Post

Hi, this is our first post. We finally decided to set up a blog where to write about our development experiences.

We’re both Computer Engineering students and .NET programmers.

Our interest is mainly focused on Web Development, using ASP.NET, SQL Server, CSS, and (recently) Javascript.

We’re also interested in developing soft-computing models for risk prediction and analysis.

We hope this weblog might contribute positively to the already thriving .NET developers’ community!

Marco & Serena

This article is part of the GWB Archives. Original Author: Juan DoNeblo

Related Posts