java - Bing map 地理数据解压缩算法移植到 PHP

Question

我正在尝试将 Microsoft 的解压缩算法从 Java 移植到 PHP(或者可能是 C++ 或 C#，因为那是 Microsoft)。这是一种从 Bing map 地理数据 API 结果中获取压缩形状数据并将其扩展为纬度/经度坐标的算法。他们已在其网站 https://msdn.microsoft.com/en-us/library/dn306801.aspx 上发布了算法

我的数据库中存储了一个坐标列表，我正在尝试检索定义多边形以处理形状的坐标数组。我的结果有所不同。谁能指出两者之间的差异？

编辑:我相信我的问题在于 PHP 不处理 LONG 类型整数，并且在进行按位运算时会发生精度损失。我可能需要转换一些操作以使用 BCMath。在这里帮忙？

解压算法(微软)

public const string safeCharacters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-";

private static bool TryParseEncodedValue(string value, out List<Coordinate> parsedValue)
{
    parsedValue = null;
    var list = new List<Coordinate>();
    int index = 0;
    int xsum = 0, ysum = 0;

    while (index < value.Length)        // While we have more data,
    {
        long n = 0;                     // initialize the accumulator
        int k = 0;                      // initialize the count of bits

        while (true)
        {
            if (index >= value.Length)  // If we ran out of data mid-number
                return false;           // indicate failure.

            int b = safeCharacters.IndexOf(value[index++]);

            if (b == -1)                // If the character wasn't on the valid list,
                return false;           // indicate failure.

            n |= ((long)b & 31) << k;   // mask off the top bit and append the rest to the accumulator
            k += 5;                     // move to the next position
            if (b < 32) break;          // If the top bit was not set, we're done with this number.
        }

       // The resulting number encodes an x, y pair in the following way:
       //
       //  ^ Y
       //  |
       //  14
       //  9 13
       //  5 8 12
       //  2 4 7 11
       //  0 1 3 6 10 ---> X

       // determine which diagonal it's on
       int diagonal = (int)((Math.Sqrt(8 * n + 5) - 1) / 2);

       // subtract the total number of points from lower diagonals
       n -= diagonal * (diagonal + 1L) / 2;

       // get the X and Y from what's left over
       int ny = (int)n;
       int nx = diagonal - ny;

       // undo the sign encoding
       nx = (nx >> 1) ^ -(nx & 1);
        ny = (ny >> 1) ^ -(ny & 1);

        // undo the delta encoding
        xsum += nx;
        ysum += ny;

        // position the decimal point
        list.Add(new Coordinate { Latitude = ysum * 0.00001, Longitude = xsum * 0.00001 });
    }

    parsedValue = list;
    return true;
}

我的解压算法(PHP)

function tryParseEncodedValue($value) {   
    $value = 'vx1vilihnM6hR7mEl2Q';
    var_error_log($value);
    $safeCharacters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-";
    $list = array();
    $index = 0;
    (int)$xsum = 0;
    (int)$ysum = 0;

    while ($index < strlen($value))   // While we have more data,
    {
        $n = 0;                       // initialize the accumulator
        $k = 0;                       // initialize the count of bits

        while (true)
        {
            if ($index >= strlen($value)) // If we ran out of data mid-number
            {
                var_error_log('failed: inxed >= strlen($value)');
                return false;             // indicate failure.
            }
            (int)$b = strpos($safeCharacters, $value[$index++]);

            if (!$b) {                    // If the character wasn't on the valid list,
                var_error_log('failed: character not in valid list');
                return false;             // indicate failure.
            }
            $n |= ($b & 31) << $k;        // mask off the top bit and append the rest to the accumulator
            $k = $k+5;                    // move to the next position
            if ($b < 32) break;           // If the top bit was not set, we're done with this number.
        }

        // The resulting number encodes an x, y pair in the following way:
        //
        //  ^ Y
        //  |
        //  14
        //  9 13
        //  5 8 12
        //  2 4 7 11
        //  0 1 3 6 10 ---> X

        // determine which diagonal it's on
        $diagonal = (int)((sqrt(8 * $n + 5) - 1) / 2);

        // subtract the total number of points from lower diagonals
        $n -= $diagonal * ($diagonal + (int)1) / 2;

        // get the X and Y from what's left over
        $ny = (int)$n;
        $nx = $diagonal - $ny;

        // undo the sign encoding
        $nx = pow(($nx >> 1), (-($nx & 1)) );
        $ny = pow(($ny >> 1), (-($ny & 1)) );

        // undo the delta encoding
        $xsum += $nx;
        $ysum += $ny;

        // position the decimal point
        $coordinates = array($ysum * 0.00001, $xsum * 0.00001);
        array_push($list, $coordinates); 
    }

    $parsedValue = $list;
    var_error_log($parsedValue);
    return $parsedValue;
}

已知输入Microsoft 提供了一个示例输入和输出来验证您的算法。 https://msdn.microsoft.com/en-us/library/jj158958.aspx#TestingYourAlg

compressed shape = 'vx1vilihnM6hR7mEl2Q'

预期输出

an array of coordinates
35.894309002906084, -110.72522000409663
35.893930979073048, -110.72577999904752
35.893744984641671, -110.72606003843248
35.893366960808635, -110.72661500424147

我的输出

array(4) {
  [0]=>
  array(2) {
    [0]=>
    float(1.0E-5)
    [1]=>
    float(1.0E-5)
  }
  [1]=>
  array(2) {
    [0]=>
    float(1.027027027027E-5)
    [1]=>
    float(1.0181818181818E-5)
  }
  [2]=>
  array(2) {
    [0]=>
    float(1.0825825825826E-5)
    [1]=>
    float(1.0552188552189E-5)
  }
  [3]=>
  array(2) {
    [0]=>
    float(1.1103603603604E-5)
    [1]=>
    float(1.0734006734007E-5)
  }
}

所以，我们可以看到 PHP 输出没有被正确计算，我有一种感觉，这与 Java 中转换为长整数和对整数运行按位运算的差异有关。 PHP 应该处理整数，无论​​它们是长整数、 float 还是整数，但我有一种感觉我忽略了一些东西。

我敢打赌问题与这条线有关。有人能指出差异吗？

n |= ((long)b & 31) << k;   // mask off the top bit and append the rest to the accumulator

Answer 1

我怀疑您的问题是在转换以下 C# 代码时出现的:

nx = (nx >> 1) ^ -(nx & 1);
ny = (ny >> 1) ^ -(ny & 1);

在您的 PHP 代码中，您将其转换为:

$nx = pow(($nx >> 1), (-($nx & 1)) );
$ny = pow(($ny >> 1), (-($ny & 1)) );

在 C# 中，^ 是按位异或运算，而不是幂。 PHP 使用相同的符号进行按位异或，因此请尝试将代码更改为:

$nx = ($nx >> 1) ^ (-($nx & 1));
$ny = ($ny >> 1) ^ (-($ny & 1));