Prüfen ob verschiedene Regionen ein Punkt enthalten

[100]

Hi, ich möchte ein optimiertes Verfahren für folgende Aufgabe finden:

Später spielt sich das Ganze im 3-dimensionalen Raum ab, zum Verständnis tut es ein 2-dimensionaler Raum allerdings auch. Ich habe also ein Koordinatensystem (später in alle Richtungen) mit verschiedenen Rechtecken, die sich auch überlappen können. Die Rechtecke (Regionen auf meinem Feld) sind definiert durch ihren kleinsten Punkt (also dem Eckpunkt, der dem Ursprung am nächsten ist) und den jeweils gegenüberliegenden Punkt.
Es gibt locker 100-200 Regionen und 300-500 Mal pro Sekunde muss geprüft werden, ob eine Koordinate in einer Region vorhanden ist.

Minimiert werden soll die Zeit für die Ausführung, was vorher alles an Arbeit anfällt ist egal.

Meine einzige Lösung bisher war die, dass ich alle Regionen für die jeweiligen Koordinaten pro Wert (minX, maxX, minY, maxY) jeweils in eine geordnete Datenstruktur eingefüge, sodass ich zumindestens alle ausschließe, die darüber liegen. Trotzdem werden eigentlich unnötige Rechnungen durchgeführt, nämlich von Regionen, die eigentlich schon vorher ausgeschieden sind. Um das zu vermeiden wäre es meiner Ansicht nach nötig, zur Laufzeit eine Art Liste mit Kandidaten zu erstellen, allerdings kommen mir dann langsam die Zweifel, ob ich im Endeffekt nicht mehr Arbeit verursache als ich einspare.

Umgesetzt werden soll dies in Java. Vielleicht hat jemand eine gute Idee mit Erklärungen auf Lager ;)

[blackberry]

Mein vielleicht etwas naiver Ansatz (aber das sinnvollste, was mir nach 10 Min dazu eingefallen ist):

Du könntest deine Rechtecke in konzentrische Kreise um den Ursprung einbetten.
Skizze:
http://img6.imagebanana.com/img/mr0exj5g/skizze.png

Dann könntest du deine Rechtecke evtl. in deiner Datenstruktur auch noch nach dem Radius ihres größtens sie noch berührenden Kreises anordnen. Die Euklid-Norm deines Punktes als Vektor aufgefasst kannst du ganz leicht berechnen; das musst du überdies auch nur einmal machen, denn die ändert sich ja während eines Durchlaufs nicht.

Anschließend kannst du die Rechtecke finden, die für einen Vergleich überhaut infrage kommen. Wenn du ein großes Feld mit vergleichsweise kleinen Rechtecken hast, dann werden das von vornherein nicht sehr viele sein.

Je nachdem wie geschickt du diese sortiert hast kannst du die ganz schnell finden und zum prüfen musst du auch nur den kleinen und großen Radius mit der Norm des Vektors vergleichen.

Wenn dann die Menge deiner Kandidaten schon so eingeschränkt ist kannst du für jedes dieser infrage kommenden Rechtecke einen "echten" Vergleich anstellen, ob dein Punkt nun drin liegt, oder nicht.