一维轴对齐矩形长方体 (MBR) 的交集

Question

目前我正在做时间序列索引算法的基准测试。由于大多数时候没有可用的参考实现，我必须编写自己的实现（全部在 Java 中）。目前，我在一篇名为 Indexing multi-dimensional time-series with support for multiple distance measures available here in PDF : http://hadjieleftheriou.com/papers/vldbj04-2.pdf

的论文的第 6.2 节有点卡住了

MBR（最小边界矩形）基本上是一个具有某些坐标和方向的长方体。例如，P 和 Q 是两个 MBR，其中 P.coord={0,0,0} 和 P.dir={1,1,3} 和 Q.coords={0.5,0.5,1 } 和 Q.dir={1,1,1} 其中第一个条目表示时间维度。

现在我想计算 Q 和 P 之间的 MINDIST(Q,P) :

但是我不确定如何实现 "intersection of two MBRs in the time dimension" (Dim 1)，因为我不确定时间维度中的交集实际上意味着什么。也不清楚 h_Q、l_Q、l_P、h_P 是什么意思，因为这个符号没有解释（我猜他们的意思是最高或最低值交叉点中的维度）。

如果有人能向我解释如何计算第一维中两个 MBR 的交集，并可能通过对符号的解释来启发我，我将不胜感激。谢谢！

Answer 1

好吧，你论文中的图 14 解释了时间交集。并且矩形是axis-aligned，因此在每个坐标上使用高和低是有意义的。

你看到的乘号不是叉积，只是一个普通的乘法，因为它的两边都是标量，而不是向量。

但是我必须同意第 14 页上的讨论相当模糊，但它们似乎告诉我们两种类型的交集（完整的和部分的），当它们有 t 下标时，表示交集的范数t坐标。

因此，您似乎可以分解时间交集以获得一个公式：

值得注意的是，可能counter-intuitively，当你的对象在时间平面上不相交时，它们的MINDIST被定义为0。

因此 pseudo-code ;

mindist(P, Q)
{
    if( Q.coord[0] + Q.dir[0] < P.coord[0] ||
        Q.coord[0] > P.coord[0] + P.dir[0] )
            return 0;

    time = min(Q.coord[0] + Q.dir[0], P.coord[0] + P.dir[0]) - max(Q.coord[0], P.coord[0]);

    sum = 0;
    for(d=1; d<D; ++d)
    {
        if( Q.coord[d] + Q.dir[d] < P.coord[d] )
            x = Q.coord[d] + Q.dir[d] - P.coord[d];
        else if( P.coord[d] + P.dir[d] < Q.coord[d] )
            x = P.coord[d] + P.dir[d] - Q.coord[d];
        else
            x = 0;

        sum += x*x;
    }

    return sqrt(time * sum);
}

注意论文中的绝对值是不必要的，因为我们只是检查了哪些值更大，因此我们知道我们只添加正数。

一维轴对齐矩形长方体 (MBR) 的交集

Intersection of axis-aligned rectangular cuboids (MBR) in one dimension

algorithm

math

indexing

geometry

time-series