N intersection de rectangle

Question

Considérons l'ensemble de n rectangles parallèles à l'axe. L'algorithme de force brute est de vérifier si un rectangle intersecte avec d'autres et la complexité est O (n^2). Existe-t-il un algorithme avec la complexité de O (nlogn) pour trouver toutes les intersections entre ces ensembles de rectangles?

Deuxième question est de savoir comment trouver des rectangles qui sont à l'intérieur d'un autre rectangle dans un ensemble donné de rectangles également avec la complexité O (nlogn)?

Answer 1

Regardez dans les arbres quadruples ou dans la zone de contour large alignée par axe pour la détection de coup.

Ce sont des systèmes de moteur d'utilisation de jeu/physique typiques pour la détection de coup rectangle.