Ich habe ein Bild und möchte QuickInfos anzeigen, wenn sich die Maus über bestimmte rechteckige Bereiche bewegt. Die rechteckigen Bereiche können bis zu 1000 sein. Wenn Sie jedoch jedes Rechteck überprüfen, wenn sich der Punkt darin befindet, also O (N), reagiert die Schnittstelle nicht mehr, wenn Sie die Maus bewegen.
Gibt es eine Möglichkeit, es in weniger als O (N) zu machen? Ich kann die Rechtecke vorher sortieren (ich nehme an, dass es nötig wäre). Die Rechtecke können sich (sehr selten) überlappen, aber nicht mehr als 4-5 Rechtecke können dieselbe Fläche überlappen. In diesem Fall müsste ich vielleicht eine Liste aller Rechtecke erhalten, aber auch nur eine davon wäre immer noch gut genug.
Aber ich gehe davon aus, dass dieses Problem bereits von Window Managern etc. gelöst wurde.
Es klingt, als ob Sie Ihre Rechtecke in einem R-Tree speichern und danach fragen möchten. Es sind einige Implementierungen verfügbar:
Schau dir ihre STRtree-Klassen an.
Eine schnellere und einfachere (wenn auch weniger speichereffiziente) Methode als eine Struktur für Bilder (und Webseiten, die auf relativ kleinen Bildern gerendert werden können) ist die Verwendung einer Schablone. Wenn Sie beispielsweise ein Bild x x y Pixel haben, erstellen Sie ein zweidimensionales Array der Größe x x und füllen Sie es mit Ihren QuickInfo-IDs. Dies hat eine Suchgeschwindigkeit von Pixelposition zu ID von O (1) (mein Lieblings-O)
Wenn das Rechteck achsversetzt ist, können Sie spezielle Datenstrukturen vermeiden.
Unterteile zuerst den Raum in einer Dimension, z. Unterteilung des Bildschirms horizontal in vertikale Streifen. Jedes Rechteck kann aus mehreren Streifen bestehen. Dann unterteilen Sie jeden Streifen abhängig von den Rechtecken, die diesen Streifen überlappen. Die Suche umfasst dann zwei O (log n) -Suchen oder binäre Bäume - einen zur Identifizierung des Streifens, einen zur Identifizierung des Rechtecks.
Diese ist eine anerkannte räumliche Datenstruktur, aber für mich zählt sie nicht wirklich - sie verwendet nur normale Binärbäume. Du könntest es sogar mit einem std::map<int, std::map<int, int>> machen.
Aber es gibt tatsächlich eine Option, die O (1) -Suchen unterstützt, die "Pixel-Picking" genannt wird. Zeichnen Sie die Rechtecke grundsätzlich in einer Offscreen-Bitmap, jedes Rechteck in einer anderen Farbe und die vordersten Rechtecke wie beim normalen Zeichnen (Malers-Algorithmus). Sie können an jedem Punkt erkennen, welches Rechteck am weitesten vorne liegt, indem Sie einfach dieses Pixel lesen.
Extra-Bonus - Ihre Grafikkarte kann sogar das Zeichnen der Rechtecke beschleunigen, so dass Sie sich nicht zu viele Gedanken über das Neuzeichnen machen müssen, wenn sich die Menge der Rechtecke ändert (was offensichtlich nicht in diesem O (1) enthalten ist). Es ist ein bisschen teuer im Gedächtnis, aber auf einer modernen Maschine interessiert Sie das vielleicht nicht.
Verwenden Sie eine räumliche Suchdatenstruktur wie die Quad-Struktur .
Sie müssen Ihre Rechtecke vorher zum Baum hinzufügen, aber die durchschnittliche Suche wird schnell sein. Im schlimmsten Fall haben Sie vielleicht noch O (N).