Réduction du temps nécessaire pour trouver l'intersection de lignes N

Question

Il existe N segments de ligne horizontaux ou verticaux. Maintenant, j'ai besoin de connaître le nombre total d'Intersections et le nombre total d'Intersections par segment de ligne. N peut aller jusqu'à . J'ai essayé de vérifier chaque paire de lignes. La réponse est correcte, mais j'ai besoin de réduire le temps que cela prend.

Voici mon code:

using namespace std; 

typedef struct Point 
{ 
    long long int x; 
    long long int y; 
} ; 


bool fun(Point p0, Point p1, Point p2, Point p3) 
{ 
    double s1_x, s1_y, s2_x, s2_y; 
    s1_x = p1.x - p0.x;  s1_y = p1.y - p0.y; 
    s2_x = p3.x - p2.x;  s2_y = p3.y - p2.y; 

    double s, t; 
    s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y))/(-s2_x * s1_y + s1_x * s2_y); 
    t = (s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x))/(-s2_x * s1_y + s1_x * s2_y); 

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1) 
    { 
     return 1; // Collision detected 
    } 

    return 0; // No collision 
} 


int main() 
{ 
    long long int n // number of line segments; 

    Point p[n],q[n]; // to store end points of line segments 

    for(long long int i=0;i<n;i++) 
    { 

// line segments is defined by 2 points P(x1,y1) and Q(x2,y2) 
     p[i].x=x1; 
     p[i].y=y1; 
     q[i].x=x2; 
     q[i].y=y2; 
    } 

    for(long long int i=0;i<n-1;i++) 
    { 
     for(long long int j=i+1;j<n;j++) 
     { 
      if(fun(p[i],q[i],p[j],q[j])) 
       count++; 
     } 

    } 

    return 0; 
} 

que quelqu'un peut me aider à réduire la complexité temporelle de ce programme?

Answer 1

Voici un algorithme O (n log n) -time qui utilise une ligne de balayage avec un arbre Fenwick.

Etape 0: coordonnées remappage

Trier les coordonnées x et remplacer chaque valeur par un nombre entier dans 0..n-1 de manière à préserver l'ordre. Faites de même pour les coordonnées y. Les propriétés d'intersection sont préservées tout en permettant aux algorithmes ci-dessous une implémentation plus simple.

Etape 1: segments de lignes parallèles

je décris cette étape pour des segments horizontaux. Répétez l'opération pour les segments verticaux.

Groupez les segments horizontaux par la coordonnée y. Traitez un groupe à la fois, en créant des événements pour la ligne de balayage comme suit. Chaque segment reçoit un événement de démarrage à son extrémité inférieure et un événement d'arrêt à son plus grand. Le tri commence avant les arrêts si vous voulez des segments de ligne fermés. Balayez les événements dans l'ordre trié, en suivant le nombre de segments de ligne qui coupent actuellement la ligne de balayage et le nombre d'événements de début traités. Le nombre d'intersections parallèles pour un segment est (nombre de segments recoupés à l'heure de début + nombre d'événements de démarrage traités à l'heure d'arrêt - nombre d'événements de démarrage traités à l'heure de début). (Voir aussi Given a set of intervals, find the interval which has the maximum number of intersections pour une explication précédente de la mine pour cela.)

Etape 2: perpendiculaire segments de ligne

Je vais décrire cette étape en termes de comptage pour chaque segment de ligne horizontale nombre de segments de ligne verticale il se croise.

Nous faisons un autre algorithme de ligne de balayage. Les événements sont des démarrages de segments horizontaux, des segments verticaux et des arrêts de segments horizontaux, triés dans cet ordre en supposant des segments de ligne fermés. Nous utilisons un arbre de Fenwick pour suivre, pour chaque coordonnée y, combien de segments verticaux ont couvert cette coordonnée y jusqu'ici. Pour traiter un début horizontal, soustrayez la valeur de l'arbre de sa coordonnée y à partir de son nombre d'intersections. Pour traiter un arrêt horizontal, ajoutez la valeur de l'arbre pour sa coordonnée y à son compte d'intersection. Cela signifie que le nombre augmente de la différence, qui est le nombre de segments verticaux qui ont poignardé l'horizontal pendant qu'il était actif. Pour traiter un segment vertical, utilisez la puissance de l'arbre Fenwick pour incrémenter rapidement toutes les valeurs entre sa coordonnée y inférieure et sa plus grande (inclusivement en supposant des segments fermés).

Si vous le souhaitez, ces algorithmes de ligne de balayage peuvent être combinés. Je les ai gardés séparés pour des raisons explicatives.