c ++ - Hit test rektangler

Indlæg af Hanne Mølgaard Plasc

Problem



Jeg arbejder på et projekt, hvor jeg har flere rektangler, og jeg vil have en svær effekt for hver enkelt. Nu ved jeg, at jeg bare kunne fange WM\_MOUSEMOVE beskeden og gentage gennem hvert rektangel. Men hvad nu hvis Jeg har mange rektangler (hvis 50 er meget).

Jeg kan måske være forkert, men ville ikke gennemføre det mange og slå test hver enkelt gang musen bevæger langsomt applikationen lidt ned?


Så begyndte jeg at spekulere på, hvordan et operativsystem (som Windows) gør dette, der er ligesom 100 + ting på min skærm lige nu, at alle har en slags animation, når jeg svæver over dem. Og jeg tror ikke, at vinduer gentager sig gennem alle dem hver gang musen bevæger en pixel.


Dybest set:

1. Hvordan kan jeg finde ud af, hvilket rektangel min mus er forbi, hvis jeg har omkring 50 rektangler, med ydeevne i tankerne
2. Hvordan gør windows dette? (Jeg er mere nysgerrig end noget, men hvis det ikke er kompliceret, kan jeg måske implementere noget lignende i mit eget program?)


Åh, og de 'er alle rektangler, de vundet 't blive roteret eller noget.

Bedste reference


Jeg ville ikke være generet meget om ydeevne, før det bliver klart, at et stykke kode skaber en reel flaskehals. Lad os antage, at du har en sådan flaskehals og måle udførelsen af ​​følgende kode (den er i C # , men jeg er ret sikker på at C ++ ikke vil være langsommere):


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


Vi er interesserede i at udføre HitTest() metoden, så lad os måle det!


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


På min pc udskriver ovennævnte kode:



  Forløbet tid: 701ms. (0,701us pr en iteration)



Som du kan se tager det mindre end en mikrosekund for at ramme test 50 rektangler. Tror du virkelig, at dette er for langt i forhold til den tid det tager at skabe fancy hovereffekter, og hvad ellers dit program gør? Kun du kan selvfølgelig svare på dette spørgsmål.


Men moralen i min historie er: Prøv ikke at optimere og ikke bruge tid på at forsøge at løse et problem, som måske slet ikke eksisterer.

Andre referencer 1


Tænk ikke på ydeevne.
Hvis du gør det, må du måle det!


Musen begivenheder er meget lavt niveau begivenheder, det er hurtigt, virkelig.
Windows lægger musebeskeder i kø, og din ansøgning læser eller ignorerer dem. I din mushændelseshåndterer, ved at tjekke hvilket rektangel er musen, er en hurtig betjening.


Hvis dine 'rektangler' er Windows-kontroller (og de burde), så kan du indstille en muselytter til hver kontrol, så den højre håndterer automatisk bliver kaldt af Windows.

Andre referencer 2


Jeg er enig i, at for et lille antal rektangler (fx halvtreds) er den indlysende tilgang til at teste hver enkelt til gengæld sandsynligvis hurtigst.


Jeg vil gætte, at Windows gør det meget det samme. Det er selvfølgelig ikke nødvendigt at teste børnevinduer, medmindre musemarkøren er i forældrene, og selv de mest dårligt udformede dialoger har sjældent mere end hundrede kontroller synlige på en gang. Kontroller, der har mange strejktestregioner (f.eks. ListViews , grids) optimere deres egen hit-test.


Hvis du havde titusindvis af rektangler, kan performance være et problem, og du kan bruge en af ​​metoderne beskrevet her.

Andre referencer 3


De andre spørgsmål her svarede ikke på din del 2, så jeg vil give det et skud:



2. Hvordan gør windows dette? (Jeg er mere nysgerrig end noget, men hvis det ikke er kompliceret, kan jeg måske implementere noget lignende i mit eget program?)


Det er vigtigt at indse, at selvom du har mange vinduer åbne, hver med mange værktøjslinjer, hver med mange elementer i den osv., Hver gang du flytter musen, behøver Windows ikke at tjekke alt .


Windows er grundlæggende struktureret i to lag: der er HWND'er, hvilket er, hvordan Windows selv styrer underinddeling af plads på skrivebordet, og typisk inden for hver HWND er en kontrol, der styrer sin egen plads i den HWND: en listeboks, der forvalter sin egen liste elementer, en fanekontrol, der administrerer sine egne faner, en HTML-kontrol, der forvalter sit eget HTML-sidelayout osv. (Eller i din egen kode kode for at styre 50 eller så rektangler.)


Når musen bevæger sig, bestemmer Windows først den korrekte HWND for at sende den WM\_MOUSEMOVE til. Og det gør det ved at krydse HWND'erne. HWND'erne gemmes som et træ, der repræsenterer indeslutning, og rækkefølgen blandt søskende repræsenterer Z-Order, så Windows kan gøre en simpel dybde-første nedstigning i dette træ for at finde ud af den nederste HWND på et givet punkt. Hvis du starter Spy ++ app, kan du se selv, hvad dette HWND-træ ligner. Bemærk, at Windows ikke gør en fuld udtømmende gennemgang: Når du f.eks. Går gennem de øverste applikationsvinduer, for eksempel at finde ud af, hvilken app pointet er i, så snart Windows finder den første top-level HWND, der indeholder punktet, er det vil bore ind i det, uden at ignorere alle andre apps, der er under/efter det - og alle kontroller i dem. Dette er nøglen, der betyder, at Windows kun skal krydse relativt få HWND'er, selvom der er mange mange synlige på skærmen på én gang.


Når Windows har bestemt den korrekte HWND, sender den den rigtige besked til den (WM\_NCHITTEST, WM\_MOUSEMOVE osv.), Og det er så op til den kontrol at gøre ligeledes for sit eget indhold. For en listeboks, der indeholder genstande i fast størrelse , at bestemme emnet på et bestemt tidspunkt kan være så simpelt som en division operation, eller for en HTML-kontrol, kan kontrollen have sit eget ækvivalent med et 'layouttræ', som det kan bruge til at krydse og hurtigt bestemme elementet på det tidspunkt . I dit tilfælde kan looping gennem listen af ​​rektangler være helt fint.


Det er den noget forenklede version: den er lidt mere kompleks end ovenfor - f.eks. windows gør det ikke bare til en punkt-i-rekt check, er der andre kontroller, der giver mulighed for ulige og gennemsigtige vinduer (og usynlige og deaktiverede vinduer); men den grundlæggende træ nedstigning ideen gælder.


Det andet vigtige spørgsmål at huske er, at alt dette er ret hurtigt: at flytte en mus foregår i 'menneskelig tid', og en moderne CPU kan til en masse operationer i den tid det tager med musen at flytte et par pixels på skærm. Og endelig bemærk, at når du bevæger musen fra punkt A til punkt B på skærmen, går musen ikke over hver eneste pixel imellem - især hvis du flytter musen hurtigt.

Andre referencer 4


Jeg tror, ​​du har en helt unødvendig 'gren' i svaret (som i din test resulterer i en ekstra million operationer). I din 'HitTest' slutter du med:


return ... ? true : false;


'True: false' er overflødig, da udtrykket allerede er 'sandt' eller 'false'. Når jeg forsøger at lave ultra-effektiv kode, tænker jeg altid på 'operationer' udført ...


PS: også ting som ++ var, versus var ++ kan have en værdig indvirkning på ydeevnen afhængigt af hvordan det er brugt i koden (som optimeringsoptagere fanger nogle af dem og retter det til dig ...


PPS: Mens jeg 'm ved det' heller aldrig sætter et udtryk eller en metodeopkald i dine sløjfer, medmindre sløjfen ændrer udtrykket, fx: for (int i=0; i < getWidth (); ++ i). .. hvis dette loopede en million gange, din metode ville blive kaldt en million gange :)