Пересечение между двумя кривыми

Question

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

Учитывая две кривые C1 и C2, определенные точками N1 и N2, соединенными прямыми, получить все пересечения C1 с C2.Обе кривые не пересекаются.

Я пробовал несколько подходов, но пока ни один из них не работает.Есть предположения?

Answer 1

Самый простой способ - проверить все пары сегментов, по одному на каждой кривой. Если это слишком медленно, попробуйте полосовое дерево . Нижеприведенный документ можно найти на сайте автора .

Баллард, Д. Х. (1981), Полосатые деревья: иерархическое представление для кривые, связи АСМ, т.24 п.5,310-321

Answer 2

Поскольку ваши кривые состоят из отрезков, я бы предложил использовать пространственное дерево (например, quadtree ) для проверки только тех сегментов, которые находятся рядом друг с другом.Это снизит сложность вашего алгоритма с O(N1 N2) до O(N log N) (где N = N1 + N2), предполагая, что число очень близких пересечений мало.

Кроме этого, вы можете найти пересечения в таким образом .