@victor1234
IT: Компьютерное зрение, linux, с++

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

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

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

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

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

Разработкка идет на с++ под OpenCV, но, понятное дело, готов принять на других языках, словесные описания и просто ссылки
  • Вопрос задан
  • 6386 просмотров
Пригласить эксперта
Ответы на вопрос 3
m03r
@m03r
Лучше проверять пары отрезков на пересечение.
Разумеется, не надо проверять соседние отрезки, а также уже проверенные пары.

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

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

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы