Geeks With Blogs

News Welcome to Marco Anastasi and Serena Caruso's technical weblog on Microsoft .NET technologies and related matters!
Juan DoNeblo Just another Dot Net blog by marco anastasi & serena caruso

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:

overpressure

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.

Serena

kick it on DotNetKicks.com Digg! Posted on Thursday, October 25, 2007 9:07 PM C# , Mathematical models | Back to top


Comments on this post: Data Interpolation with SPLINE in C#

# re: Data Interpolation with SPLINE in C#
Requesting Gravatar...
Evald,

I believe that you need to change the following line in the SpLine method...

double previous = 0.0;

... to this ...

double previous = double.MinValue;

I haven't tested the change much, but that seems to have worked for me.
Left by Dan Jagnow on Dec 20, 2007 11:50 PM

# re: Data Interpolation with SPLINE in C#
Requesting Gravatar...
Works flawlessly. Thanks.
Left by B Nichols on Mar 22, 2009 4:57 PM

# re: Data Interpolation with SPLINE in C#
Requesting Gravatar...
Great demo however when I try to add bigger value it all goes wrong. I know have the xml setup:
<sample id="1" x="10" y="417.00"/>

<sample id="2" x="20" y="506.00"/>

<sample id="3" x="30" y="477.00"/>

<sample id="4" x="40" y="383.00"/>

<sample id="5" x="50" y="386.00"/>

<sample id="6" x="60" y="438.00"/>

<sample id="7" x="70" y="405.00"/>

<sample id="8" x="80" y="404.00"/>

<sample id="9" x="90" y="436.00"/>

<sample id="10" x="100" y="461.00"/>

<sample id="11" x="110" y="442.00"/>

<sample id="12" x="120" y="326.00"/>

<sample id="13" x="130" y="328.00"/>

<sample id="14" x="140" y="278.00"/>

<sample id="15" x="150" y="280.00"/>

<sample id="16" x="160" y="345.00"/>

<sample id="17" x="170" y="234.00"/>

<sample id="18" x="180" y="230.00"/>

<sample id="19" x="190" y="280.00"/>

<sample id="20" x="200" y="252.00"/>

<sample id="21" x="210" y="241.00"/>

<sample id="22" x="220" y="294.00"/>

<sample id="23" x="230" y="249.00"/>

<sample id="24" x="240" y="340.00"/>

<sample id="25" x="250" y="234.00"/>

but it tells me I have an index out of bounds error. I have tried the above fix but to no avail :-(
Left by P Batt on Jul 07, 2009 8:25 AM

# re: Data Interpolation with SPLINE in C#
Requesting Gravatar...
Superb! Works like a charm! So simple. Nice one. Thank you!
Left by Gizz on Aug 11, 2010 3:33 AM

Your comment:
 (will show your gravatar)


Copyright © Marco Anastasi & Serena Caruso | Powered by: GeeksWithBlogs.net | Join free