Ich habe den Hoey-Shamos-Algorithmus ursprünglich implementiert, er ist jedoch für zukünftige Wartbarkeit zu komplex (ich kann nichts dazu sagen) und er hat nicht richtig berichtet, daher werde ich einen optimierten Brute-Force-Algorithmus verwenden.

Meine Frage ist: Wie kann ich diesen Code optimieren, um verwendbar zu sein?

So wie es aussieht, enthält mein Code eine verschachtelte for-Schleife, die dieselbe Liste zweimal durchläuft.

BEARBEITEN: Linien in ein HashSet verwandelt und zwei foreach-Schleifen verwendet ... ca. 45 Sekunden nach dem Scannen von 10.000 rasiert. Es ist immer noch nicht genug.

foreach (Line2D g in lines)
{                   
foreach (Line2D h in lines)
{
    if (g.intersectsLine(h))
    {
        return false;
    }
}                  

 } // end 'lines' for each loop

Wenn ich meine "intersectsLine ()" - Methode zwinge, zu Testzwecken false zurückzugeben, dauert es immer noch 8 Sekunden, 10.000 Datensätze zu scannen (ich habe 700.000 Datensätze). Das ist zu lang, deshalb muss ich diesen Code optimieren.

Ich habe versucht, Linien aus der Liste zu entfernen, nachdem sie mit allen anderen Linien verglichen wurden. Es gibt jedoch ein Genauigkeitsproblem (keine Ahnung warum) und die Geschwindigkeitssteigerung ist kaum spürbar.

Hier ist meine intersectsLine-Methode. Ich habe einen alternativen Ansatz gefundenHier aber es sieht so aus, als wäre es langsamer mit allen Methodenaufrufen und so weiter. Die Berechnung der Steigung scheint mir nicht viel Rechenarbeit zu kosten. (Korrigieren Sie mich, wenn ich falsch liege?)

public bool intersectsLine(Line2D comparedLine)
{

//tweakLine(comparedLine);
if (this.Equals(comparedLine) ||
    P2.Equals(comparedLine.P1) ||
    P1.Equals(comparedLine.P2))
{
    return false;
}

double firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;

firstLineSlopeX = X2 - X1;
firstLineSlopeY = Y2 - Y1;

secondLineSlopeX = comparedLine.X2 - comparedLine.X1;
secondLineSlopeY = comparedLine.Y2 - comparedLine.Y1;

double s, t;
s = (-firstLineSlopeY * (X1 - comparedLine.X1) + firstLineSlopeX * (Y1 - comparedLine.Y1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
t = (secondLineSlopeX * (Y1 - comparedLine.Y1) - secondLineSlopeY * (X1 - comparedLine.X1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);

if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
    //console.WriteLine("s = {0}, t = {1}", s, t);
    //console.WriteLine("this: " + this);
    //console.WriteLine("other: " + comparedLine);
    return true;
}

return false; // No collision */

}

BEARBEITEN: Der größte Engpass sind die großen Polygone! Ich habe die Ausführung von Polygonen mit mehr als 100 Zeilen ausgeschlossen, und alle über 700.000 Polygone wurden in 5:10 ausgeführt. Welches ist im akzeptablen Bereich! Sicherlich gibt es eine Möglichkeit, festzustellen, ob ein Polygon eine Berechnung wert ist, bevor dieser Code ausgeführt wird. Ich habe Zugriff auf die Eigenschaften XMin, Xmax, YMin und YMax, wenn dies hilfreich ist.

Führen Sie einen weiteren Test durch, bei dem die Anzahl der Polygone auf jeweils unter 1000 Zeilen begrenzt wurde. Es dauerte etwas mehr als eine Stunde.

Ich habe alle Begrenzungen von Polygonen entfernt und es läuft jetzt seit 36 ​​Stunden ... immer noch keine Ergebnisse.

Ein paar Ideen, die ich habe:

-Wenn ich meine Linien-Hashset generiere, haben Sie eine andere Hashset / Liste, die Kandidaten für die Schnittmenge hat. Ich würde nur Linien zu dieser Liste hinzufügen, wenn es eine Möglichkeit für eine Überschneidung gibt. Aber wie eliminiere / füge ich Möglichkeiten hinzu? Wenn es nur drei Linien gibt, die sich möglicherweise mit anderen überschneiden könnten, würde ich 4000 Linien mit 3 anstatt 4000 vergleichen. Das allein könnte einen RIESIGEN Unterschied machen.

-Wenn derselbe Punkt bis auf den ersten und den letzten Punkt zweimal vorkommt, lassen Sie die Ausführung der verschachtelten for-Schleife aus.

Bearbeiten:

Angaben zu den Polygonen: insgesamt 700.000

Es gibt über viertausend Polygone mit 1.000 oder mehr Punkten

Es gibt 2 Polygone mit 70.000 oder mehr Punkten

Ich denke, es ist möglich, dies mit ein bisschen Kreativität auf ungefähr fünfzehn Minuten zu reduzieren.