1

現在の状況に応じてaCircleから aを取得する必要がありますList<Circle>MousePosition

サークルクラスです

public class Circle
        {
            public Point Center;

            public Circle(int x, int y)
            {
                this.Center = new Point(x, y);

            }
            public int Distance(int x, int y)
            {
                int result = 0;
                double part1 = Math.Pow((this.Center.X - x), 2);
                double part2 = Math.Pow((this.Center.Y - y), 2);
                double underRadical = part1 + part2;
                result = (int)Math.Sqrt(underRadical);
                return result;
            }
            public void Draw(Graphics g, Pen pen, int d)
            {
                g.DrawEllipse(pen, this.Center.X - d / 2, this.Center.Y - d/ 2, d, d );
            }
    }

リストからサークルを取得する方法は次のとおりです

public class UserControl1 : UserControl
{
private Circle currentCircle;
private List<Circle> circles = new List<Circle>();
private const int RADIUS = 16;
// ...snip
private void Form1_MouseMove(object sender, MouseEventArgs e)
        {
            currentCircle= this.circles 
                .Where(c => c.Distance(e.X, e.Y) < RADIUS )
                .DefaultIfEmpty(null)
                .First();
        }
//...snip
}

これは小さなリストでは問題なく機能しますが、リストが大きくなるにつれて遅くなります。List.BinarySearch を使用してパフォーマンスを向上させることができると思いますがIComparable、このシナリオで実装する方法がわかりませんでした。

4

5 に答える 5

3

1 つの観察 -時間を節約するためにMath.Powandをキャンセルできます。Math.Sqrt計算された距離は「距離の二乗」になりますが、すべての円が同じスケーリングを受けるため、問題にはなりません。

ただし、検索されるアイテムの数が、一致を見つけるのにかかる時間に直接影響しないソリューションが必要です。

そのため、大量の次元データに対して高速なパフォーマンスを提供する KD ツリーを検討することをお勧めします。このページ (KDTreeDLL.zip) にリンクされている Marco A. Alvarezによって書かれたソースから完全な汎用 KD ツリーを採用しました。ただし、より良く、より一般的であるように見えるこれがあります。残念ながら、私のコードを提供することはできません - それは私の雇用主が所有しています ;)

KD ツリーにデータを取得したら、現在の X、Y (KD ツリーへの単一呼び出し) に最も近い円を探し、ポインタがその中にあるかどうかを確認します。それがあなたが探しているものです。

構造は事実上、各レベルの左/右の値が連続する次元の「分割平面」の上/下にあり、子ノードがなくなるまでラップアラウンドする二分木です。データが保存される方法のため、近接検索は高速です。なぜなら、近い隣人が見つかると、同じ分割平面の周りの他の隣人だけがより近くなる可能性があるためです (それよりも少し微妙で、実際には数学よりも上位のクラスです)。私ができること）。その結果、アルゴリズムがすべてのノードを調べて最も近い一致を見つける必要はほとんどありません。ただし、すべてのノードを検索する必要があるシナリオもあります。これは、他の何よりもデータを挿入する順序に依存します。

したがって; 円の数が非常に多い場合は、「バランスのとれた挿入」が必要になる場合があります (これについては、ウィキペディアの KD Trees エントリの「構築」サブトピックに適切な説明があります)。私がリンクしたコードは、それを構築するためのポイントのリストがあると仮定すると、何らかの形式のバランスの取れた挿入を行うように見えるので、問題ないようです.

また、距離を測定する際のデフォルトの動作はユークリッド距離であるように見えますが、これはまさにあなたが望むものです。

パフォーマンスの大まかな考えとして (これは常に主観的な尺度です)、現在マップ上のポイントの Haversine 距離計算をプラグインしている私の適応 KD ツリーは、250,000 から最も近い緯度/経度を見つけるのに約 250 ～ 350 ミリ秒かかります。ユークリッド距離の計算はかなり高速になる可能性があります。

于 2012-09-10T12:57:11.857 に答える
1

バイナリ検索は、ソートされたリストでのみ機能します。したがってCircle、ソートされたリストを取得するには、オブジェクトを比較できる必要があります。ただし、マウスカーソルの位置との「衝突」をより速く見つけるために、それらを合理的な線形順序で配置することはできません。

AsParallelLINQクエリで使用して、すべてのCPUコアを比較に使用できます。これはまだ、したがってあまりうまくスケーリングしませんが、おそらく少しスピードアップします（オブジェクトO(n)の数がほとんど増えていない場合）。Circle

于 2012-09-10T11:52:22.317 に答える
0

マウス入力用のイベントハンドラーを登録するだけではどうですか？これをテストし、112X116でラグはありません。

    public MainWindow()
    {

        InitializeComponent();

        for (int j = 0; j < 112; j++)
        {
            for (int i = 0; i < 116; i++)
            {
                ellipse = new Ellipse();
                ellipse.Name = "EllipseX" + i.ToString() + "Y" + j.ToString();
                ellipse.StrokeThickness = 1;
                ellipse.Stroke = System.Windows.Media.Brushes.Blue;
                ellipse.Width = 5;
                ellipse.Height = 5;
                ellipse.MouseEnter += ellipse_MouseEnter;
                ellipse.MouseLeave += ellipse_MouseLeave;

                Canvas.SetTop(ellipse, 5 * j);
                Canvas.SetLeft(ellipse, 5 * i);
                Canvas1.Children.Add(ellipse);
            }
        }
    }

    private void ellipse_MouseEnter(object sender, MouseEventArgs e)
    {
        Ellipse ellipse = (Ellipse)sender;
        ellipse.Fill = System.Windows.Media.Brushes.Red;
        tbEname.Text = ellipse.Name;
    }

    private void ellipse_MouseLeave(object sender, MouseEventArgs e)
    {
        ((Ellipse)sender).Fill = System.Windows.Media.Brushes.Blue;
        tbEname.Text = string.Empty;
    }
于 2012-09-10T18:58:48.017 に答える
0

比較を円に移動して、いくつかのショートカットを実行できるようにします. そして、より速い数学を使用してください。円は重ならないと思います。最悪の場合 (多くても) 4 つのボックスに点が含まれるため、複雑な方程式は多くても 4 回評価されます。

public bool Distance(double x, double y, double radius)
{
    double deltaX = this.Center.X - x;
    if (deltaX > radius) return false;   // test to see if this makes it faster
    double deltaY = this.Center.Y - y;
    if (deltaY > radius) return false;
    if ( (deltaX + deltaY) > radius) return false;   
    return ( (deltaX*deltaX + deltaY*deltaY) <= radius*radius) );
}

他のコメントや回答に記載されているように、FirstOrDefault および Parallel と組み合わせます。

于 2012-09-10T12:49:15.147 に答える
-1

HashSet<Circle>の代わりに使用してみてくださいList<Circle>。データサイズが大きくなるにつれてパフォーマンスが向上するようになります-HashSetとListのパフォーマンス

于 2012-09-10T11:52:14.857 に答える