Прямоугольники проверки попадания

Я бы не стал сильно беспокоиться о производительности, пока не станет ясно, что фрагмент кода создает настоящее узкое место. Предположим, что у вас есть такое узкое место, и измерим производительность следующего кода (он на 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);
}

На моем ПК напечатан приведенный выше код:

Затраченное время: 701 мс. (0,701 мкс за одну итерацию)

Как видите, проверка 50 прямоугольников занимает менее одной микросекунды. Вы действительно думаете, что это слишком долго по сравнению со временем, необходимым для создания причудливых эффектов наведения и всего остального, что делает ваша программа? Конечно, только вы можете ответить на этот вопрос.

Но мораль моей истории такова: не пытайтесь выполнить предварительную оптимизацию и не тратьте время на попытки решить проблему, которая может не существовать вовсе.

Не думайте о производительности. Если да, то измерьте!

События мыши - это события очень низкого уровня, они действительно быстрые. Windows помещает сообщения мыши в очередь, и ваше приложение либо читает, либо игнорирует их. В обработчике событий мыши проверка того, в каком прямоугольнике находится мышь, является быстрой операцией.

Если ваши «прямоугольники» представляют собой элементы управления Windows (а они должны), вы можете установить прослушиватель мыши для каждого элемента управления, чтобы правый обработчик автоматически вызывался окнами.

Я согласен с тем, что для небольшого количества прямоугольников (например, пятидесяти) очевидный подход к тестированию каждого по очереди, вероятно, будет самым быстрым.

Я предполагаю, что Windows делает то же самое. Очевидно, что не нужно тестировать дочерние окна, если указатель мыши не находится в родительском, и даже в самых плохо спроектированных диалогах редко отображается более сотни элементов управления одновременно. Элементы управления, которые имеют множество областей проверки попадания (например, ListView, сетки), оптимизируют собственное тестирование попадания.

Если у вас есть десятки тысяч прямоугольников, производительность может быть проблемой, и вы можете использовать один из методов, описанных здесь.

Другие вопросы здесь не ответили на вашу часть 2, поэтому я попробую:

2. How does windows do this? (I'm more curious then anything, but if it's not to complex, maybe I could implement something similar in my own program?)

Следует понимать, что даже если у вас открыты десятки окон, в каждом из которых много панелей инструментов, в каждой много элементов и т. Д., Каждый раз, когда вы перемещаете мышь, окнам не нужно проверять все < / em>.