Хит тест прямоугольников

Question

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

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

В основном:
1. Как я могу определить, над каким прямоугольником у меня находится мышь, если у меня около 50 прямоугольников, с учетом производительности.
2. Как Windows это делает?(Мне более любопытно, чем что-либо, но если это не сложно, может быть, я мог бы реализовать нечто подобное в моей собственной программе?)

О, и все они прямоугольники, они не будут вращаться или что-то еще.

Answer 1

Меня не сильно беспокоит производительность, пока не станет ясно, что кусок кода создает реальное узкое место. Давайте предположим, что у вас есть такое узкое место, и измерим производительность следующего кода (он написан на 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,701us за одну итерацию)

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

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

Answer 2

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

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

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

Answer 3

Я полагаю, у вас есть одна совершенно ненужная «ветвь» в ответе (которая в вашем тесте приводит к дополнительному миллиону операций). В вашем «HitTest» вы заканчиваете:

return ... ? true : false;

«? True: false» является избыточным, поскольку выражение уже «true» или «false». Когда я пытаюсь сделать ультраэффективный код, я всегда думаю о выполненных «операциях» ...

PS: также такие вещи, как ++ var и var ++ могут оказать достойное влияние на производительность в зависимости от того, как он используется в коде (так как оптимизаторы ловят некоторые из них и исправляют это для вас ...

PPS: пока я в этом ... также никогда не помещайте выражение или вызов метода в ваши циклы, если только цикл не изменяет результаты выражения, например: for (int i = 0; i

Answer 4

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

2. Как Windows это делает? (Мне более любопытно, чем что-либо, но если это не так сложно, может быть, я мог бы реализовать нечто подобное в моей собственной программе?)

Необходимо понять, что даже если у вас открыто несколько десятков окон, в каждом из которых много панелей инструментов, в каждом из которых много элементов и т. Д., При каждом перемещении мыши окна не нужно проверять все .

Windows в основном структурирована в два уровня: есть HWNDs, и именно так Windows сама управляет разделением пространства на рабочем столе; и обычно в каждом HWND есть элемент управления, который управляет его собственным пространством в этом HWND: список, управляющий его собственными элементами списка, элемент управления вкладками, управляющий его собственными вкладками, элемент управления HTML, управляющий его собственным макетом страницы HTML, и так далее. (Или, в вашем случае, код, управляющий примерно 50 прямоугольниками.)

Когда мышь перемещается, Windows сначала определяет правильный HWND для отправки этого WM_MOUSEMOVE. И это происходит путем обхода HWND. HWND хранятся в виде дерева, представляющего содержание, и порядка среди братьев и сестер, представляющих Z-порядок, поэтому Windows может выполнить простой спуск на глубину в это дерево, чтобы найти самый нижний HWND в любой заданной точке. Если вы запустите приложение Spy ++, вы сможете увидеть, как выглядит это дерево HWND. Обратите внимание, что Windows не выполняет полный исчерпывающий обход: например, при обходе окон приложений верхнего уровня, чтобы выяснить, в каком приложении находится точка, как только Windows находит первый HWND верхнего уровня, содержащий точку, она подробно расскажет об этом, полностью игнорируя все другие приложения, которые находятся ниже или после него, и все элементы управления внутри них. Это ключ, который означает, что окна должны проходить только относительно немного HWND, даже если на экране видно много разных изображений.

Как только Windows определяет правильный HWND, она отправляет соответствующее сообщение этому (WM_NCHITTEST, WM_MOUSEMOVE и т. Д.), И затем этот элемент управления также должен сделать то же самое для своего собственного контента. Для списка, содержащего элементы фиксированного размера, определение элемента в конкретной точке может быть таким же простым, как операция деления; или для элемента управления HTML элемент управления может иметь собственный эквивалент «дерева макетов», которое он может использовать для быстрого поиска элемента в этой точке. В вашем случае, циклический просмотр списка прямоугольников может быть вполне нормальным.

Это несколько упрощенная версия: она немного сложнее, чем выше - например. окна не просто для проверки «точка-в-прямоугольник», существуют другие проверки, позволяющие создавать нечетные и прозрачные окна (а также невидимые и отключенные окна); но основная идея происхождения дерева применима.

Другая важная проблема, которую следует помнить, заключается в том, что все это довольно быстро: перемещение мыши происходит в «человеческое время», и современный ЦП может выполнять множество операций за то время, которое требуется мыши для перемещения пары. пикселей на экране. И наконец, обратите внимание, что при перемещении мыши из точки A в точку B на экране мышь не всегда пересекает каждый отдельный пиксель между ними - особенно если вы быстро перемещаете мышь.

Answer 5

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

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

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