Wie finde ich überlappende mehrdimensionale Bereiche?Python

Python-Programme
Guest
 Wie finde ich überlappende mehrdimensionale Bereiche?

Post by Guest »

Angenommen, ich schreibe die Funktion find_overlapping_ranges, um überlappende Bereiche in einer Liste mehrdimensionaler 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 range in the list
range2_index: int                      # Index of the second range in the list
overlapping_intervals: List[Interval]  # Overlapping intervals for each dimension

def find_overlapping_ranges(ranges: List[Range]) -> List[Overlap]

Die erwartete Anzahl von Bereichen beträgt ~10.000 und die erwartete Anzahl von Dimensionen beträgt ~100. Vielleicht ist es erwähnenswert, dass in den meisten Fällen keine Überlappung erwartet wird und die Funktion [] zurückgeben sollte. Der naive Ansatz, jedes Bereichspaar zu überprüfen, scheint nicht machbar. Welchen Algorithmus würden Sie vorschlagen?
Wenn kein Algorithmus machbar ist, würde ich eine einfachere Funktion has_overlap verwenden, um zu prüfen, ob es eine Überlappung gibt.

Code: Select all

def find_overlapping_ranges(ranges: List[Range]) -> bool

Quick Reply

Change Text Case: 
   
  • Similar Topics
    Replies
    Views
    Last post