Mam dużą kolekcję prostokątów, wszystkie o tym samym rozmiarze. Generuję losowe punkty, które nie powinny wpaść w te prostokąty, więc chciałbym sprawdzić, czy wygenerowany punkt leży w jednym z prostokątów, a jeśli tak, wygenerować nowy punkt.

Używanie drzew R wydaje się działać, ale tak naprawdę są przeznaczone dla prostokątów, a nie punktów. Mógłbym użyć zmodyfikowanej wersji algorytmu R-tree, który również działa z punktami, ale wolałbym nie odkrywać na nowo koła, jeśli jest już jakieś lepsze rozwiązanie. Nie znam dobrze struktur danych, więc może już istnieje jakaś struktura, która działa na mój problem?

Podsumowując, zasadniczo pytam, czy ktoś wie o dobrym algorytmie, który działa w Pythonie, który może być użyty do sprawdzenia, czy punkt leży w jakimś prostokącie w danym zestawie prostokątów.

edytuj: To jest w 2D, a prostokąty nie są obracane.