Первоначально я реализовал алгоритм Hoey-Shamos, однако он слишком сложен для поддержки в будущем (у меня нет права голоса в этом), и он не дает правильных отчетов, поэтому я собираюсь использовать оптимизированный алгоритм грубой силы.
Мой вопрос: как я могу оптимизировать этот код, чтобы его можно было использовать?
В нынешнем виде мой код содержит вложенный цикл for, дважды повторяющий один и тот же список.
РЕДАКТИРОВАТЬ: Превратил строки в HashSet и использовал два цикла foreach ... сократил около 45 секунд сканирования 10 000. Этого все еще недостаточно.
foreach (Line2D g in lines)
{
foreach (Line2D h in lines)
{
if (g.intersectsLine(h))
{
return false;
}
}
} // end 'lines' for each loop
Если я заставлю свой метод «intersectsLine()» возвращать false (в целях тестирования), сканирование 10 000 записей все равно займет 8 секунд (у меня 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 полигона с 70 000 и более точек
Я думаю, что можно сократить это время до пятнадцати минут или около того, проявив немного творчества.
PriorityQuatree<T>реализацию. - person Simon Mourier schedule 01.10.2013HasItemsIntersecting,GetItemsIntersecting,GetItemsInsideи т. д. - person Simon Mourier schedule 01.10.2013