J'ai plusieurs polygones convexes qui se croisent. Je veux trouver les zones où beaucoup d'entre elles se croisent. Dans une image, on pourrait y voir un "pic". Je cherche les pics locaux. J'ai le logiciel pour croiser deux polygones. Maintenant, je pense à la façon de calculer les pics, sans calculer toutes les intersections possibles (temps exponentiel!).Intersection multiple de polygones convexes
Est-ce que quelqu'un a un indice?
Étant donné k polygones convexes. Supposons que nous ayons la limite de tous les polygones donnés sous la forme de n segments de ligne. Chaque segment de ligne a une référence au polygone auquel il appartient et à son côté intérieur. Laissez-nous trier les sommets des segments de ligne par leur coordonnée x. Maintenant, nous commençons un balayage de ligne de gauche à droite. Pendant le balayage au plus O (k) fois un polygone commence et se termine, car tous les polygones sont convexes. Lors d'un tel événement de départ, nous examinons l'état de la ligne de balayage et déterminons combien d'autres polygones nous entourent. Qui prend le temps O (n).
Pour n segments le balayage de ligne vous donne toutes les intersections en O (n log n + k^2) temps en ajoutant la gestion des événements de démarrage que nous obtenons O (n log n + k^2 + kn) temps. En utilisant les références des segments de ligne, il devrait être possible d'assigner à chaque zone (segment de ligne) le nombre de polygones couvrant actuellement.
Merci pour la réponse rapide! – yar
Si je vous comprends bien, l'exemple suivant ne fonctionnera pas: Deux polygones en forme de losange se croisent au milieu, mais leurs parties gauche et droite ne se croisent pas. La ligne de balayage va de gauche à droite, de sorte qu'à chaque début d'un polygone, nous comptons 1 polygone et à la fin, nous comptons 0 polygones. De cette façon, nous manquons l'intersection, non? – yar
@yar le principal avantage de l'approche sweepline est que nous trouvons ces intersections. Comme nous savons déjà combien de polygones sont imbriqués avant une telle intersection, nous devons seulement augmenter ou diminuer le nombre assigné aux segments respectifs, selon le type d'intersection. Comme nous savons où se situe l'intérieur relatif des segments, nous pouvons désirer localement ce qu'il faut faire. – gue