1

我必须Circle从 a 中获取 aList<Circle>取决于当前MousePosition

这是Circle类

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

一项观察 - 您可以取消Math.PowandMath.Sqrt以节省时间。计算出的距离变为“距离平方”，但由于所有圆圈都经过相同的缩放，所以没关系。

但是，您需要一个解决方案，其中正在搜索的项目数量不会直接影响找到匹配项所花费的时间。

所以我想你可能想看看 KD 树，它为大量维度数据提供了快速的性能。我已经从 Marco A. Alvarez 编写的源代码中改编了一个完整的通用 KD 树，链接到此页面 (KDTreeDLL.zip)；但是，有一个似乎更好，更通用。不幸的是，我无法提供我的代码 - 它归我的雇主所有；）

在 KD 树中获取数据后，您只需查找与当前 X、Y 最近的圆（这是对 KD 树的一次调用），然后检查指针是否在其中，如果这就是你要找的。

该结构实际​​上是一个二叉树，每个级别的左/右值在连续维度上的“分割平面”之上/之下，环绕直到没有子节点。由于数据的存储方式，邻近搜索很快，因为当找到近邻时，只有同一分割平面周围的其他邻居才能更近（它比这更微妙，实际上是更高级别的数学比我有能力的）。因此，该算法很少需要检查所有节点以找到最接近的匹配。尽管如此，在某些情况下可能需要搜索所有节点。这与您插入数据的顺序一样多。

因此; 非常多的圆圈可能需要“平衡插入”（在KD Trees 的维基百科条目的“构造”子主题中有很好的描述）。无论如何，我链接到的代码似乎都做了某种形式的平衡插入，假设你有一个点列表来构建它 - 所以看起来你会没事的。

看起来它测量距离的默认行为是欧几里得距离，这正是您想要的。

作为性能的粗略概念（这始终是一个主观衡量标准），我适应的 KD 树，我目前将地图上点的 Haversine 距离计算插入其中，大约需要 250-350 毫秒才能找到 250,000 中最近的纬度/经度。欧几里得距离计算可能会快很多。

于 2012-09-10T12:57:11.857 回答
1

二进制搜索仅适用于排序列表。因此，您的Circle对象需要具有可比性才能获得排序列表。不过，恐怕您无法将它们以合理的线性顺序排列，以更快地找到与鼠标光标位置的“碰撞”。

您可以AsParallel在 LINQ 查询中使用所有 CPU 内核进行比较。这仍然存在O(n)，因此不能很好地扩展，但它可能会加快速度（考虑到Circle对象的数量几乎没有增长）。

于 2012-09-10T11:52:22.317 回答
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 回答
0

为鼠标输入注册一个事件处理程序怎么样？对此进行了测试，并且在 112 X 116 时没有延迟。

    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 回答
-1

尝试使用HashSet<Circle>而不是List<Circle>. 随着数据大小的增长，它似乎有更好的性能 - HashSet 与 List 性能

于 2012-09-10T11:52:14.857 回答