距離の近似値計算

大昔、平方根(sqrt)を使わない距離の近似式が話題になってて、PHP で実験してたのを突然思い出した。忘れないうちにメモしとく。

• flipcode - Fast Approximate Distance Functions

要するに曲線でなく面を折り畳んで似た形にして、その面を表す式で近似する。
MAX の式で凸面、MIN の式で凹面が出来て、それらを適当な割合で足すとかなり良い感じの形になり、あと x と y の差があり過ぎる時に大きくズレルので減算の補正をかけてる。

乗算無しバージョンの式もあるけど、乗算を使う方ので実験。

3次元版

function approx_distance_3d( $dx, $dy, $dz)
{
    return approx_distance(approx_distance( $dx, $dy ), $dz);
}

等とすれば３次元に拡張出来るはず。

試した感じかなり良い値を出す。(ad が近似値で、cd が正確な値)

yoya@sakura:~$ php approx_distance.php  10 10 10
dx:10.000, dy:10.000, dz:10.000, ad:18.000, cd:17.321
yoya@sakura:~$ php approx_distance.php  10 20 30
dx:10.000, dy:20.000, dz:30.000, ad:38.000, cd:37.417
yoya@sakura:~$ php approx_distance.php  10 100 1000
dx:10.000, dy:100.000, dz:1000.000, ad:987.000, cd:1005.037

approx_distance.php

<?php
// http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml     

function approx_distance( $dx, $dy )
{
    if ( $dx < 0 ) $dx = -$dx;
    if ( $dy < 0 ) $dy = -$dy;

    if ( $dx < $dy ) {
        $min = $dx; $max = $dy;
    } else {
        $min = $dy; $max = $dx;
    }
    $approx = ( $max * 1007 ) + ( $min * 441 );
    if ( $max < ( $min << 4 )) {
        $approx -= ( $max * 40 );
    }
    // add 512 for proper rounding                                                
    return (( $approx + 512 ) >> 10 );
}

function approx_distance_3d( $dx, $dy, $dz)
{
    return approx_distance(approx_distance( $dx, $dy ), $dz);
}

if ($argc !== 4) {
    echo "Usage: php approx_distance.php 10 20 30\n";
    exit(1);
}
list($prog, $dx, $dy, $dz) = $argv;

$ad = approx_distance_3d($dx, $dy, $dz); // aproximate value                      

$cd = sqrt($dx*$dx + $dy*$dy + $dz * $dz); // correct value                       

printf("dx:%.3f, dy:%.3f, dz:%.3f, ad:%.3f, cd:%.3f\n", $dx, $dy, $dz, $ad, $cd);