Эффективный, правильный и оптимизированный алгоритм поиска пересечения между двумя линиями

Question

Какой самый эффективный алгоритм поиска точки пересечения между двумя линиями?

Вам дается четыре очка A, B, C, D. Найдите точку пересечения между AB и CD. Оптимизируйте алгоритм как можно больше.

Для этого есть два подхода: один использует точечное произведение, а другой использует форму пересечения по наклонной линии для линии. какой из них лучше.

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

Answer 1

Для этого не требуется никакого алгоритма, только решение двух пересекающихся линий . Это основная математическая проблема, а не вычислительная (это просто алгебраические манипуляции).

Тем не менее, вот обсуждение , которое вы должны найти полезным.

Answer 2

Я предпочитаю веб-сайт мистера Бурка для таких вопросов. Вот его статья по линии intersectoin:

Точка пересечения двух линий

Учитывая, насколько это тривиально, оптимизировать довольно сложно.

Полагаю, лучшее, что вы можете сделать, - это убедиться, что все находится в кэше ЦП, чтобы вы могли выполнять эти математические операции на полной скорости. У вас может возникнуть искушение заранее вычислить некоторые из различий (P2 - P1), но в этом мире трудно сказать, будет ли поиск в памяти этого быстрее, чем просто выполнение самого вычитания. Процессоры могут выполнять вычитание и умножение за 1 операцию, тогда как поиск памяти, если они пропустили кеш, может занять на пару порядков больше.

Answer 3

Это не так тривиально.

Насколько я помню, пример Паскаля (http://actionsnippet.com/?p=956) не работает с коллинеарными точками.

Мне не удалось найти правильно реализованный алгоритм, поэтому мне пришлось написать собственный.