命中测试矩形

我正在研究一个项目，其中有几个矩形，我想为每个矩形都设置一个悬停效果。现在我知道我可以捕获消息WM_MOUSEMOVE，并遍历每个矩形。但是如果我有很多矩形（如果50很多）。
我可能是错的，但不会迭代那么多，并且每次鼠标移动都会减慢应用程序的运行速度，就会对每一个进行测试。命中测试矩形

然后我就开始琢磨一个操作系统（如Windows），如何做到这一点，有没有像100+我的屏幕上的东西，现在，所有的都有某种动画，当我将鼠标悬停在他们。我不认为每次鼠标移动一个像素时，Windows都会遍历它们。

基本上：
1.如果我有大约50个长方形，并考虑到性能，我怎样才能确定鼠标的哪个矩形已经结束。
2. Windows如何做到这一点？（我对任何事情都比较好奇，但是如果不是很复杂，也许我可以在自己的程序中实现类似的东西？）

哦，它们都是矩形，它们不会被旋转或任何东西。

来源

2012-03-02 Josh

使用PtInRect该函数。如果存在效率问题，请进行配置并进行更改。 – 2012-03-02 15:53:00

，直到它变得清晰，一段代码创建了一个真正的瓶颈，我不会被人打扰太多关于性能。让我们假设你有这样的瓶颈，并测量以下代码的性能（这是在C＃中，但我敢肯定，C++不会慢）：

public class Rectangle 
{ 
    public int X { get; set; } 
    public int Y { get; set; } 
    public int W { get; set; } 
    public int H { get; set; } 

    public bool HitTest(int x, int y) 
    { 
     return x >= X && x < X + W && y >= Y && y < Y + H ? true : false; 
    } 
}

我们有兴趣性能的HitTest()方法，所以让我们来衡量它！

void PerformanceTest() 
{ 
    const int Iterations = 1000000; 
    Random rnd = new Random(); 
    var rectangles = Enumerable.Range(1, 50).Select(
      r => new Rectangle { 
       X = rnd.Next(1000), 
       Y = rnd.Next(1000), 
       W = rnd.Next(1000), 
       H = rnd.Next(1000)}).ToList(); 

    Stopwatch sw = new Stopwatch(); 
    sw.Start(); 
    for (int i = 0; i < Iterations; i++) 
    { 
     rectangles.ForEach(r => r.HitTest(500, 500)); 
    } 
    sw.Stop(); 

    Console.WriteLine("Elapsed time: {0}ms. ({1}us per one iteration)", 
     sw.ElapsedMilliseconds, 
     (float)sw.ElapsedMilliseconds * 1000/Iterations); 
}

在我的电脑上面的代码打印：

执行时间：701ms。（每一次迭代0.701us）

正如你所看到的，它需要不到一微秒的命中测试50米的矩形。你真的觉得这个时间太长了吗？与创建幻想悬停效果的时间相比，你的程序还有其他什么？当然，只有你可以回答这个问题。

但我的故事的寓意是：不要试图预先优化，不花时间试图解决它可能不存在的一个问题。

来源

2012-03-02 15:23:10

不要考虑性能。如果你这样做，然后衡量它！

鼠标事件是非常低级别的事件，它的快速，真的。 Windows将鼠标消息放入队列中，并且您的应用程序读取或忽略它们。在您的鼠标事件处理程序中，检查哪个矩形是鼠标是一种快速操作。

如果你的“矩形”是Windows控件（他们应该），那么你可以设置一个鼠标监听器为每个控件，以便正确的处理程序将被Windows自动被调用。

来源

2012-03-02 14:07:27 vulkanino

我同意对于少数的矩形（例如，50）依次每一个测试的明显的方法很可能是最快的。

我猜想Windows的功能差不多。显然，它不必测试子窗口，除非鼠标指针在父窗口中，甚至最糟糕的设计对话框也很少有一百个控件可以同时显示。有很多命中测试区域的控件（例如ListViews，网格）优化他们自己的命中测试。

如果您有数万个矩形，那么性能可能会成为问题，您可以使用the methods described here之一。

来源

2012-03-03 16:08:37 arx

其他问题，这里没有回答你的第2部分，所以我给一个镜头：

2.如何窗户做到这一点？（我对任何事情都比较好奇，但如果不是很复杂，也许我可以在自己的程序中实现类似的东西）

要实现的是即使你打开几十个窗口，许多工具栏，每个工具栏都有很多项目，等等，每次移动鼠标时，窗口都不需要检查的所有内容。

Windows基本上分为两层：HWNDs，它是Windows本身如何管理桌面空间的细分;并且通常在每个HWND中都有一个控制器，用于管理该HWND中的自己的空间：管理自己的列表项的列表框，管理自己的选项卡的选项卡控件，管理自己的HTML页面布局的HTML控件等等。（或者，在你的情况下，代码管理50左右的矩形。）

当鼠标移动时，Windows首先确定将WM_MOUSEMOVE发送到的正确HWND。它通过遍历HWND来完成。 HWND存储为一棵树，表示包含，以及表示Z顺序的兄弟之间的顺序，因此Windows可以在此树中执行简单的深度优先下降，以找出任意给定点处最底层的HWND。如果你启动Spy ++应用程序，你可以自己看看这个HWND树是什么样的。请注意，Windows并未进行全面的遍历遍历：例如，在遍历顶级应用程序窗口时，一旦Windows找到包含该点的第一个顶层HWND，就会找出该点在哪个应用程序中，将深入研究，彻底忽略所有其他下/后的应用程序 - 以及其中的所有控件。这是一个关键，这意味着即使屏幕上有许多许多可见的信息，windows也只需要遍历相对较少的HWND。

一旦Windows确定了正确的HWND，它就会将相应的消息发送到该消息（WM_NCHITTEST，WM_MOUSEMOVE等），然后由该控件自行处理。对于包含固定尺寸项目的列表框，在特定点确定项目可能与分割操作一样简单;或者对于HTML控件，控件可以有自己的等价物，可以用它来遍历并快速确定该点处的元素。在你的情况下，循环矩形列表可能会非常好。

这是一个稍微简化的版本：它比上面稍微复杂 - 例如。窗口不仅仅是一个点的直接检查，还有其他检查可以用于奇形和透明的窗口（以及不可见和禁用的窗口）;但基本树下降的想法适用。

要记住的另一个重要问题是，所有这些都非常快：移动鼠标发生在“人类时间”，并且现代CPU可以在鼠标移动一对夫妇的时间内进行大量操作屏幕上的像素。最后，请注意，当您将鼠标从A点移动到屏幕上的B点时，鼠标并不总是遍历它们之间的每个像素 - 尤其是当您快速移动鼠标时。

来源

2012-03-04 02:49:45 BrendanMcK

我相信你在答案中有一个完全不必要的'分支'（在你的测试中有一个额外的百万次操作）。在你的“的HitTest”你结束与“？真：假”

return ... ? true : false;

的是多余的，因为表达已经是“真”或“假”。当试图制作超高效的代码时，我总是想到'操作'执行...

PS：类似于++ var和var ++之类的东西可以对性能产生有价值的影响，具体取决于它在代码中的使用方式（如优化赶上他们中的一些，并为您解决问题...

PPS：而我在这......也从来没有把一个表达式或方法调用你的循环，除非循环会改变表达结果，如：的for（int i = 0;我<的getWidth（）; + +1）...如果这个循环一万次，你的方法将被称为万次:)

来源

2012-03-31 14:48:10 Joe

命中测试矩形

回答

相关问题