Алгоритм поиска самопересечений двумерного контура

Question

[Виктор]

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

Требуется найти координаты точек его самопересечения, причем быстро.

Пока из того, что нашел/додумался:
1. Найти прямоугольник, описаный вокруг контура.
2. Создать массив размером с этот прямоугольник
3. И отрисовывыть поточечно туда контур
4. Проверяя попадает ли новая точка точно на страрую
5. И нет ли рядом других, на случай диагонального перечесение.

Может эффективнее проверять соседство после отрисовки, если контур плотный.

Разработкка идет на с++ под OpenCV, но, понятное дело, готов принять на других языках, словесные описания и просто ссылки

Answer 1

[m03r]

Лучше проверять пары отрезков на пересечение.
Разумеется, не надо проверять соседние отрезки, а также уже проверенные пары.

Ещё будет проблема, если два отрезка частично совпадают: тогда множество точек пересечения бесконечно.

Про проверку отрезков можно почитать на RSDN, там и примеры кода есть. Ну или нагуглить что ещё.

Answer 2

[molekyla]

Чисто математический подход:
http://www.exponenta.ru/educat/systemat/lapteva/3a.asp
Не знаю будет ли работать с дискретными данными, но на первый взгляд вполне реализуемо

Answer 3

[Wataru]

Простое, но медленное решение - проверять на пересечение все пары отрезков. Это работает за квадратичную сложность от количества отрезков в контуре.
Проверка пересечения двух отрезков делается довольно просто. Можно пересечь 2 прямые, заданные параметрически (2 линейных уравнения, решение на бумажке), а потом проверить, что точка пересечения на каждой прямой внутри отрезка (можно задать параметрическое уравнение прямой так, что отрезок соответствует параметрам от 0 до 1). Другой, более быстрый способ с помощью векторного произведения. Надо проверить, что точки каждого отрезка лежат по разные стороны от прямой, на которой лежит другой отрезок.

Есть сложное, но более быстрое решение задачи - с помощью заметающей прямой. Подробно описанно вот тут: e-maxx.ru/algo/intersecting_segments
Работает за O(n log n), где n - количество отрезков. Его, правда, придется чуть-чуть подкорректировать, чтобы не учитывать пересечения соседних отрезков.