Wie finde ich überlappende mehrdimensionale Bereiche? [geschlossen]
Posted: 31 Dec 2024, 14:17
Angenommen, ich schreibe die Funktion find_overlapping_ranges, um überlappende Bereiche in einer Liste mehrdimensionaler Bereiche zu finden. Zwei mehrdimensionale Bereiche überlappen sich, wenn sie sich in allen Dimensionen überlappen.
Die Anzahl der Bereiche beträgt ~100.000 oder mehr. Der einfachste Ansatz besteht darin, alle Bereichspaare in der Liste zu überprüfen, was zu einer Komplexität O(n^2) führt. Gibt es einen effizienteren Algorithmus, um überlappende mehrdimensionale Bereiche zu finden?
Code: Select all
from typing import List, Tuple
from dataclasses import dataclass
Interval = Tuple[float, float] # Single interval with (min, max) bounds
Range = List[Interval] # Multi-dimensional range
@dataclass
class Overlap:
range1_index: int # Index of the first overlapping range in the list
range2_index: int # Index of the second overlapping range
def find_overlapping_ranges(ranges: List[Range]) -> List[Overlap]