Implémentation d’un algorithme de force brute pour la détection d’un polygone à intersection automatique

Votre algorithme actuel de Brute-Force est O (n ^ 2). Pour seulement vos deux 70 000 polygones de lignes, cela représente un facteur de près de 10 milliards d’opérations, sans parler des 700 000 autres polygones. De toute évidence, aucune optimisation de code ne suffira, vous avez donc besoin d’une optimisation algorithmique qui puisse réduire ce facteur O (n ^ 2) sans être excessivement compliquée.

Le O (n ^ 2) provient des boucles nestedes dans l’algorithme de force brute qui sont chacune délimitées par n , ce qui en fait un O (n * n). Le moyen le plus simple d’améliorer cela consiste à trouver un moyen de réduire la boucle interne de sorte qu’elle ne soit pas liée ou dépendante de n . Nous devons donc trouver un moyen de commander ou de réorganiser la liste interne de lignes avec lesquelles vérifier la ligne externe, de sorte que seule une partie de la liste complète doit être analysée.

L’approche que je suis en train de tirer tire parti du fait que si deux segments de droite se croisent, la plage de leurs valeurs X doit se chevaucher. Remarquez, cela ne signifie pas qu’ils se croisent, mais si leurs plages X ne se chevauchent pas, ils ne peuvent pas se croiser, il n’est donc pas nécessaire de les comparer. (Ceci est également vrai pour les plages de valeurs Y, mais vous ne pouvez utiliser qu’une dimension à la fois).

L’avantage de cette approche est que ces plages X peuvent être utilisées pour ordonner les extrémités des lignes, qui peuvent à leur tour être utilisées comme points de départ et d’arrêt pour les lignes contre lesquelles l’intersection doit être vérifiée.

Nous définissons donc une classe personnalisée ( endpointEntry ) qui représente les valeurs High ou Low X des deux points de la ligne. Ces points de terminaison sont tous placés dans la même structure de liste, puis sortingés en fonction de leurs valeurs X.

Ensuite, nous implémentons une boucle externe dans laquelle nous parcourons toute la liste, comme dans l’algorithme de force brute. Cependant, notre boucle intérieure est considérablement différente. Au lieu de ré-parsingr toute la liste des lignes pour vérifier les intersections, nous commençons plutôt à parsingr la liste des extrémités sortingées à partir de l’extrémité supérieure de la valeur X de la ligne de la boucle extérieure et à la terminer lorsque nous passons sous l’extrémité inférieure de la même valeur. De cette manière, nous ne vérifions que les lignes dont la plage de valeurs X chevauche la ligne de la boucle externe.

OK, voici une classe illustrant mon approche:

 class CheckPolygon2 { // internal supporting classes class endpointEntry { public double XValue; public bool isHi; public Line2D line; public double hi; public double lo; public endpointEntry fLink; public endpointEntry bLink; } class endpointSorter : IComparer { public int Compare(endpointEntry c1, endpointEntry c2) { // sort values on XValue, descending if (c1.XValue > c2.XValue) { return -1; } else if (c1.XValue < c2.XValue) { return 1; } else // must be equal, make sure hi's sort before lo's if (c1.isHi && !c2.isHi) { return -1; } else if (!c1.isHi && c2.isHi) { return 1; } else { return 0; } } } public bool CheckForCrossing(List lines) { List pts = new List(2 * lines.Count); // Make endpoint objects from the lines so that we can sort all of the // lines endpoints. foreach (Line2D lin in lines) { // make the endpoint objects for this line endpointEntry hi, lo; if (lin.P1.X < lin.P2.X) { hi = new endpointEntry() { XValue = lin.P2.X, isHi = true, line = lin, hi = lin.P2.X, lo = lin.P1.X }; lo = new endpointEntry() { XValue = lin.P1.X, isHi = false, line = lin, hi = lin.P1.X, lo = lin.P2.X }; } else { hi = new endpointEntry() { XValue = lin.P1.X, isHi = true, line = lin, hi = lin.P1.X, lo = lin.P2.X }; lo = new endpointEntry() { XValue = lin.P2.X, isHi = false, line = lin, hi = lin.P2.X, lo = lin.P1.X }; } // add them to the sort-list pts.Add(hi); pts.Add(lo); } // sort the list pts.Sort(new endpointSorter()); // sort the endpoint forward and backward links endpointEntry prev = null; foreach (endpointEntry pt in pts) { if (prev != null) { pt.bLink = prev; prev.fLink = pt; } prev = pt; } // NOW, we are ready to look for intersecting lines foreach (endpointEntry pt in pts) { // for every Hi endpoint ... if (pt.isHi) { // check every other line whose X-range is either wholly // contained within our own, or that overlaps the high // part of ours. The other two cases of overlap (overlaps // our low end, or wholly contains us) is covered by hi // points above that scan down to check us. // scan down for each lo-endpoint below us checking each's // line for intersection until we pass our own lo-X value for (endpointEntry pLo = pt.fLink; (pLo != null) && (pLo.XValue >= pt.lo); pLo = pLo.fLink) { // is this a lo-endpoint? if (!pLo.isHi) { // check its line for intersection if (pt.line.intersectsLine(pLo.line)) return true; } } } } return false; } } 

Je ne suis pas certain de la véritable complexité d’exécution de cet algorithme, mais je soupçonne que pour la plupart des polygones non pathologiques, il sera proche de O (n * SQRT (n)), ce qui devrait être assez rapide.

Explication de la logique de boucle interne:

La boucle interne parsing simplement la liste des points d’extrémité dans le même ordre de sorting que la boucle externe. Mais il commencera à parsingr à partir de l’endroit où se trouve la boucle externe à partir de laquelle la boucle externe est actuellement dans la liste (qui est le point hiX d’une ligne), et n’parsingra que jusqu’à ce que les valeurs de point final soient inférieures à la valeur loX correspondante de cette même ligne.

Ce qui est délicat ici, c’est que cela ne peut pas être fait avec un énumérateur (le foreach(..in pts) de la boucle externe) car il n’y a aucun moyen d’énumérer une sous-liste d’une liste, ni de démarrer l’énumération basée sur une autre énumération. . Par conséquent, au lieu de cela, j’ai utilisé les propriétés des liens vers l’avant et vers l’arrière (fLink et bLink) pour créer une structure de liste doublement chaînée qui conserve l’ordre sortingé de la liste, mais que je peux parsingr de manière incrémentielle sans énumérer la liste:

 for (endpointEntry pLo = pt.fLink; (pLo != null) && (pLo.XValue >= pt.lo); pLo = pLo.fLink) 

En décomposant cela, l’ancien spécificateur de boucle for comporte trois parties: initialisation, condition et incrémentation-décrémentation. L’expression d’initialisation, endpointEntry pLo = pt.fLink; initialise pLo avec le lien direct du point actuel de la liste. C’est-à-dire le point suivant de la liste, en ordre de sorting décroissant.

Ensuite, le corps de la boucle interne est exécuté. Ensuite, l’incrémentation-décrémentation pLo = pLo.fLink est appliquée, ce qui définit simplement le point actuel de la boucle interne ( pLo ) sur le prochain point inférieur à l’aide de son lien direct ( pLo.fLink ), faisant ainsi avancer la boucle.

Finalement, il boucle après avoir testé la condition de boucle (pLo != null) && (pLo.XValue >= pt.lo) qui boucle tant que le nouveau point n’est pas nul (ce qui voudrait dire que nous étions à la fin de la liste) et tant que la valeur XValue du nouveau point est toujours supérieure ou égale à la valeur X basse du point actuel de la boucle externe. Cette deuxième condition garantit que la boucle interne ne regarde que les lignes qui chevauchent la ligne du point final de la boucle externe.

Ce qui est plus clair pour moi à présent, c’est que j’aurais probablement pu contourner toute cette maladresse de fLink-bLink en traitant la liste des points extrêmes comme un tableau:

1. Remplir la liste avec des points d’extrémité
2. Trier la liste par XValue
3. Boucle extérieure dans la liste dans l’ordre décroissant, à l’aide d’un iterator d’index ( i ), au lieu d’un énumérateur foreach
4. (A) Boucle intérieure dans la liste, à l’aide d’un deuxième iterator ( j ), commençant par i et se terminant lorsqu’il passe sous pt.Lo

Je pense que ce serait beaucoup plus simple. Je peux poster une version simplifiée comme ça, si vous voulez.

il y a 2 choses à vérifier:

1. polygone fermé se compose d’une séquence cyclique de points
   • s’il y a plus d’une fois le même point dans cette séquence qu’il ne s’agisse d’un polygone à intersection automatique.
   • méfiez-vous que le premier et le dernier point peuvent être identiques (ce qui diffère selon la représentation de votre polygone); dans ce cas, ce point doit être plus bronzé deux fois.
2. vérifier toutes les lignes non voisines de votre polygone pour l’intersection
   • les lignes non voisines ne partagent aucun point
   • s’il y a intersection, le polygone s’entrecroise

Optimisation simple qui devrait être la moitié du temps pour les polygones qui ne se croisent pas:

 int count = lines.Count(); for (int l1idx = 0; l1idx < count-1; l1idx++) for (int l2idx = l1idx+1; l2idx < count; l2idx++) { Line2D g = lines[l1idx]; Line2D h = lines[l2idx]; if (g.intersectsLine(h)) { return false; } }