2

私の問題

GPS デバイスと傾斜計 (実際にはどちらも携帯電話ではなくスタンドアロン デバイスです) に接続し、ユーザーが車を運転している間にデータをログに記録するプログラムからデータ ストリームが送信されます。私が受け取る重要なデータは次のとおりです。

  • 緯度/経度 - GPS から、約 +-5 フィートの解像度で、
  • 車両の地上速度 - GPS から、ノットで、MPH に変換
  • シーケンシャル レコード インデックス - データベースからの自動インクリメント整数であり、何も削除されません。
  • 私の現在の問題に関係のない他のもの。

このデータはデータベースに保存され、データベースから配列に読み戻されます。最初から最後まで、記録順序は適切に維持されるため、GPS デバイスから記録されるタイムスタンプは 1 秒の精度でしかなく、5 Hz でサンプリングしても、時間の絶対値は重要ではなく、挿入順序は重要ではありません。で十分です。

データの分析を支援するために、ユーザーは、収集された経路データから道路上のカーブの「開始」と「終了」を選択するという非常に基本的なデータ入力タスクを実行します。Google から地図画像を取得し、その上に曲線データを描画します。ユーザーは、その領域に関する独自の知識に基づいて、関心のある曲線にズームインし、マップ上の 2 つのポイントをクリックします。Google は実際には非常に優れており、ユーザーがクリックした場所を緯度/経度で報告してくれるので、ユーザーがデータに関連してどこをクリックしたかという問題はカバーされています。

曲線を拡大すると、データがクリップされます。ズーム レベルで定義された緯度/経度ウィンドウに収まるデータのみを取得します。ほとんどの場合、私は 300 未満のデータ ポイントを扱っていますが、1 回の運転セッションで 10 万を超えるデータ ポイントが発生する可能性があります。

クリック ポイントの間にある曲線データのサブセグメントを見つける必要があります。

私が試したこと

最初は、各クリック ポイントに最も近い 2 つのポイントを取得し、曲線はそれらの間のすべてのものでした。ドライバーが道路を何度も通過できるようになるまで、それは機能していました。通常、ドライバーは興味深い道路を 2 回往復して、合計 4 回のパスを行います。2 つのクリック ポイントに最も近い 2 つのポイントを取得すると、最初のポイントが 1 つのパスのデータムに対応し、2 番目のポイントがまったく別のパスのデータムに対応することになる場合があります。これらの 2 つの点の間のシーケンス内の点は、曲線をはるかに超えて拡張されます。そして、運が良く、見つかったすべてのデータ ポイントが両方とも同じパス上にあったとしても、パスの 1 つしか得られないため、すべてのパスを収集する必要があります。

しばらくの間、私ははるかにうまく機能するソリューションを持っていました。各データ ポイントから各クリック ポイントまでの距離を表す 2 つの新しいシーケンスを計算し、次にその距離のおおよその 2 次導関数を計算して、データ ポイント上のクリック ポイントからの距離の変曲点を探しました。変曲点とは、変曲点の前の点がクリック点に近づき、変曲点の後の点がクリック点から遠ざかっていることを意味すると推論しました。これをデータ ポイントに対して繰り返し行うことで、曲線をグループ化することができました。

おそらくいくつかのコードが適切です (これは C# ですが、親切に返信することを心配しないでください。私はほとんどの言語を読むことができます)。

static List<List<LatLngPoint>> GroupCurveSegments(List<LatLngPoint> dataPoints, LatLngPoint start, LatLngPoint end)
{
    var withDistances = dataPoints.Select(p => new
    {
        ToStart = p.Distance(start),
        ToEnd = p.Distance(end),
        DataPoint = p
    }).ToArray();
    var set = new List<List<LatLngPoint>>();
    var currentSegment = new List<LatLngPoint>();
    for (int i = 0; i < withDistances.Length - 2; ++i)
    {
        var a = withDistances[i];
        var b = withDistances[i + 1];
        var c = withDistances[i + 2];

        // the edge of the map can clip the data, so the continuity of
        // the data is not exactly mapped to the continuity of the array.
        var ab = b.DataPoint.RecordID - a.DataPoint.RecordID;
        var bc = c.DataPoint.RecordID - b.DataPoint.RecordID;

        var inflectStart = Math.Sign(a.ToStart - b.ToStart) * Math.Sign(b.ToStart - c.ToStart);
        var inflectEnd = Math.Sign(a.ToEnd - b.ToEnd) * Math.Sign(b.ToEnd - c.ToEnd);

        // if we haven't started a segment yet and we aren't obviously between segments
        if ((currentSegment.Count == 0 && (inflectStart == -1 || inflectEnd == -1)
        // if we have started a segment but we haven't changed directions away from it
            || currentSegment.Count > 0 && (inflectStart == 1 && inflectEnd == 1))
        // and we're continuous on the data collection path
            && ab == 1
            && bc == 1)
        {
            // extend the segment
            currentSegment.Add(b.DataPoint);
        }
        else if (
        // if we have a segment collected
            currentSegment.Count > 0
        // and we changed directions away from one of the points
            && (inflectStart == -1
                || inflectEnd == -1
        // or we lost data continuity
                || ab > 1
                || bc > 1))
        {
            // clip the segment and start a new one
            set.Add(currentSegment);
            currentSegment = new List<LatLngPoint>();
        }
    }
    return set;
}

これは、ドライバーに毎時 15 マイル (約 15 マイル) でターンするようにアドバイスし始めるまではうまく機能していました (おそらく、これはセンサーのエラーを減らすのに役立ちます。個人的には、高速で見られるのがエラーであると完全に確信しているわけではありませんが、おそらくそうするつもりはありません)。その議論に勝つ）。時速 15 マイルで走行する車は 22 fps で走行しています。このデータを 5 Hz でサンプリングすると、各データ ポイントが約 4.5 フィート離れていることになります。ただし、当社の GPS ユニットの精度は約 5 フィートです。そのため、GPS データ自体のジッタだけでも、このような低速で高いサンプル レートでデータに変曲点が生じる可能性があります (技術的には、このサンプル レートでは、この問題を回避するには少なくとも時速 35 マイルを超える必要がありますが、実際には時速 25 マイルで問題なく動作するようです)。

また、近いうちにサンプリング レートを 10 ～ 15 Hz に上げる予定です。関心のある曲線のほとんどで安全ではない、私の屈折の問題を回避するには、約 45MPH で運転する必要があります。私の現在の手順では、データを数十のサブセグメントに分割することになり、パスが 4 つしかないことがわかっている道路セクションに分割されます。300 のデータ ポイントしかない 1 つのセクションは、 35 のサブセグメントになりました。各パスの開始と終了の表示 (小さなアイコン) のレンダリングは、各実際のパスがいくつかの断片に切り刻まれていることを非常に明確に示していました。

行きたいと思っている場所

  1. すべての点から始点と終点の両方のクリック ポイントまでの最小距離を見つける
  2. その距離から +10 フィート以内にあるすべての点を見つけます。
  3. データの連続性によってポイントの各セットをグループ化します。つまり、各グループはデータベース内で連続している必要があります。これは、特定のパス上の複数のポイントが距離半径内に収まる可能性があるためです。
  4. 各パスの代表的な開始点と終了点として、各クリック ポイントの各グループのデータ中間点を取得します。
  5. 各「始点」と「終点」の間のレコード インデックスの距離を最小化するものによって、クリック ポイントごとに 2 つのセットのポイントをペアにします。

ハーフ？！

しかし、私はこれを以前に一度試したことがあり、うまく機能しませんでした。ステップ 2 では、ユーザーが特に意図した場所の近くをクリックしないと、不当に多くのポイントが返される可能性があります。ユーザーが非常にクリックした場合、特に意図した場所の近くでクリックした場合、返されるポイントが少なすぎる可能性があります。ステップ 3 の計算負荷がどの程度になるかはわかりません。また、ドライバーが特に長いカーブを運転し、開始と終了の直後に引き返して後続のパスを実行した場合、ステップ 5 は失敗します。そうならないようにドライバーを訓練することはできるかもしれませんが、私はそのようなことに賭けるのは好きではありません。そのため、このパスをクリップしてグループ化し、曲線上のパスのサブセグメントに戻す方法を理解する助けを借りることができます。

4

1 に答える 1

1

さて、これが私がやったことです。今のところうまくいくようです。以前よりも少し簡単にフォローできるようになったことが気に入っています。私の質問のステップ 4 は必要ないと判断しました。始点と終点として使用される正確なポイントは重要ではないため、最初のクリック ポイントの希望の半径内にある最初のポイントと、2 番目のポイントの希望の半径内にある最後のポイントを取得し、中間にあるすべてのポイントを取得します。 .

protected static List<List<T>> GroupCurveSegments<T>(List<T> dbpoints, LatLngPoint start, LatLngPoint end) where T : BBIDataPoint
{
    var withDistances = dbpoints.Select(p => new
    {
        ToStart = p.Distance(start),
        ToEnd = p.Distance(end),
        DataPoint = p
    }).ToArray();
    var minToStart = withDistances.Min(p => p.ToStart) + 10;
    var minToEnd = withDistances.Min(p => p.ToEnd) + 10;
    bool startFound = false, 
        endFound = false, 
        oldStartFound = false, 
        oldEndFound = false;

    var set = new List<List<T>>();
    var cur = new List<T>();
    foreach(var a in withDistances)
    {
        // save the previous values, because they
        // impact the future values.
        oldStartFound = startFound;
        oldEndFound = endFound;

        startFound =
            !oldStartFound && a.ToStart <= minToStart
            || oldStartFound && !oldEndFound
            || oldStartFound && oldEndFound
                && (a.ToStart <= minToStart || a.ToEnd <= minToEnd);

        endFound =
            !oldEndFound && a.ToEnd <= minToEnd
            || !oldStartFound && oldEndFound
            || oldStartFound && oldEndFound 
                && (a.ToStart <= minToStart || a.ToEnd <= minToEnd);

        if (startFound || endFound)
        {
            cur.Add(a.DataPoint);
        }
        else if (cur.Count > 0)
        {
            set.Add(cur);
            cur = new List<T>();
        }
    }

    // if a data stream ended near the end of the curve,
    // then the loop will not have saved it the pass.
    if (cur.Count > 0)
    {
        cur = new List<T>();
    }
    return set;
}
于 2013-09-06T02:16:48.133 に答える