Trouver des polygones convexes qui se chevauchent

Question

J'ai un ensemble de polygones convexes avec un nombre modéré de côtés (disons de 4 à 30). Il y a quelques dixièmes de polygones, disons 100 à 1000. La plupart d'entre eux sont isolés mais quelques-uns forment de petits groupes de 2 à 10 qui se chevauchent entre eux.

J'ai besoin d'identifier efficacement les groupes de polygones qui se chevauchent.

Existe-t-il un algorithme classique? (Je pense à une approche «sweepline» mais peut-être y a-t-il mieux?) Serait-il bénéfique de placer les polygones dans des boîtes avant la détection?

Ci-dessous, un cas représentatif.

Answer 1

Une approche traditionnelle qui est utilisée pour ce genre de problème en deux dimensions est de construire un quadtree, qui divise hiérarchiquement votre espace 2D dans des seaux successivement plus petits jusqu'à ce que vous avez un petit nombre d'objets dans chaque seau. Votre détection de chevauchement marcherait sur le quadtree jusqu'à ce que vous trouviez le compartiment ou l'ensemble de compartiments qui ont été intersectés par votre objet, puis vous effectueriez votre détection de chevauchement sur un ensemble d'objets plus petit.

Il y a une introduction simple à construire et à utiliser eux pour la détection de collision ici: Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space

Une simple mais approche plus informatiquement coûteuse serait de faire quelque chose un peu comme utiliser un z-buffer pour déterminer si un polygone obture une autre :

• Attribuer chacun de vos polygones un numéro unique (il est de profondeur)
• Rastériser chaque polygone à un tampon, en vérifiant chaque écriture dans la mémoire tampon pour voir si vous avez occlus un pixel qui est déjà défini. Si c'est le cas, la profondeur identifie le polygone que vous avez occlus et la nouvelle valeur que vous écrivez le polygone avec lequel vous l'avez occlus.