Berechnung von Rechecken auf Basis von Koordinaten-Vektor

[Gateway_man]

Guten Abend,

ich sitze gerade an einer Performancekritischen Angelegenheit und könnte

geistige Unterstützung benötigen .

Es geht um folgendes:

Ich habe eine Funktion der ein Vector mit Punten (Locations) übergeben wird.

Der Rückgabewert soll ebenfalls ein vector sein nur das der mit Rect strukturen geüllt sein soll.

Ein wichtiger Hinweis könnte sein, das die Punkte in keiner Form vorab sortiert wurden.

Es gab schon vorher eine Lösung die aber recht simple gestrickt war und nur ein Rect zurückgab.

Dabei wurde der kleinste X, größte X, kleinste Y und größte Y Wert ermittelt und daraus wurde dann das Rect gebildet.

Das ist natürlich suboptimal sobald der vector nur wenige Punkte hat die aber weit auseinander liegen.

Bsp.:

Punkt A liegt bei 10/20

Punkt B liegt bei 1500/500

Punkt C liegt bei 1410/450

Die alte Funktion hätte jetzt ein Rectangle gebildet das wie folgt aussehen würde:

Rectangle : X=10, Y=20, Width = 1480 , Heigth= 480

Da aber die Punkte die nicht angegeben wurden nicht interessant sind wurde der Vorschlag unterbreitet eine Funktion zu schreiben, welche multiple Rect zurückgibt um so den ganzen Overhead an Punkten Herr zu werden.

Da das ganze aber recht performancekritisch ist fällt mir aktuell dazu noch kein adäquater.

Die Möglichkeiten die mir eingefallen sind würden zu lange dauern da ich den vector sehr sehr oft durchiterieren müsste.

Mein Ansatzpunkt war folgender:

-Neben dem vector der die Punkte (Locations) übergibt müsste noch ein Wert übergeben werden, welcher die toleranzgrenze der Punktentfernungen defniert (Ab wann muss ein nuss ein neues Rechteck generiert werden?!)

-Die nicht geordnete Liste müsste geordnet werden. Da bin ich mir jetzt nicht ganz sicher was besser wäre (nach X,Y oder beides).

Das wäre mein Anfang.

vector<Rect> CalculateRectangles(vector<Point> &data, int maxDistance)

{

       vector<Rect> result;

       vector<Point> orderedVector;

       //Sortierungsschleife

       for (int i =0; i< data.size();i++){

         //ToDo

       }

       //Duchiterieren des ordered Vectors und auf Basis der maxDistance die Rect Strukturen bilden.

return result;

}

So jetzt zu meiner Frage.

Wie würdet Ihr das angehen? Genauso oder völlig anders?

Ich bin mir da nicht so ganz sicher.

lg

Gateway

[flashpixx]

Bitte formuliere sowohl die Eingabe, wie das Ziel einmal in ein bzw. zwei Sätzen. Was ist gegeben und was soll nachher die Ausgabe sein?

[Gateway_man]

Bitte formuliere sowohl die Eingabe, wie das Ziel einmal in ein bzw. zwei Sätzen. Was ist gegeben und was soll nachher die Ausgabe sein?

Gegeben ist zum einen ein Vector vom Typ Point und ein integer Wert welcher die Maximale Reichweite der Bildpunkte definiert.

Die Point struktur besteht lediglich aus zwei Ganzahlwerten (X und Y).

Das Ergebnis soll ein vector vom typ Rect sein.

Die Rect Strukur verfügt über vier Ganzahlwerte (X,Y, Width und Heigth).

Die Anforderung ist die ganzen Punkte zu sinvollen Rechtecken zusammenzufassen anstatt ein großes zu definieren.

Denn wenn man das Rechteck aus den ganzen Punkten berechnet kann es sein das dabei auch ein großer Bereich im Rechteck erfasst wird der garnicht von Interesse ist.

Dabei ist zu beachten das nur die Punkte die übergeben wurden von interesse sind.

[flashpixx]

Gegeben ist zum einen ein Vector vom Typ Point und ein integer Wert welcher die Maximale Reichweite der Bildpunkte definiert.

verstehe ich das richtig, dass Du n verschiedene 2-dimensionale Punkte gegeben hast?

Die Anforderung ist die ganzen Punkte zu sinvollen Rechtecken zusammenzufassen anstatt ein großes zu definieren.

siehe Korrekt gestelltes Problem bzw. Ill-Pose-Problem.

"sinnvoll" ist kein definierter Begriff und somit ist Dein Problem nicht lösbar. Du musst für die Lösung des Problems und dem daraus resultierenden Algorithmus schon genau definieren was für Dich eine richtige Lösung ist, ohne diese Definition ist es nicht möglich einen Algorithmus zu entwickeln bzw. es wäre letztendlich eine rein zufallsbasierte Lösung.

Bitte überlege Dir, wie Du entsprechenden Bedingungen formulieren musst, damit man eine Lösung entwerfen kann

[Gateway_man]

Da ich es scheinbar nicht ordentlich rüberbringen kann hab ich mal ein Bild gemalt xD.

Siehe Anhang.

Nochmals. Es wird der Funktion ein vector mit Bildpunkten übergeben.

Die alte Version hat aus diesen Bildpunkten ein Rechteck generiert das alle Bildpunkte beinhaltet.

Jetzt schau dir das Bild an und du wirst die Problematik darin erkennen.

Es geht darum, das große Bereiche in dem Recheck überflüssig sind da dort keine Bildpunkte liegen.

Es sollen also nun statt einem Recheck mehrere Rechtecke gebildet werden um diese Problematik zu umgehen und auch nur die Bereiche zu erhalten in denen Bildpunkte liegen.

Das schwarze Rechteck dient als Beispiel für die alte Funktion. Die Funktion nimmt dafür den obersten Punkt in der Linken oberen Ecke und den letzten Punkt in der rechten unteren Ecke.

Die neue Funktion soll in dem Beispiel die roten Rechtecke berechnen und zurückgeben.

lg

Gateway

[Klotzkopp]

Es geht darum, das große Bereiche in dem Recheck überflüssig sind da dort keine Bildpunkte liegen. Es sollen also nun statt einem Recheck mehrere Rechtecke gebildet werden um diese Problematik zu umgehen und auch nur die Bereiche zu erhalten in denen Bildpunkte liegen.

Wenn es nur darum geht, ist die optimale Lösung die, dass du pro Punkt ein Rechteck erstellst, dann gibt es nichts Überflüssiges mehr.

Da das vermutlich auch nicht gewünscht ist, merkst du vielleicht, dass du dir ganz genau überlegen musst, wie du mögliche Lösungen bewertest. Wenn du nicht selbst klar definieren kannst, was die gesuchte "beste" Lösung ist, kannst du das Problem auch nicht durch ein Programm lösen lassen.

[flashpixx]

@Gateway_man: Es spielt keine Rollen was Du in Deine Funktion für Daten gibst, Du musst definieren was mit den Daten geschieht und eben wie diese zu einer Lösung umgesetzt werden sollen.

Wenn ich Dir Fleisch, Kartoffeln und Gemüse gebe, dann würdest Du sagen "mach mir daraus ein Essen". Wenn Du diese Aufgabe 5 Leuten gibst, dann werden alle 5 Dir zwar ein Essen kochen, aber jeder wird es anders machen und Du hast 5 verschiedene Gerichte nachher dort stehen, von denen Du vielleicht 3 gar nicht magst und 2 naja sind.

Bevor wir hier weiter diskutieren können musst Du einmal definieren wie Deine Lösung auszusehen hat bzw. was das Ziel des Algorithmus sein soll, das Ziel wird hier nicht sein Rechtecke zu erzeugen, sondern es wird sein Rechtecke mit einer gewissen Bedingung zu erzeugen

[Gateway_man]

Wenn ich Dir Fleisch, Kartoffeln und Gemüse gebe, dann würdest Du sagen "mach mir daraus ein Essen". Wenn Du diese Aufgabe 5 Leuten gibst, dann werden alle 5 Dir zwar ein Essen kochen, aber jeder wird es anders machen und Du hast 5 verschiedene Gerichte nachher dort stehen, von denen Du vielleicht 3 gar nicht magst und 2 naja sind.

Exakt das hatte ich ja gehofft.

Wie gesagt es geht mir hierbei weniger um eine fertige oder allgemein um die Lösung.

Wie ich schon geschrieben hatte ging es mir eher darum wie ihr das angehen würdet.

Damit meine ich nicht das komplettieren oder neudefinieren meiner Funktion.

Viele Wege führen nach Rom, jedoch hat jeder seine eigenen Vor- und Nachteile.

Wie ich bereits erwähnte sind die Kriterien hierfür lediglich die Performance.

Klotzkopp hat den Ball schonmal ins Rollen gebracht indem er verschiedene Vorgehensweise erwähnte.

Beispielsweise könnte ich für jeden Punkt der übergeben wurde ein Rechteck definieren.

Das hatte ich mir auch schon überlegt und es dann wieder verworfen weil es bei vielen Punkten nichtmehr performant wäre.

Damit man sich das besser vorstellen kann werde ich jetzt mal die Katze aus dem Sack lassen und den Einsatzzweck dieser Funktion erörtern. (Wobei ich denk das die meisten sich schon vorstellen können worauf das abziehlt).

Ich habe ein Modul das Bildschirminhalte überträgt. Ich kämpfe aber momentan noch um Performance. Zu Anfangs hatte ich den kompletten Bildschirminhalt komprimiert übertragen.

Das klappte innerhalb eines lokalen Netzes auch wunderbar.

Wenn man aber ins WAN wechselt wird das ganze abhängig vom Verbindungspartner sehr langsam.

Der Gedanke (der ja an sich schon in vielen Programmen umgesetzt wurde) war das man nur den Bereich sendet der sich geändert hat.

Eine solche Funktion würde geschrieben und ist aktiv im Einsatz. Diese ist akzeptabel aber es besteht noch viel Optimierungsbedarf.

Ich hatte mich damal entschieden es so einfach wie möglich umzusetzten (aus Zeitgründen).

Ich vergleiche lediglich die Bildpunkte beider Bilder.

Dann wird eigentlich das gemacht was ich oben bereits erwähnte.

Es wird ein Rechteck gebildet von den Punkt in der linken oberen Ecke und dem Punkt in der rechten unteren Ecke.

Die Problematik dabei habe ich oben bereits erwähnt aber ich werde Sie anhand des beispiels nochmal erläutern.

Stellt euch vor ein Icon im IconTray ändert sich und zur gleichen Zeit selektiert Ihr eine Desktopverknüpfung in der linken oberen Ecke eures Desktops.

Das Programm bemerkt es und bildet statt zwei kleiner Rechecke ein riesiges das von der Selektierten Desktopverknüpfung links oben bis runter zu dem Icon im IconTray geht.

Das ist natürlich alles andere als optimal.

Wie gesagt es geht mir hier weniger um eine Lösung sonder mehr um die verschiedenen Vorgehensweisen. Daher habe ich mich an euch gewendet um mich von euren Vorgehensweisen Inspirieren zu lassen.

Ich hatte beispielsweise auch schon die Möglichkeit in Erwägung gezogen die geänderten Bildpunkte einzeln zu übertragen.

lg

Gateway

[flashpixx]

Ich habe ein Modul das Bildschirminhalte überträgt.

Das kommt darauf, was übertragen werden z.B. statische Bilder, Videostreams o.ä. Bei Videostreams würde man ggf zu H.264 als Komprimierung greifen. Ich meine gängige Systeme wie VLC, RDP oder NX NoMachine nutzen entsprechende Ansätze, d.h. warum nutzt Du so etwas selbst nicht.

Der Gedanke (der ja an sich schon in vielen Programmen umgesetzt wurde) war das man nur den Bereich sendet der sich geändert hat.

[...] Diese ist akzeptabel aber es besteht noch viel Optimierungsbedarf. [...] Ich vergleiche lediglich die Bildpunkte beider Bilder.

Zunächst einmal ist die Frage, wie Du überhaupt definierst, ab wann eine Änderung übertragen wird. Dann ist die Frage, was Du real überträgst und wie Du das ggf. gegen nicht zu übertragende Bereiche abgrenzst. Man kann hier Mit Bounding Volumina, kd- , Grid, Oct-Trees oder auch sicherlich Überlegungen aus dem Bereich des Clippings (Cohen-Sutherland-Algorithmus) gewisse Optimierung erreichen bzw- Strukturen einer MIP-Map aufbauen, die Frage ist aber was hat man real an Daten, wo sind aktuell Schwächen des ganzen Systems und warum nutzt man nicht gängige Komponenten, bevor man hier irgendwie etwas zusammen codiert.

Wenn es Dir darum geht, Bildschirminhalte zu übertragen, dann nutze gängige Systeme bzw. nutze die Bibliothek dieser Systeme, damit wirst Du die beste Lösung erreichen und Du hast einen allgemeinen Ansatz, der eben entsprechende Kompatibilität mit bringt.

Wenn es sich allerdings um speziellere Anforderungen handelt, dann muss man diese sich im Detail anschauen und daraus ein passendes Verfahren ableiten. Im Moment sehe ich aber hier nicht den Bedarf so etwas zu machen, denn es gibt dafür schon fertige Lösungen, die man verwenden kann.

[Gateway_man]

Das kommt darauf, was übertragen werden z.B. statische Bilder, Videostreams o.ä.

Bei Videostreams würde man ggf zu H.264 als Komprimierung greifen.

Aktuell wird entweder ein ganzes Bild oder nur der partielle Teil der sich geändert hat übertragen (teilweise Redudant bei der partiellen Übertragung).

Zunächst einmal ist die Frage, wie Du überhaupt definierst, ab wann eine Änderung übertragen wird.

Dann ist die Frage, was Du real überträgst und wie Du das ggf. gegen nicht zu übertragende Bereiche abgrenzst.

Das Prinzip ist einfach. Solange das Modul aktiv ist wird von der .NET Anwendung eine Funktion einer Cpp Library aufgerufen.

Deren Signatur sieht wie folgt aus:

bool ExtractChangedRectangleExt(IntPtr hbmp, IntPtr hbmp1, int min, int max, ref ImageCompareResult result);

Der min Wert definiert die Prozentual minimal benötigte Abweichung beider Bilder. Erst wenn dieser Wert überschritten ist, wird das Rechteck berechnet das den veränderten Inhalt beinhaltet.

Der max Wert definiert die Prozentual maximale Obergrenze.

Die .Net Anwendung arbeitet dann mit dem ImageCompareResult objekt weiter.

Darin ist der fehlercode definiert (Sofern ein Fehler auftrat), sowie die prozentuale Abweichung beider Bilder und das Rechteck das sich geändert hat.

Aktuell wird ein Rechteck dann ermittelt wenn eine Abweichung von mindestens 2 Prozent erreicht wurde.

Das Recheckt wird berechnet. Die Bildpunkt-Informationen werden extrahiert und das Ergebnis wird verschlüsselt über einen Socket in der .NET Anwendung gesendet.

Man kann hier Mit Bounding Volumina, kd- , Grid, Oct-Trees oder auch sicherlich Überlegungen aus dem Bereich des Clippings (Cohen-Sutherland-Algorithmus) gewisse Optimierung erreichen bzw- Strukturen einer MIP-Map aufbauen,

die Frage ist aber was hat man real an Daten, wo sind aktuell Schwächen des ganzen Systems und warum nutzt man nicht gängige Komponenten, bevor man hier irgendwie etwas zusammen codiert.

Ich werde mich dahingehend mal etwas weiter Informieren.

Wenn es Dir darum geht, Bildschirminhalte zu übertragen, dann nutze gängige Systeme bzw. nutze die Bibliothek dieser Systeme, damit wirst Du die beste Lösung erreichen und Du hast einen allgemeinen Ansatz,

der eben entsprechende Kompatibilität mit bringt.

Wenn es sich allerdings um speziellere Anforderungen handelt, dann muss man diese sich im Detail anschauen und daraus ein passendes Verfahren ableiten.

Im Moment sehe ich aber hier nicht den Bedarf so etwas zu machen, denn es gibt dafür schon fertige Lösungen, die man verwenden kann.

Es geht mir nicht um kompatibilität. Das wäre aktuell garnicht möglich da die alternativanwendungen die du aufgezählt hast nichts mit den Daten anfangen könnten (Daten werden über ein nicht properitäres Verfahren

verschlüsselt).

Dann gibt es noch faktoren wie:

- Mögliche Probleme mit Lizenzen von Drittanbietern.

- Da die Anforderungen zweifelsohne eine Anpassung der Fremdkomponenten notwendig macht müsste es eine Open-Source Lösung sein die gut Dokumentiert ist.

Es geht mir letztendlich darum die bestehende Lösung zu verbessern.

Aber wir schweifen vom Thema ab.

Es geht hier keineswegs um das gesamte Modul (da dies ja schon funktioniert), sondern lediglich um die sinvolle Gruppierung der geänderten Bildpunkte. (vorzugsweise in Geometrischen Formen).

Ich werde testweise die aktuelle Funktion fertig implementieren und mich dann nocheinmal melden um meinen Lösungsweg zu posten.

Eventuell fällt dem ein oder anderen noch ein Weg ein das ganze noch etwas flotter zu gestallten.

lg

Gateway

[flashpixx]

Der min Wert definiert die Prozentual minimal benötigte Abweichung beider Bilder. Erst wenn dieser Wert überschritten ist, wird das Rechteck berechnet das den veränderten Inhalt beinhaltet.

Der max Wert definiert die Prozentual maximale Obergrenze.

Wofür benötigst Du eine Obergrenze? Im Normalfall braucht man nur einen Threshold, der besagt ab wann neu übertragen wird, d.h. eine Grenze fällt eigentlich weg.

Darin ist der fehlercode definiert (Sofern ein Fehler auftrat), sowie die prozentuale Abweichung beider Bilder und das Rechteck das sich geändert hat.

Wie stellst Du diese Abweichung fest? Wenn Du letztendlich nur die Pixel zählst, die sich unterscheiden, von denen ich jetzt ausgehe. Musst Du immer n*m Pixel * Farbtiefe vergleichen. Was letztendlich zuviel ist und vor allem sehr ineffizient ist.

Im Normalfall würde man sich an einen Eventhandler anhängen, so dass man schon direkt von dem Objekt, das verändert wurde eine Nachricht erhält. Zusätzlich muss man auch nur die Daten übertragen, die direkt sichtbar für den Benutzer sind, d.h. man hat hier eine klassische Clippinganwendung

Aktuell wird ein Rechteck dann ermittelt wenn eine Abweichung von mindestens 2 Prozent erreicht wurde.

Wenn Du so einen Ansatz hast, dann entstehen schon direkt Probleme z.B. beim Focuswechsel. Wenn ein Fenster sich durch Änderung z.B. der Titelfarbe als Blinken Aufmerksamkeit durch den Benutzer anfordern will, dann hast Du hier definitiv mehr als 2% Abweichung, zusätzlich läufst Du in die Problematik, dass Du, wenn Du dieses Verhalten exakt übertragen möchtest Du mindestens doppelt so häufig alle Bereiche abtasten musst, wie die Frequenz des Blinkens ist (Shannon-Abtasttheorem: Nyquist-Shannon-Abtasttheorem ), d.h. Dein Algorithmus muss den gesamten Bildbereich doppelt so schnell auf Änderungen abtasten, wie Du theoretisch wechselnde Veränderungen haben kannst.

- Da die Anforderungen zweifelsohne eine Anpassung der Fremdkomponenten notwendig macht müsste es eine Open-Source Lösung sein die gut Dokumentiert ist.

Für NX NoMachine ist die GPL verfügbar.

Es geht hier keineswegs um das gesamte Modul (da dies ja schon funktioniert), sondern lediglich um die sinvolle Gruppierung der geänderten Bildpunkte. (vorzugsweise in Geometrischen Formen).

Ich gehe davon aus, dass in dem System mehrere strukturelle Fehler sind. Pixelbasiert einfach die Bereich abzutasten ist sicherlich nicht der richtige Ansatz, d.h. irgendwie effizienter zu Gruppieren wird ohne weitere Kenntnis nicht möglich sein. Wenn ich z.B. ein Video auf dem Bildschirm habe, dann wäre die Frage, wie Dein Algorithmus dieses verarbeitet. Bei einem normalen Film hast Du durchaus ständig Veränderungen des Pixelbereiches, d.h. Dein Algorithmus muss so schnell (nach Shannon) sein, dass er die gleiche Frameanzahl bearbeiten kann, wie das Video Läuft (analog für Spiele z.B.), d.h. die Bearbeitung darf, d.h. von Änderungsdedektion bis zum Versenden der Daten über das Netzwerk darf nur so lange dauern, wie das Frame sichtbar ist.

Wenn also die Daten mit z.B. 60 fps dargestellt werden, muss Dein Programm mit mind. 120 fps den kompletten Bildschirm abtasten, um Änderungen zu erkennen.

Ich würde dringend dazu raten, den kompletten Algorithmus zu überdenken und ggf. auf bestehende Komponenten setzen

[Gateway_man]

Wofür benötigst Du eine Obergrenze? Im Normalfall braucht man nur einen Threshold, der besagt ab wann neu übertragen wird, d.h. eine Grenze fällt eigentlich weg.

Das max bedeutet nur das er bei einer Abweichung darüber hinaus das ganze Bild nehmen soll. Beispiel bei 95 % Abweichung braucht er den Bereich der sich geändert hat nicht extahieren. Dann soll er gleich den ganzen Bereich nehmen...

Wie stellst Du diese Abweichung fest?

Meinst du Prozentual?!

An sich wird das ganze recht einfach gemacht.

Die Cpp Funktion hat beide Bilder.

Vor beginn des Vergleiches wird die GesamtPixel Anzahl erreichnet. (Width * Heigth)

Am Ende der Funktion wenn der Vector alle Pixel beinhaltet die sich geändert haben wird folgendes gemacht:

Percentage = (Vector.Size() / GesamtPixel) * 100

Wenn Du letztendlich nur die Pixel zählst, die sich unterscheiden, von denen ich jetzt ausgehe. Musst Du immer n*m Pixel * Farbtiefe vergleichen. Was letztendlich zuviel ist und vor allem sehr ineffizient ist.

Was du jetzt mit der Farbtiefe willst weiß ich zwar nicht aber wie ich es berechne hast du oben schon gesehn. (Nebenbei bemerkt, werden nur ganz bestimmte Bilder in der Vergleichsfunktion unterstützt)

Im Normalfall würde man sich an einen Eventhandler anhängen, so dass man schon direkt von dem Objekt, das verändert wurde eine Nachricht erhält.

Das halte ich für eher unwarscheinlich.

Du kannst dich nur an Dinge hängen die auch über ein Handle verfügen und vom OS Messages erhalten.

Was machst du also wenn Anwendung xy mit GDI einen Kreis auf HWND 0 zeichnet.

Ich wüsste nicht wie ich mich daran hängen sollte.

Ich wusste das es ein Fehler war auf den Einsatzzweck näher einzugehen, weil man leicht in Versuchung kommt und sich zu sehr auf die Funktion fixiert welche die Bilder vergleicht.

Es geht mir nicht darum eine bereits funktionierende Funktion zu ersetzten.

Und auch wenn mir das einige nicht glauben möchten.

Der Vergleich sowie das extrahieren der veränderten Daten läuft aktuelle bei einer Auflösung von 1920x1080 innerhalb von 0,03571 Sekunden ab.

Damit bin ich mehr als Zufrieden.

Ist ja nicht so als würde ich 19201080 mal bmp1.GetPixel(x,y) != bmp2.GetPixel(x,y) performen.

Es ging mir einzig allein darum die nicht veränderten Pixel aus dem Rechteck zu bekommen indem ich multiple kleinere Rechecke bilde auf Basis eines Vektors der die Pixeldaten innehält.

Und das wenn möglich ohne die momentan akzeptable Dauer des ganzen Prozesses groß zu beeinflussen.

Das Problem das aus dem oben genannten Problem resultiert ist folgendes:

Wenn sich zwei Bildpunkte ändern, die jedoch weit voneinander entfernt sind, wird ein großes Rechteck gebildet und das ist kontraproduktiv wenn ich versuche den Netzwerktraffic so gering wie möglich zu halten.

lg

Gateway

[flashpixx]

Wenn sich zwei Bildpunkte ändern, die jedoch weit voneinander entfernt sind, wird ein großes Rechteck gebildet und das ist kontraproduktiv wenn ich versuche den Netzwerktraffic so gering wie möglich zu halten.

Dir ist die Problematik nicht wirklich klar: Wenn ich ein einziges Pixel auf dem Schirm verändere (mal abgesehen, davon dass dann evtl Dein Threshold nicht greift) ist die Frage, wie Du das dedektierst !? Im Moment machst Du letztendlich durch Pixelvergleiche von Rechtecken.

Du sammelst eben alle veränderten Pixel ein, bastelst daraus Rechtecke und überträgst diese.

Die zentrale Frage bei Deinem Problem ist, wann muss ein Bereich übertragen werden und wie viele Pixel / Daten müssen übertragen werden, damit das Bild korrekt dargestellt werden kann. Beides lässt sich mit unterschiedlichen Strukturen effizient bearbeiten und feststellen. Ich habe diesbezüglich einige genannt: kd-, Oct-, Grid-Tree oder auch Szenegraphen bzw. Bounding-Hierarchien.

Da Du aber immer wieder auf Deine Rechtecke und Pixel das Problem reduzierst, wird sich das Problem nicht wirklich effizient lösen lassen.