What is the most efficient algorithm to find intersection point between two lines?
You are given four points A, B , C , D. Find the intersection point between AB and CD. Optimize the algorithm as much as you can.
There are two approach for this, one is using dot product and another is using slope intercept form for line. which one is better.
This might sound a repeated question but what I want to ask is which approach is better and most efficient with better complexity.
This doesn't require any algorithm, just the solution of two intersecting lines. That's a basic mathematics problem, not a computing one (it's just algebraic manipulation).
That said, here's a discussion you should find helpful.
I prefer Mr. Bourke's website for these types of questions. Here's his article on line intersectoin:
Intersection point of two lines
Given how trivial this is, it's pretty tough to optimize.
I guess the best you can do is make sure that everything is in the CPU cache, that way you can run those math ops at full speed. You may be tempted to precompute some of the differences (P2 - P1), but it's hard to say in this world whether the memory lookup for that will be any faster than just performing the subtraction itself. CPUs can do subtraction and multiplication in 1 op whereas memory lookups, if they miss the cache, can take a couple orders of magnitude longer.
It's not that trivial.
As far I remember the Pascal example ( http://actionsnippet.com/?p=956 ) does not work with collinear points.
I was not able to find a correctly implemented algorithm, so I had to write my own.