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

Question

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.

ire_and_curses · Accepted Answer · 2009-10-23 17:24:03Z

6

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.

answered Oct 23, 2009 at 17:24

ire_and_curses

70.6k24 gold badges120 silver badges141 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Richard Simões Over a year ago

All mathematical operations, no matter how simple, are algorithms.

ire_and_curses Over a year ago

@BipedalShark: The point is, this is a computing forum, not a mathematics one. It makes no sense to talk about complexity of this 'algorithm', for example. See e.g. this discussion on meta: meta.stackexchange.com/questions/26339/…

Daniel Pryden Over a year ago

The first subheading in the linked discussion shows the most efficient way that I'm aware of to get from four points to the intersection of those two lines. Most other mathematical discussions of the problem assume you're starting with lines in slope-intercept form (y = mx + b), but in real-world applications, I find you're much more likely to be starting from points instead.

George Co Over a year ago

It does make sense to talk of correctness. A naive translation of the algrebraic solution will not be accurate. Since the question involves floating point arithmetic a computing forum is an appropriate place to ask the question. It is answered in Ch. 33, Computational Geometry, of the 2nd edition of the textbook "Introduction to Algorithms" available from mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/…. As they point out it is important to avoid the division in the algebraic solution.

Frank Krueger · Accepted Answer · 2009-10-23 17:40:26Z

2

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.

answered Oct 23, 2009 at 17:40

Frank Krueger

71.2k48 gold badges165 silver badges212 bronze badges

Comments

CC. · Accepted Answer · 2009-10-23 18:31:41Z

0

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.

answered Oct 23, 2009 at 18:31

CC.

2,9192 gold badges20 silver badges13 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related