Solved

Intersection point for two lines, given endpoints.

Posted on 2004-09-29
4
8,079 Views
Last Modified: 2013-12-26
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
0
Comment
Question by:etrek
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
4 Comments
 
LVL 3

Accepted Solution

by:
str_ek earned 250 total points
ID: 12190737
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


0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 250 total points
ID: 12202518
0

Featured Post

On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
Michael from AdRem Software outlines event notifications and Automatic Corrective Actions in network monitoring. Automatic Corrective Actions are scripts, which can automatically run upon discovery of a certain undesirable condition in your network.…
Michael from AdRem Software explains how to view the most utilized and worst performing nodes in your network, by accessing the Top Charts view in NetCrunch network monitor (https://www.adremsoft.com/). Top Charts is a view in which you can set seve…

617 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question