Początkowo zaimplementowałem algorytm Hoeya-Shamosa, jednak jest on zbyt złożony, aby można go było w przyszłości utrzymać (nie mam w tym nic do powiedzenia) i nie raportował poprawnie, więc zoptymalizowany algorytm brute force jest tym, z czego będę korzystać.

Moje pytanie brzmi: jak mogę zoptymalizować ten kod, aby był użyteczny?

W obecnej postaci mój kod zawiera zagnieżdżoną pętlę for, powtarzającą tę samą listę dwa razy.

EDYCJA: Przekręciłem linie w HashSet i użyłem dwóch pętli foreach ... ogoliłem około 45 sekund skanowania 10.000. To wciąż za mało.

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

 } // end 'lines' for each loop

Jeśli wymuszę metodę „intersectsLine ()”, aby zwrócić false (w celach testowych), skanowanie skanowanych 10 000 rekordów trwa nadal 8 sekund (mam 700 000 rekordów). To za długo, więc muszę zoptymalizować ten fragment kodu.

Próbowałem usunąć linie z Listy po porównaniu z wszystkimi innymi liniami, jednak istnieje problem z dokładnością (nie wiem dlaczego), a wzrost prędkości jest ledwo zauważalny.

Oto moja metoda intersectsLine. Znalazłem alternatywne podejścietutaj ale wygląda na to, że będzie wolniejszy przy wszystkich wywołaniach metod i tym podobnych. Obliczanie nachylenia nie wydaje mi się, aby wymagało to zbyt dużej mocy obliczeniowej (popraw mnie, jeśli się mylę?)

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 */

}

EDYTOWAĆ: Głównym wąskim gardłem są duże wielokąty! Wykluczyłem prowadzenie wielokątów z więcej niż 100 liniami i uruchomiłem wszystkie 700 000 + wielokątów w 5:10. Który jest w dopuszczalnym zakresie! Z pewnością istnieje sposób, aby sprawdzić, czy wielobok jest warty obliczenia przed uruchomieniem tego kodu? Mam dostęp do właściwości XMin, Xmax, YMin i YMax, jeśli to pomaga?

Przeprowadził kolejny test, ograniczając wielokąty do poniżej 1000 linii każdy. Trwało to trochę ponad godzinę.

Usunąłem wszystkie ograniczenia wielokątów i działa już 36 godzin ... nadal nie ma wyników.

Mam kilka pomysłów:

-Gdy generuję hashset linii, mam inny zestaw / listę, która ma kandydatów do przecięcia. Dodałbym tylko linie do tej listy, jeśli jest szansa na skrzyżowanie. Ale jak mogę wyeliminować / dodać możliwości? Jeśli są tylko trzy linie, które mogłyby się przecinać z innymi, porównałbym 4000 linii z 3 zamiast z 4000. Tylko to mogłoby spowodować OGROMNĄ różnicę.

-Jeśli ten sam punkt występuje dwukrotnie, z wyjątkiem pierwszego i ostatniego punktu, pomiń uruchamianie zagnieżdżonej pętli for.

Edytować:

Informacje o wielokątach: 700 000 łącznie

Istnieje ponad cztery tysiące wielokątów z 1000 lub więcej punktów

Istnieją 2 wielokąty z 70 000 lub więcej punktów

Myślę, że jest to możliwe, aby uzyskać to do piętnastu minut przy odrobinie kreatywności.