Как реализовать проверку самопересечения ломаной?

Question

пишу программу, определяющую, является ли заданная в пространстве ломаная линия самопересекающейся. С клавиатуры задаются количество звеньев и координаты вершин по порядку. Единственный алгоритм, который пока пришёл в голову - это попарная проверка на пересечение каждого с каждым отрезка через решение системы уравнений, состоящей из двух уравнений плоскости в пространстве. Но подозреваю, что задачу можно решить легче, поскольку само по себе решение системы с шестью переменными - не такая простая задача, а для количества звеньев в несколько тысяч (надо сгенерировать именно такие тестовые наборы) работать решение будет занимать слишком долго и много по памяти. Какой алгоритм можно использовать?

Answer 1

что-то мне кажется задача легче O(n^2) не решается

например если ломанная представляет собой спираль, то никакими иными способами как проверка всех её звеньев задачу не решить

опять же может и есть какие-то оптимизации, то они лишь влияют на коэффициентик около n^2

так что да - алгоритм заключается в том чтобы

пройтись по всем звеньям кроме последнего -
```
 for (int i = 0; i < n - 1; i ++)
```
пройти по всем звеньям от текущего до последнего -
```
 for (int j = 0; j < n; j ++)
```
проверить отрезки [i], [j] на пересечение

https://e-maxx.ru/algo/segments_intersection_checking

в качестве оптимизации - не надо проверять отрезки, соединяющиеся с текущим, т.е.
```
 if ((i == j) || (abs(i - j) == 1))
     continue
```
в качестве оптимизации - не надо проверять отрезки до проверенного отрезка (поскольку их уже проверили), т.е.
```
 for (int j = i + 1; j < n; j ++)
```

условия 4) и 5) приводят к тому, что надо делать

    for (int i = 0; i < n - 1; i ++)
        for (int j = i + 2; i < n; j ++)

Answer 2

Есть решение за O(n^2)(оно вами и описывалось). Смотрим на каждую пару отрезков, если хоть одна из этих пар пересекается, то ломаная самопересекающаяся, иначе - нет.

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


for (int first = 0; first < n - 1; first++) {
    for (int second = 0; second < n - 1; second++) {
       if (first != second) //  говорим, что отрезки разные
          // в line содержится структурка, которая хранит координаты двух точек
          if (intersect (line[i], line[i+1], line[j], line[j+1]) {
                // нашли пересечение
          }
    }
}

Функцию пересечения отрезков можете подсмотреть здесь.

БЛОГ НА HUSL

Как реализовать проверку самопересечения ломаной?

Ответы (2 шт):