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

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.

Answer 2

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...