Intersection point for two lines, given endpoints.: lines, two, intersection, point

Intersection point for two lines, given endpoints.

Asked by: etrek

I need code to find the intersection point of two lines given the endpoints of both lines. Tried Liang-Barsky algorithm, with no luck. I'm using C/C++ and openGL.

I did a search of this website first to see if my question had been previously answered, but the resulting webpages, just read: 404: page not found - so if this has been answered in the past, it's not on the site now.

Thanks for your help,
Ethan Deyo

Instant Access to this Solution

Plus...

30 Day FREE access, no risk, no obligation

Collaborate with the world's top tech experts

Unlimited access to our exclusive solution database

Never be left without tech help again

Trusted by hundreds of thousands everyday for fast, accurate and reliable tech support.

"The time we save is the biggest benefit of Experts Exchange to Warner Bros. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange." Mike Kapnisakis, Warner Bros.

"Our team likes having a resource that is more secure than just using Google and most experts using this service really know their stuff. It's nice to look here first versus using Google." Dayna Sellner, Lockheed Martin

"Anytime that I've been stumped with a problem, 9 out of 10 times Experts Exchange has either the accepted solution or an open discussion of the potential solution to the problem." Kenny Red, eBay Inc.

See what Experts Exchange can do for you.

Got a question?

We've got the answer.

Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.

Screenshot of Experts Exchange Knowledgebase

Need individual assistance?

Our experts are ready to help.

If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.

Want to learn from the best?

Read articles from industry experts.

Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.

Working on a long term project?

Store your work and research.

Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.

Join the Community

Give a Little. Get a Lot.

Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.

if lines in this contexts are line sections for 2d space the exact solution comes from deriving the common/intersect point of two line equations

so for 2d ( extra dimmentsion just add an extra param for extra coordinate)

if y=a*x+b and you got the coords of two point belonging to that line like (x1,y1) (x2,y2)

you can derive the a and b params :

y1=a*x1+b
y2=a*x2+b

b=y1-a*x1
y2=a*x2+y1-a*x1 => a=(y2-y1)/(x2-x1) => b=y1-(y2-y1)/(x2-x1)*x1

when you have deriven parameters (for both line - just like the example above )
you can tell that you seek an intersection of
y=a1*x+b1 line, and
y=a2*x+b2 line

x and y of this point is the common point of both lines, so it's the point that will compute both equatuins

yi=a1*xi+b1
yi=a2*xi+b2

a1*xi+b1=a2*xi+b2 => xi=(b2-b1)/(a1-a2)
yi=a1*(b2-b1)/(a1-a2)+b1

oh.. but you know the exact a1,a2,b1,b2 and you can make the equations more useful
just paste the a1 b1 etc values into solution

so.. if 1. line is (x11,y11;x12,y12) second (x21,y21;x22,y22)

xi=(b2-b1)/(a1-a2)
yi=a1*(b2-b1)/(a1-a2)+b1

xi=(y21-(y22-y21)/(x22-x21)*x21-y11-(y12-y11)/(x12-x11)*x11)/((y12-y11)/(x12-x11)-(y22-y21)/(x22-x21))
yi=(y12-y11)/(x12-x11)*(b2-b1)/((y12-y11)/(x12-x11)-(y22-y21)/(x22-x21))+y11-(y12-y11)/(x12-x11)*x11

it will return values or infinties (division by zero - so make code check for 0 in divisions!)
values are the common, and infiniteis (or 0 - in division as you would detect it) are for paralel lines !
ok, but that's not all!

you need to check if your intersection point belongs to your line sections, cos this is common somution of lines - not lines sections intersect !

this is done petty eazyly!

given points are guaranted to belong to the line your line secion lays on, so all you do is check the bound ...

if xi is between x11 and x12 , and yi is between y11 and y12 that means this point belongs to the line sections decribed by these points! so, alll you do is check the boundaries...

if your interscection pooint lays within boundaries of both line sections it is line sections intersection!

if you point lays beond boundaries that means lines intersect (arent pararel) , but sections dont

taht's all but' it

Question

Intersection point for two lines, given endpoints.

Subscribe now for full access to Experts Exchange and get

Instant Access to this Solution

lines

two

intersection

point

Graphics & Game Programming

Trusted by hundreds of thousands everyday for fast, accurate and reliable tech support.

See what Experts Exchange can do for you.

Got a question?

We've got the answer.

Need individual assistance?

Our experts are ready to help.

Want to learn from the best?

Read articles from industry experts.

Working on a long term project?

Store your work and research.

What Makes Experts Exchange Unique?

Trusted by the world's most respected brands.

Faithfully serving IT professionals since 1996.

Related Solutions

Free Tech Articles

Cloud Class Webinars

Join the Community

Give a Little. Get a Lot.

Answers

3 Ways to Join

The Experts

The Experts

Testimonials

Testimonials

Testimonials

Business Clients

Business Clients

In the Press

In the Press

In the Press