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

Question

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

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

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

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

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); 
} 

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

Прошедшее время: 701ms. (0.701us за одну итерацию)

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

return ... ? true : false; 

является излишним, так как выражение уже «истина» или «ложь». При попытке сделать ультраэффективный код я всегда думаю о выполненных операциях ...

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

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