Первоначально я реализовал алгоритм Hoey-Shamos, однако он слишком сложен для будущей ремонтопригодности (я не могу сказать об этом), и он не отвечал правильно, поэтому я собираюсь использовать оптимизированный алгоритм перебора.

Мой вопрос: как я могу оптимизировать этот код, чтобы его можно было использовать?

В моем коде есть вложенный цикл for, повторяющий один и тот же список дважды.

РЕДАКТИРОВАТЬ: превратил строки в HashSet и использовал два цикла foreach ... сбрил около 45 секунд от сканирования 10000. Это все еще недостаточно.

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

 } // end 'lines' for each loop

Если я заставлю свой метод intersectsLine () возвращать значение false (для целей тестирования), все равно потребуется 8 секунд для сканирования 10000 записей (у меня 700 000 записей). Это слишком долго, поэтому мне нужно оптимизировать этот кусок кода.

Я попытался удалить строки из Списка после того, как он был сравнен со всеми другими строками, однако есть проблема точности (не знаю почему), и увеличение скорости едва заметно.

Вот мой метод intersectsLine. Я нашел альтернативный подходВот но похоже, что это будет медленнее со всеми вызовами методов и еще много чего. Мне кажется, что вычисление наклона не требует слишком больших вычислений (поправьте меня, если я ошибаюсь?)

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

}

РЕДАКТИРОВАТЬ: Основным узким местом являются большие полигоны! Я исключил запуск полигонов с более чем 100 линиями, и он запустил все 700 000+ полигонов за 5:10. Который находится в приемлемом диапазоне! Конечно, есть способ узнать, стоит ли вычислять многоугольник перед запуском этого кода? У меня есть доступ к свойствам XMin, Xmax, YMin и YMax, если это поможет?

Провел еще один тест, ограничив полигоны до 1000 строк каждый. Прошло чуть больше часа.

Я удалил все ограничения полигонов, и он работает уже 36 часов ... все еще безрезультатно.

У меня есть пара идей:

-Когда я сгенерирую свой хэш-набор строк, есть другой хэш-набор / список, который имеет кандидатов на пересечение. Я бы только добавил строки в этот список, если есть шанс пересечения. Но как мне исключить / добавить возможности? Если бы только три линии могли пересекаться с другими, я бы сравнил 4000 строк против 3 вместо 4000. Одно это может иметь ОГРОМНОЕ различие.

-Если одна и та же точка встречается дважды, за исключением первой и последней точек, пропустите запуск вложенного цикла for.

Редактировать:

Информация о полигонах: всего 700 000

Есть более четырех тысяч полигонов с 1000 или более точек

Есть 2 полигона с 70000 или более точек

Я думаю, что это можно сократить до пятнадцати или около того минут с небольшим творческим потенциалом.