Point of Intersection

If you have questions about any aspect of QBasic programming, or would like to help fellow programmers solve their problems, check out this board!

Moderators: Pete, Mods

Post Reply
User avatar
Zamaster
Veteran
Posts: 174
Joined: Wed Jun 15, 2005 1:51 pm
Contact:

Point of Intersection

Post by Zamaster » Sat Feb 25, 2006 11:17 pm

Can anybody help me find the point of intersection between TWO LINE SEGMENTS. If I only have (x1, y1, x2, y2) of both line segments, what is the formula to get two variables, px and py. Is there a way to test beforehand if the lines cross? And can nobody post the way you do it on paper, Im aware how to use substitution to get the point. I came up with a formula:

xp = (y1A + (y1B * -1)) / (xslopeB - xslopeA)
yp = xslopeA * xp + y1A

where y1A is the starting y for the first line and y1B is the starting y for the second line. xslopeA is the x slope for the first line and xslopeB is the x sloep for the second line. However this equation doesnt work when both of the two line's y1 coordinates are equal. Im not sure whether or not it works if the xslopes are the same. Can anybody come up with a more reliable equation IN CODE FORM and NOT AS YOU'D DO IT ON PAPER that would return two variables, xp and yp that hold the point of intersection as well as a way to know whether or not the two line segmants cross? This may sound like alot to ask but Im not much for math and Im trying to create a system of collision that's flawless. Thanks!
C:\DOS
C:\DOS\RUN
RUN\DOS\RUN

User avatar
Zim
Veteran
Posts: 98
Joined: Mon Dec 05, 2005 4:31 pm
Location: Wisconsin, USA
Contact:

Post by Zim » Mon Feb 27, 2006 12:53 pm

This is not a trivial problem! This is the sort of thing I did for 20 years with my programs. Surveyors run into this sort of thing all the time.

I don't have time to check your math, but if it works for most cases it's probably right. It's easier to find an intersection for two lines, than for two line segments, for sure.

I think the way to approach it is just as you have; first see if the two LINES intersect, then test to make sure both of the SEGMENTS actually contain the intersection point.

Also, of course, if the slopes are the same the equation doesn't work. If the slopes are the same the lines are parallel and there is no intersection.
--- Zim ---
--- Time flies like an arrow, but fruit flies like a banana ---

User avatar
Zamaster
Veteran
Posts: 174
Joined: Wed Jun 15, 2005 1:51 pm
Contact:

Post by Zamaster » Mon Feb 27, 2006 3:09 pm

First of all, let me fix my equation...

xp = (y1A - y1B) / (xslopeB - xslopeA)
yp = xslopeA * xp + y1A

Im not sure how I got the first one. Im still working on it, the first thing I need to do is get this equation to compensate for similar y1's. Then I need to come up with a way to check if they do cross in the first place. This shouldnt be too hard though, I can waste as many math classes as I need to on this one. Im still more than open to suggestions!
C:\DOS
C:\DOS\RUN
RUN\DOS\RUN

User avatar
Quibbler
Coder
Posts: 16
Joined: Tue Jan 24, 2006 7:29 am
Location: Trinidad and Tobago

Post by Quibbler » Tue Feb 28, 2006 11:08 am

Ok so this will find the intersection of two lines. If the Y,X answer is outside the range of either of the two line segments (as it is in my example) then they do not inersect.

Code: Select all

y1a = 10: x1a = 20: y2a = 20: x2a = 30
y1b = 5: x1b = 7: y2b = 15: x2b = 22
ma = (y1a - y2a) / (x1a - x2a)
ca = y2a - ma * x2a
mb = (y1b - y2b) / (x1b - x2b)
cb = y2b - mb * x2b
X = (cb - ca) / (ma - mb)
Y = ma * X + ca
PRINT Y; X

User avatar
Patz QuickBASIC Creations
Veteran
Posts: 399
Joined: Wed Mar 02, 2005 9:01 pm
Location: Nashville, Tennessee
Contact:

Post by Patz QuickBASIC Creations » Tue Feb 28, 2006 4:47 pm

This reminds me of the INTERSECT feature on my TI-83+. :lol:

User avatar
Zamaster
Veteran
Posts: 174
Joined: Wed Jun 15, 2005 1:51 pm
Contact:

Post by Zamaster » Tue Feb 28, 2006 9:31 pm

What do you mean by, "outside the range of the two lines"? Do you mean if the point doesnt fall on either line?
C:\DOS
C:\DOS\RUN
RUN\DOS\RUN

zanzibar
Coder
Posts: 21
Joined: Tue Feb 28, 2006 10:03 pm

Post by zanzibar » Thu Mar 02, 2006 3:09 pm

I worked on the same thing! Try a book on vector calc for more info.

my game had a round ship that would bounce of walls. I projected the current path of my ship, then if that short projection crossed a line, it bounced back. never could finish that game though...

basically i had two line segments: the projected path and the wall.

User avatar
Zamaster
Veteran
Posts: 174
Joined: Wed Jun 15, 2005 1:51 pm
Contact:

Post by Zamaster » Sat Mar 04, 2006 9:37 pm

Yeah, thats pretty much what Im doing. Im working on a Sand Simulator and I need the collision to be perfect. So the sand doesnt go through specified "surfaces"-(just lines that act as barriers), I need to project a line segment from the sand to its next position and a line segment of the surface and check to see if they intersect and if so, where. Oh yeah, could you show me your code (darklink) for your collision/intersection thing?
C:\DOS
C:\DOS\RUN
RUN\DOS\RUN

User avatar
Zamaster
Veteran
Posts: 174
Joined: Wed Jun 15, 2005 1:51 pm
Contact:

Post by Zamaster » Sat Mar 04, 2006 10:25 pm

Hehehe, I figured it out. After about 10 mins of tough "sheet of paper staring", I decided what Needed to be done. Take angles from points of line A and B. Find the distance from points on line A and B, depending on the angles and distances one of the points (must be greater from point Axy1 to Axy2 then Axy1 to Bxy*). Then just use my formula to calculate the intersection point. I know im rushing and this probably makes no sense but Ill explain in detail later when I have the time.
C:\DOS
C:\DOS\RUN
RUN\DOS\RUN

Post Reply