Ich habe eine große Sammlung von Rechtecken, alle gleich groß. Ich generiere zufällige Punkte, die nicht in diese Rechtecke fallen sollen. Ich möchte also testen, ob der generierte Punkt in einem der Rechtecke liegt, und wenn ja, einen neuen Punkt generieren.

Die Verwendung von R-Bäumen scheint zu funktionieren, aber sie sind wirklich für Rechtecke und nicht für Punkte gedacht. Ich könnte eine modifizierte Version eines R-Tree-Algorithmus verwenden, der auch mit Punkten arbeitet, aber ich würde das Rad lieber nicht neu erfinden, wenn es bereits eine bessere Lösung gibt. Ich bin nicht sehr vertraut mit Datenstrukturen, also gibt es vielleicht schon eine Struktur, die für mein Problem funktioniert?

Zusammenfassend möchte ich wissen, ob jemand einen guten Algorithmus kennt, der in Python funktioniert und mit dem überprüft werden kann, ob ein Punkt in einem Rechteck in einem bestimmten Satz von Rechtecken liegt.

Bearbeiten: Dies ist in 2D und die Rechtecke werden nicht gedreht.