0

私は地理空間データ、特にトラック (緯度と経度によって定義された地理的位置の順序付けられたシーケンス) をいじっています。

ほとんどのアプリケーションでは、開始点から特定の点までの累積距離を計算する必要があります。したがって、track.totalDistance[20]たとえば を呼び出すと、開始点から点までの距離がインデックス 20 で取得されます。

現在、連続するすべての距離を事前に計算し、変数を増やし、各ポイントに値を割り当てることでこれを解決していますが、これは、トラックを編集 (ポイントの追加、削除、更新) し、「合計distance」は、実際にはトラックポイントの固有のプロパティではなく、トラックを含むトラックのコンテキストにおけるトラックポイントの固有のプロパティです。

一方、ゲッター関数の評価を先延ばしすると、たとえば 、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 に答える