0

我正在修补地理空间数据，特别是 Tracks（由纬度和经度定义的地理位置的有序序列）。

大多数应用程序要求我计算从起点到给定点的累积距离。因此，例如，如果我调用track.totalDistance[20]，我会得到从 start 到索引为 20 的点的距离。

目前我正在通过预先计算每个连续距离、增加一个变量并将值分配给每个点来解决这个问题，这不是一个好的行为，因为我打算编辑轨道（添加、删除和更新点）和“总距离”实际上不是跟踪点的内在属性，而是跟踪点在其包含轨道的上下文中的固有属性。

另一方面，如果我推迟对 getter 函数的评估，比如 ，getTotalDistance(track, 20)将会有很多重复且实际上是不必要的计算。

所以问题是：如何实现一个类，以便在任何时候更有效地获得任意索引的累积总和，同时避免不必要的计算（完全初始化或重复）？

我使用的语言主要是 Python、Javascript 和 C#，但我想答案可能是可以用任何语言实现的通用结构。

4

1 回答 1

0

您可以使用具有如下节点的自平衡树：

public class Node
{
    public Node(Node leftChild, Node rightChild)
    {
        FirstPoint = leftChild.FirstPoint;
        LastPoint = rightChild.LastPoint;
        LeafCount = leftChild.LeafCount + rightChild.LeafCount;
        BetweenDistance = leftChild.LastPoint.DistanceTo(rightChild.FirstPoint);
        TotalDistanceSum = leftChild.TotalDistanceSum
            + BetweenDistance
            + rightChild.TotalDistanceSum;
        IsLeaf = false;
        LeftChild = leftChild;
        RightChild = rightChild;
    }

    public Node(Point p)
    {
        FirstPoint = p;
        LastPoint = p;
        LeafCount = 1;
        IsLeaf = true;
    }

    /// The point of the leftmost decendant.
    public Point FirstPoint { get; set; }
    /// The point of the rightmost decendant.
    public Point LastPoint { get; set; }

    /// Number of leaves.
    public int LeafCount { get; set; }
    /// The distance from FirstPoint to LastPoint along the path.
    public double TotalDistanceSum { get; set; }
    /// The distance between LeftChild and RightChild.
    public double BetweenDistance { get; set; }

    /// Flag wheter this is a node or a leaf.
    public bool IsLeaf { get; set; }
    /// Left child of this non-leaf node.
    public Node LeftChild { get; set; }
    /// Right child of this non-leaf node.
    public Node RightChild { get; set; }

    /// Calculates the distance between two point along the path. 'start' is inclusive. 'end' is exclusive.
    public double DistanceSum(int start, int end)
    {
        if (IsLeaf || start >= LeafCount || end < 0 || start >= end)
            return 0;

        if (end > LeafCount) end = LeafCount;
        if (start < 0) start = 0;

        if (start == 0 && end == LeafCount)
            return TotalDistanceSum;

        int n = LeftChild.LeafCount;
        return LeftChild.DistanceSum(start, end)
            + BetweenDistance
            + RightChild.DistanceSum(start - n, end - n);
    }
}

public class Point
{
    public double X { get; private set; }
    public double Y { get; private set; }

    public Point(double x, double y)
    {
        X = x;
        Y = y;
    }

    public double DistanceTo(Point other)
    {
        double dx = other.X - X;
        double dy = other.Y - Y;
        return Math.Sqrt(dx*dx + dy*dy);
    }
}

例子：

var tree = new Node(
    new Node(
        new Node(new Point(0,0)),
        new Node(new Point(1,0))
    ),
    new Node(
        new Node(new Point(1,1)),
        new Node(new Point(0,1))
    )
);
double dist = tree.DistanceSum(0,4); // returns 3.0
于 2013-06-03T07:16:20.883 回答