-1

ソートする必要があるパスのエッジを形成する座標のリストがあります。グラハムスキャンを使用しようとしており、次のサンプルをいくつか試しました。

  1. GrhamsScan.cs
  2. ConvexHull.cs
  3. 凸包アルゴリズム

これらのコードは、私が持っているいくつかのテスト ケースで失敗し、何が問題なのかわかりません。

編集：

これらの座標は、接線の一部であると想定されています。座標がソートされていない場合、接線は、嵐が進行するにつれて直線または曲線になる可能性のある適切なパスではなく、危険にさらされます。

嵐の進路を形成する円の接線を作成しています。例を次に示します。 ここに画像の説明を入力

編集#02

接線を形成する点が整っている場合、正しい形状 (最後の半円は無視してください) は次のようになります。

ここに画像の説明を入力

テストケース:

テストケース#01

[0]: {X = 11.581625 Y = -110.983437}
[1]: {X = 11.1816254 Y = -108.983437}
[2]: {X = 11.88781 Y = -113.115852}
[3]: {X = 11.587204 Y = -111.015938}
[4]: {X = 12.1884336 Y = -115.215759}
[5]: {X = 11.88781 Y = -113.115845}
[6]: {X = 12.5794077 Y = -116.863365}
[7]: {X = 12.1794081 Y = -115.163368}
[8]: {X = 13.0785418 Y = -118.855026}
[9]: {X = 12.5785418 Y = -116.855026}
[10]: {X = 13.534234 Y = -119.732178}
[11]: {X = 13.034234 Y = -118.732178}

テストケース#02

   [0]: {X = 10.4182844 Y = -111.21611}
[1]: {X = 10.0190592 Y = -109.21595}
[2]: {X = 10.712142 Y = -113.283806}
[3]: {X = 10.4127483 Y = -111.183716}
[4]: {X = 11.0115175 Y = -115.383896}
[5]: {X = 10.712141 Y = -113.2838}
[6]: {X = 11.4204569 Y = -117.136063}
[7]: {X = 11.0213022 Y = -115.435867}
[8]: {X = 11.9213 Y = -119.144341}
[9]: {X = 11.4223957 Y = -117.144066}
[10]: {X = 12.4652023 Y = -120.266693}
[11]: {X = 11.9662571 Y = -119.266167}

テストケース#03

   [0]: {X = 10.6 Y = -109.1}
    [1]: {X = 11.0 Y = -111.1}
    [2]: {X = 11.3 Y = -113.2}
    [3]: {X = 11.6 Y = -115.3}
    [4]: {X = 12.0 Y = -117.0}
    [5]: {X = 12.5 Y = -119.0}
    [6]: {X = 13.0 Y = -120.0}

浮動小数点座標の信頼できる並べ替えアルゴリズムを見つけることができ、その間に点を削除しないリソース、アルゴリズム、またはコードを親切に案内してください。スピードが優先ではなく、正確さが優先されます。

すべての入力に感謝します。ありがとう

4

2 に答える 2

1

残念ながら、かつて気象データに存在していた時間の目盛りが失われ、ポイントが順不同で到着します。そのため
、一連のポイントからパスを再構築したいと考えています。これが完了すると、この回答は、エンベロープの構築は問題にならないと考えています。

N点あればN点！可能な注文。

これらの順序付けの中から、嵐の軌跡を表す可能性を最大にするものを選択する必要があります。

単純な基準は、パスの長さを最小限に抑えることです。より高度なものは、嵐の速度が即座に変化しないことを考慮に入れることができるため、多かれ少なかれ加速にペナルティを課す. または加速度の導関数...しかし、これには、時間サンプリングの規則性に関する追加の仮説が必要になる場合があります。

どのような場合でも、嵐の軌道がどのように見えるかのモデルを注入し、ある種のスコア (確率) をさまざまな仮説 (可能な軌道) に関連付ける必要があります。

ポイントのセットが非常に小さい場合を除き、組み合わせ全体を反復することはありません。代わりに、任意の 1 点から始まる軌跡を再構築します。次に、ポイントを繰り返し追加することにより、どちらか一方の側で軌道を拡張しようとします。最も可能性の高い候補の削減されたセットを先験的に選択します (これまでに再構成された軌道の最後の点に最も近い点、または一定速度または一定加速度仮説を使用して既に再構成された軌道の外挿に最も近いなど)。

自明なアルゴリズムは、各ステップでローカルで最も可能性の高い候補を選択します。

より深刻なアルゴリズムは、いくつかの可能な軌道を並行して再構築し、いくつかの確率的選択規則に従って最も可能性の低いものを排除します。

このカテゴリの問題は、レーダーを使用したターゲットの追跡に密接に関連していることがわかります。そのため、そのような文献を見て、特にベイジアン アンサンブル確率に関心があるかもしれません。あなたが数学を好きになることを願っています。

于 2015-01-13T23:46:22.473 に答える
0

これは私が書いたもので、最終的にすべてのケースで機能しました。パフォーマンスを向上させることができることを認めさせてください。これは迅速で汚い方法かもしれませんが、これは私が現在使用しているものです。

PS: また、「Convex Hull」または「Graham Scan」が必要なものではなく、必要なものとは何の関係もないことも認めます。技術的には、それは私の側のせいでした。@クリスが提案したように、最初に最も近いポイントでポイントをソートする必要がありました。

public class ConvexHull6
{

    public class PointDistance
    {
        public double X { get; set; }
        public double Y { get; set; }
        public double distance { get; set; }
        public int index { get; set; }
    }
    public class StormPointsDistance
    {
        public StormPoints stormPoints { get; set; }
        public Double distance { get; set; }
    }
    public static List<PointD> ReOrderPointsByClosestPointFirst(List<PointD> points, bool islower = false)
    {
        var minX = points.Min(p => p.X);
        var maxX = points.Max(p => p.X);
        var minP = points.First(p => p.X == minX);
        var maxP = points.First(p => p.X == maxX);

        minP = points.First(p => p.X == minX);
        maxP = points.First(p => p.X == maxX);

        var pB = points.ToList();
        var len = pB.Count();
        //Temporary lists to hold data structures and points when performing the points sorting..
        var pDist = new List<PointDistance>();
        var distances = new List<Double>();
        int index = 0;
        //Sorted list to hold final points...
        var sorted = new List<PointD>();
        for (int i = 0; i < len; i++)
        {
            if (i > 0)
            {
                //Minimum point or "Point of Reference for comparison" is now the last point in the sorted list.
                minP = sorted[sorted.Count() - 1];
                //Clear the temporary lists used...
                pDist.Clear(); distances.Clear();
            }
            for (int j = 0; j < len - i; j++)
            {
                var distance = Math.Sqrt(Math.Pow(pB[j].X - minP.X, 2) + Math.Pow(pB[j].Y - minP.Y, 2));
                pDist.Add(new PointDistance() { X = pB[j].X, Y = pB[j].Y, distance = distance, index = index });
                distances.Add(distance);
            }
            //Order the data structure
            pDist = pDist.OrderBy(m => m.distance).ToList();
            //Convert to points list for use
            pB = pDist.Select(m => new PointD(m.X, m.Y)).ToList();
            //Get the first point and put it in the sorted list
            sorted.Add(pB[0]);
            //Remove the point from the pb list so that it is not considered again
            pB.RemoveAt(0);

            index++;
        }
        pDist = pDist.OrderBy(m => m.distance).ToList();
        distances = pDist.Select(m => m.distance).ToList();

        //The new code...
        points = sorted.ToList();

        //Get the minimum Point again as minP has been overwritten during the loop
        minX = points.Min(p => p.X);
        maxX = points.Max(p => p.X);
        minP = points.First(p => p.X == minX);
        maxP = points.First(p => p.X == maxX);
        //Check if minp does nott match the first point
        if ((minP != points[0] && maxP == points[0]) || (maxP != points[len - 1] && minP == points[len - 1]))
        {
            //Reverse only if the first point of array is not the minimum point
            points.Reverse();
        }
        return points;
    }

}
于 2015-01-26T11:17:50.107 に答える