CODEWITHSUNDEEP
algorithm
rkb
rkb

Reputation: 11231

Efficient, correct and optimized algorithm to find intersection between two lines

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.

Upvotes: 0

Views: 6599

Answers (3)

CC.
CC.

Reputation: 2899

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.

Upvotes: 0

Frank Krueger
Frank Krueger

Reputation: 71053

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.

Upvotes: 2

ire_and_curses
ire_and_curses

Reputation: 70240

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.

Upvotes: 6

Related Questions