Intereting Posts
Проблема с использованием SQLite: память: с NHibernate «Файл базы данных заблокирован» с помощью System.Data.SQLite Запуск нескольких streamов и отслеживание их из моего приложения .NET Есть ли способ запоминать или материализовать IEnumerable? перетащить на NotifyIcon в лоток в C # BadImageFormatException C # Как получить физический путь сайта на локальном сервере IIS? (из настольного приложения) Отправить почту с помощью localhost SMTP Радиус десятичной точки до ближайшей четверти в C # ASP.NET User Control: не может инициализировать свойство управления пользователем с помощью Eval («…») Распознать специальную папку Windows Shell (т. Е. Получить ее CSIDL) через свой pIDL (теперь определите, совпадают ли pIDL с C #) Загрузка библиотеки UWP в приложение .NET Framework Не удается получить доступ к HttpContext.Current Как искать в 2D-массиве LINQ? C # Threading / Async: запуск задачи в фоновом режиме, в то время как пользовательский интерфейс является интерактивным

Реализация алгоритма грубой силы для обнаружения самопересекающегося многоугольника

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

Мой вопрос: как я могу оптимизировать этот код для использования?

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

EDIT: повернутые строки в 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 = 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 */ } 

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

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

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

Несколько идей, которые у меня есть:

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

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

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


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

Существует более четырех тысяч полигонов с 1000 или более очками

Существует 2 многоугольника с 70 000 или более точек


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

Ваш текущий алгоритм Brute-Force равен O (n ^ 2). Для ваших двух 70 000 линейных полигонов, которые являются частью почти 10 миллиардов операций, не говоря уже о 700 000 других полигонов. Очевидно, что никакой простой оптимизации кода не будет достаточно, поэтому вам понадобится некоторая алгоритмическая оптимизация, которая может снизить ее O (n ^ 2) без чрезмерного усложнения.

O (n ^ 2) происходит от вложенных циклов в алгоритме грубой силы, каждый из которых ограничен n , что делает его O (n * n). Самый простой способ улучшить это – найти способ уменьшить внутренний цикл, чтобы он не был связан или не зависел от n . Таким образом, нам нужно найти способ упорядочить или переупорядочить внутренний список строк, чтобы проверить внешнюю линию, чтобы была проверена только часть полного списка.

Подход, который я принимаю, использует тот факт, что если два сегмента линии пересекаются, то диапазон их значений X должен перекрывать друг друга. Имейте в виду, это не означает, что они пересекаются, но если их диапазоны X не перекрываются, то они не могут пересекаться, поэтому им не нужно проверять их друг против друга. (это относится и к диапазонам значений Y, но вы можете использовать только одно измерение за раз).

Преимущество такого подхода заключается в том, что эти диапазоны X можно использовать для упорядочения конечных точек линий, которые, в свою очередь, могут использоваться в качестве стартовых и остановочных точек, для которых линии должны проверяться для пересечения.

Поэтому мы специально определяем пользовательский class ( endpointEntry ), который представляет значения High или Low X двух точек линии. Эти конечные точки все помещаются в одну структуру списка, а затем сортируются на основе их значений X.

Затем мы реализуем внешний цикл, в котором мы просматриваем весь список так же, как и в алгоритме грубой силы. Однако наш внутренний цикл значительно отличается. Вместо повторного сканирования всего списка строк, чтобы проверить пересечение, мы скорее начнем сканирование сортированного списка конечных точек с конечной точки с высоким значением X строки внешнего контура и закончим его, когда мы пройдем ниже этой конечной точки с той же строкой, что и нижняя конечная точка X. Таким образом, мы проверяем только линии, диапазон значений которых X перекрывает линию внешнего цикла.

ОК, вот class ac #, демонстрирующий мой подход:

 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; } } 

Я не уверен, что истинная сложность выполнения этого алгоритма, но я подозреваю, что для большинства непатологических многоугольников он будет близок к O (n * SQRT (n)), который должен быть достаточно быстрым.


Объяснение логики внутреннего контура:

Внутренняя петля просто сканирует список конечных точек в том же упорядоченном порядке, что и внешний цикл. Но он начнет сканирование с того места, где внешний цикл находится там, где в данный момент находится внешний цикл (который является точкой hiX некоторой строки), и будет проверяться только до тех пор, пока значения endPoint не упадут ниже соответствующего значения loX этой же строки.

Что здесь сложно, так это то, что это невозможно сделать с помощью Enumerator ( foreach(..in pts) внешнего цикла), потому что нет возможности перечислить подсписку списка или запустить перечисление, основанное на другой текущей позиции enums , Поэтому вместо этого я использовал свойства Forward и Backward Links (fLink и bLink), чтобы создать структуру с двойной связью, которая сохраняет отсортированный порядок списка, но я могу инкрементно сканировать без enums списка:

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

В этом случае спецификатор статического стиля for цикла имеет три части: инициализация, условие и приращение-декремент. Выражение инициализации, endpointEntry pLo = pt.fLink; инициализирует pLo с прямой pLo текущей точки в списке. То есть, следующая точка в списке, в порядке убывания сортировки.

Затем выполняется тело внутреннего цикла. Затем применяется приращение-декремент pLo = pLo.fLink , который просто устанавливает текущую точку внутреннего цикла ( pLo ) в следующую нижнюю точку, используя его прямую ссылку ( pLo.fLink ), тем самым продвигая цикл.

Наконец, он (pLo != null) && (pLo.XValue >= pt.lo) после тестирования условия цикла (pLo != null) && (pLo.XValue >= pt.lo) который петли, пока новая точка не равна нулю (что означало бы, что мы были в конце список), и до тех пор, пока значение XValue новой точки еще больше или равно низкому значению X текущей точки внешнего контура. Это второе условие гарантирует, что внутренний контур будет смотреть только на линии, которые перекрывают линию конечной точки внешнего контура.


Теперь мне стало понятнее, что я, вероятно, мог бы обойти всю эту неудобство fLink-bLink, рассматривая вместо этого список конечных точек как массив:

  1. Заполните список с помощью конечных точек
  2. Сортировка списка по XValue
  3. Outer Loop через список в порядке убывания, используя индексный iterator ( i ), вместо перечислителя foreach
  4. (A) Внутренний цикл через список, используя второй iterator ( j ), начиная с i и заканчивая, когда он проходит ниже pt.Lo

Думаю, это будет намного проще. Я могу опубликовать упрощенную версию, если захочу.

есть 2 вещи, чтобы проверить:

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

Простая оптимизация, которая должна составлять половину времени для полигонов, которые не пересекаются:

 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; } }