Interpolation in PHP

Question

I'm looking for a function in PHP for interpolating a set of irregular placed data (x,y,z) to a gridded data set for using it in ContourPlot function in JPGraph. I've developed a function based on simple Inverse distance weighting, but it is too slow. I need to use another method like "Modified Shepard's Method" or any other possible methods with more accuracy to make it faster and smoother.

Here is my current code:

for($i = 0, $ij = 0; $i < $gridX; $i ++) {
    for($j = 0; $j < $gridY; $j ++, $ij ++) {
        $x = $startP->x + ($deltaX * $i);
        $y = $startP->y + ($deltaY * $j);
        $g [$ij]->i = $i;
        $g [$ij]->j = $j;
        $g [$ij]->x = ( int ) $x;
        $g [$ij]->y = ( int ) $y;
        $g [$ij]->z = IDW_U ( $x, $y, $sampleData, $sampleSize, $p );
    }
}

function IDW_U($x, $y, $data, $size, $p) {
    $idw_sum = IDWeightSum ( $x, $y, $data, $size, $p );
    $idw_u = 0.0;
    for($k = 0; $k < $size; $k ++) {
        if ($x == $data [$k]->x && $y == $data [$k]->y)
            return $data [$k]->z;
        $idw_u += IDWeight ( $x, $y, $data [$k], $p ) * $data [$k]->z / $idw_sum;
    }
    return $idw_u;
}

function IDWeightSum($x, $y, $data, $size, $p) {
    $sum = 0.0;
    for($k = 0; $k < $size; $k ++)
        $sum += IDWeight ( $x, $y, $data [$k], $p );
    return $sum;
}

function IDWeight($x, $y, $d, $p) {
    if ($x == $d->x && $y == $d->y)
        return 1.0;
    $dx = $x - $d->x;
    $dy = $y - $d->y;
    $ret = 1.0 / pow ( sqrt ( pow ( $dx, 2 ) + pow ( $dy, 2 ) ), $p );
    return $ret;
}

Does anybody know a function or library available for this purpose?

Answer 1

If you aren't tied to PHP, you should look at switching away from it for as much of this intensive processing as you can. PHP is a slower language (last time I looked - about a year ago, both Python and Ruby outperformed it, as well as C, C++, and Java.

So by switching to an off-line graphing tool (such as gnuplot, as mentioned in the comments), rerunning your performance tests, and if necessary, switching the algorithm to a Python or Ruby script or a compiled C or C++ application, you would get a performance boost.

However, I couldn't find any more recent performance data on PHP compared to other languages since late 2008/early 2009 - my data might not be true anymore.

Answer 2

It might help you to pass the data by reference:

 function IDW_U($x, $y, &$data, $size, $p) ...
 function IDWeightSum($x, $y, &$data, $size, $p) ...

Answer 3

I am not that sure PHP would be a good choice for math intensive functionality like that. However, there are a lot of graphing libraries available where the code has been optimized, put into DLL's and things like that.

We have used Advanced Software Engineering ChartDirector PHP Charting for some pretty complex graphs and it is fast. I don't know for sure if it includes the algorithm you are interested in, but it does include some like LOWESS. The main problem I see is that you are dealing with X, Y, and Z. The handling the third dimension is not the most common feature. I am not sure this library will actually support that...

Answer 4

As far as I can see IDWeight is called quite often. You could half the number of calls to that by calculating IDW_U like that:

function IDW_U($x, $y, $data, $size, $p) {
$idw_sum = 0.0;
$idw_u = 0.0;
for($k = 0; $k < $size; $k ++) {
    if ($x == $data [$k]->x && $y == $data [$k]->y)
        return $data [$k]->z;
    $iw = IDWeight ( $x, $y, $data [$k], $p )
    $idw_u += $iw * $data [$k]->z;
    $idw_sum += $iw;
}
return $idw_u / $idw_sum;
}

I think the main problem is, that for the calculation of one pixel, all datasets are used, while most of them will have small impact. You could really increase the performance by splitting the data into small areas and calculate all areas seperatly.