| Page 1 of 2 |
|
|
 Posted: Thu, 29th Jul 2010 16:47 Post subject: Math problem (line intersection) |
|
 |
My head is full of stuff at the moment and I can't think of a good solution at the moment. Some help would be appreciated 
Problem: Two lines (Line AB & Line CD) have an intersection Point P (well or they might not have one).
Here we can see that the red circle WOULD've been the intersection point from line AB and line CD, but it's not.
What would be the easiest way to calculate if they intersect or not? (I already have the possible intersection point P calculated )
 Spoiler: |
At the moment I do this:
| Code: |
P = intersect(A,B,C,D); // Returns the point P where the lines AB & CD intersect
distance_ab = distance(A,B); //Distance from point A to B (basically length of the line)
distance_cd = distance(C,D);
distance_ap = distance(A,P);
distance_cp = distance(C,P);
quotient_a = absolute(distance_ap / distance_ab); // if >1 means that P is further away than B from A, and therefore can't intersect
quotient_c = absolute(distance_cp / distance_cd);
if (quotient_a>1) && (quotient_b>1)
return true; // Intersects!
else
return false; // Does not intersect! |
But this fails, as you can see in the picture the distance from A to B is greater than A to P and therefore this would result in an intersect, which shouldn't be the case 
|
|
|
| Back to top |
|
|
LeoNatan
☢ NFOHump Despot ☢
Posts: 73220
Location: Ramat HaSharon, Israel 🇮🇱
|
| Posted: Thu, 29th Jul 2010 16:53 Post subject: |
|
|
If you are dealing with only lines, why not just do
minX = min(A.x, B.x)
maxX = max(A.x, B.x)
minY = min(A.y, B.y)
maxY = max(A.y, B.y)
and check bounds for P.x and P.y? You might also need to check bounds with the other line in a similar fashion.
I'm really tired now, so I could be totally off point or there could be a totally faster method staring us in the face and I don't see it. 
|
|
| Back to top |
|
|
Werelds
Special Little Man
Posts: 15098
Location: 0100111001001100
|
| Posted: Thu, 29th Jul 2010 19:35 Post subject: |
|
|
Assuming you can get coordinates for A through D, check the relative positioning?
if (c.x <= a.x <= d.x || d.x <= a.x <= c.x) { check y }
and so on (sorry for the mathematical expression, too lazy to type it out full ^^) ?
Probably best to just throw these into booleans and make a decision based on booleans
boolean aBetweenCandD = (c.x <= a.x <= d.x || d.x <= a.x <= c.x);
Same for the y components and for the coordinates of b, after that it's just specific combinations of booleans. Could also use min/max or whatever instead, as long as it gives you an idea of where A and B are positioned relatively to C and D
@ Leo: I think he doesn't know the position of P, or more accurately: if there even is a P.
|
|
| Back to top |
|
|
zipfero
Posts: 8938
Location: White Shaft
|
|
| Back to top |
|
|
|
|
| Posted: Thu, 29th Jul 2010 19:57 Post subject: |
|
|
| pwerelds wrote: | Assuming you can get coordinates for A through D, check the relative positioning?
if (c.x <= a.x <= d.x || d.x <= a.x <= c.x) { check y }
and so on (sorry for the mathematical expression, too lazy to type it out full ^^) ?
Probably best to just throw these into booleans and make a decision based on booleans
boolean aBetweenCandD = (c.x <= a.x <= d.x || d.x <= a.x <= c.x);
Same for the y components and for the coordinates of b, after that it's just specific combinations of booleans. Could also use min/max or whatever instead, as long as it gives you an idea of where A and B are positioned relatively to C and D
@ Leo: I think he doesn't know the position of P, or more accurately: if there even is a P. |
I know the position of P, even when they should not intersect I can still calculate a possible intersection point of the lines (beams).
And yeah, that would be a possible way but I really want to keep out conditional statements There must be a general way to calculate this no?
Like calculating the direction of the line from a to b and check if p is in the same direction.. |
|
| Back to top |
|
|
Frant
King's Bounty
Posts: 24645
Location: Your Mom
|
| Posted: Thu, 29th Jul 2010 20:23 Post subject: |
|
|
| Quote: | To find the intersection of two straight lines:
1. First we need the equations of the two lines. If you do not have the equations, see Equation of a line - slope/intercept form and Equation of a line - point/slope form (If one of the lines is vertical, see the section below).
2. Then, since at the point of intersection, the two equations will have the same values of x and y, we set the two equations equal to each other. This gives an equation that we can solve for x
3. We substitute that x value in one of the line equations (it doesn't matter which) and solve it for y.
This gives us the x and y coordinates of the intersection. |
http://www.mathopenref.com/coordintersection.html
Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn!
"The sky was the color of a TV tuned to a dead station" - Neuromancer
|
|
| Back to top |
|
|
|
|
|
| Back to top |
|
|
|
|
| Posted: Thu, 29th Jul 2010 20:35 Post subject: |
|
|
| Frant wrote: | | Quote: | To find the intersection of two straight lines:
1. First we need the equations of the two lines. If you do not have the equations, see Equation of a line - slope/intercept form and Equation of a line - point/slope form (If one of the lines is vertical, see the section below).
2. Then, since at the point of intersection, the two equations will have the same values of x and y, we set the two equations equal to each other. This gives an equation that we can solve for x
3. We substitute that x value in one of the line equations (it doesn't matter which) and solve it for y.
This gives us the x and y coordinates of the intersection. |
http://www.mathopenref.com/coordintersection.html |
Thanks but I already have the point of intersect. This sample you gave is for infinite beams. A line has a start and an ending point, therefor you need to check if the checkpoint is on the line. |
|
| Back to top |
|
|
LeoNatan
☢ NFOHump Despot ☢
Posts: 73220
Location: Ramat HaSharon, Israel 🇮🇱
|
| Posted: Thu, 29th Jul 2010 21:13 Post subject: |
|
|
| pwerelds wrote: | | @ Leo: I think he doesn't know the position of P, or more accurately: if there even is a P. |
There is always a P which can be calculated.  Only if the two lines are parallel, but then he can catch a few NaNs and know there is no intersection.
| PumpAction wrote: | And yeah, that would be a possible way but I really want to keep out conditional statements There must be a general way to calculate this no?
Like calculating the direction of the line from a to b and check if p is in the same direction.. |
I don't think there is. Your direction theory is still not valid because you still have to check bounds. Direction is only good for a further checking of other properties of the intersection. |
|
| Back to top |
|
|
|
|
| Posted: Thu, 29th Jul 2010 21:22 Post subject: |
|
|
Yeah, lines (that are infinite), if not parallel, will always intersect (you can show that by solving simple 2x2 system y=ax+b), but line segments need not intersect...
"Quantum mechanics is actually, contrary to it's reputation, unbeliveably simple, once you take the physics out."
Scott Aaronson | chiv wrote: | | thats true you know. newton didnt discover gravity. the apple told him about it, and then he killed it. the core was never found. |

|
|
| Back to top |
|
|
LeoNatan
☢ NFOHump Despot ☢
Posts: 73220
Location: Ramat HaSharon, Israel 🇮🇱
|
| Posted: Thu, 29th Jul 2010 23:05 Post subject: |
|
|
|
|
|
| Back to top |
|
|
Lutzifer
Modzilla
Posts: 12740
Location: ____________________ **** vegan zombie **** GRRAAIIINNSS _______
|
| Posted: Thu, 29th Jul 2010 23:37 Post subject: |
|
|
to make it easier to think about it, why not assume we rotate all the lines so CD is parallel to the y-axis. Then it should be easy to solve for any given second line AB, because you only need to be dealing with x-axis value comparisons of the AB start- and end-points with the intersection point of CD with the x-axis. Because it is either part of the AB interval or not. So computing the distance of P to A and B should be sufficient (if P is bigger as A and also bigger as B (or both smaller) its not on the line; if it is inbetween it is on the line. So if (A>P>B) or (A<P<B) should be all you need to check)
By using distances and quotients you might be losing the directionality-information, but i m too lazy to think about what your computations above actually represent. But since you already know the coordinates for AB and P, cant you just check if P as a coordinate is a possible value of the interval of values between A and B (which would be the solution i described above basically)?
|
|
| Back to top |
|
|
|
|
| Posted: Thu, 29th Jul 2010 23:45 Post subject: |
|
|
Yes I thought of that one too but I would need to compute the linear function of the lines and that would cost me some more time I already switched to this calculation method because I wanted to save a little bit more computing time
But basically your thoughts are right, actually measuring the distance from a to b and a to p is that what you say, I reduce everything to a single dimension I just need to check for + and - growth in direction of B and P. If P growth != B growth then no intersect
Problem with distances is just... They are always positive :'(
|
|
| Back to top |
|
|
Lutzifer
Modzilla
Posts: 12740
Location: ____________________ **** vegan zombie **** GRRAAIIINNSS _______
|
| Posted: Fri, 30th Jul 2010 00:00 Post subject: |
|
|
yup, thats why one should always stay away from those bastards! Keep your distance from distances!!! 
|
|
| Back to top |
|
|
LeoNatan
☢ NFOHump Despot ☢
Posts: 73220
Location: Ramat HaSharon, Israel 🇮🇱
|
| Posted: Fri, 30th Jul 2010 00:01 Post subject: |
|
|
What about my algorithm?
|
|
| Back to top |
|
|
|
|
| Posted: Fri, 30th Jul 2010 00:04 Post subject: |
|
|
Could you clear it up leo? The first one I mean How exactly will this help me to determine if an intersection occurred
|
|
| Back to top |
|
|
LeoNatan
☢ NFOHump Despot ☢
Posts: 73220
Location: Ramat HaSharon, Israel 🇮🇱
|
| Posted: Fri, 30th Jul 2010 00:12 Post subject: |
|
|
Which one? The min/max or the Sweep Line?
The first is very easy but a lot of checks. You know where P is, so check if it is in the bounds set by A and B (by comparing P.x and P.y to min(A,B) and max(A,B). If the P is within the bounds then it has to be on the AB line segment, so indeed there is an intersection. Depending on your needs, you might also want to check boundaries with the CD line segment as well, to determine if P is on that line segment as well.
Sweep Line is a lot more elegant and also solves the problem for multiple lines, whereas my initial solution is naive - it grows to huge amounts of checks.
|
|
| Back to top |
|
|
LeoNatan
☢ NFOHump Despot ☢
Posts: 73220
Location: Ramat HaSharon, Israel 🇮🇱
|
| Posted: Fri, 30th Jul 2010 00:16 Post subject: |
|
|
On second thought, you want the P to be on both line segments, so you will need to check if P is on AB and also if on CD.
Also to explain the obvious, because P is not a randomly generated point but a point that is calculated from the two [imaginary] lines, if it falls withing the bounds, it is guaranteed to be on the line segment.
|
|
| Back to top |
|
|
|
|
| Posted: Fri, 30th Jul 2010 00:55 Post subject: |
|
|
Sounds logic but I must see how much of a performance hit that would be.
|
|
| Back to top |
|
|
LeoNatan
☢ NFOHump Despot ☢
Posts: 73220
Location: Ramat HaSharon, Israel 🇮🇱
|
| Posted: Fri, 30th Jul 2010 01:07 Post subject: |
|
|
Shouldn't be that much for two line segments. You already calculate distances, etc. which are more costly operations than comparison.
Use the Math.min and Math.max which should be optimized on browsers.
| Code: | function isOnSegment(x, y, ax, ay, bx, by)
{
//assumption - x,y is guaranteed to be on the imaginary infinite line going through (ax,ay) (bx,by).
if(x >= Math.min(ax,bx) && x <= Math.max(ax,bx) && y >= Math.min(ay,by) && y <= Math.max(ay,by))
return true;
return false;
}
px = ...;
py = ...;
if(isOnSegment (px, py, ax, ay, bx, by) && isOnSegment (px, py, cx, cy, dx, dy))
//intersection
|
|
|
| Back to top |
|
|
|
|
| Posted: Fri, 30th Jul 2010 01:19 Post subject: |
|
|
Sounds good! Thanks will implement this later and upload it
|
|
| Back to top |
|
|
|
|
| Posted: Fri, 30th Jul 2010 02:27 Post subject: |
|
|
My eyes......................................................
Ryzen 5 3600 cpu@3.60 Mhz.
hyper x 32 gb ddr 4 memory.
Msi Carbon gaming pro ac motherboard.
Evga 600 psu.
Msi Armour rx 8 gb 5700 Graphic card.
Ps4 Standard 500gb.
Lg 4k 42 inch tv.
Oculus Quest 2.
|
|
| Back to top |
|
|
Lutzifer
Modzilla
Posts: 12740
Location: ____________________ **** vegan zombie **** GRRAAIIINNSS _______
|
| Posted: Fri, 30th Jul 2010 18:04 Post subject: |
|
|
|
|
|
| Back to top |
|
|
|
|
| Posted: Fri, 30th Jul 2010 18:07 Post subject: |
|
|
Click the link on my sig
I had a tile based level architecture in mind, but I don't want that limitations anymore. I want to make a polygon based level architecture so that my figures have more freedom in their movement
And many connected lines make a polygon And this line intersection is for my collision detection.
|
|
| Back to top |
|
|
Lutzifer
Modzilla
Posts: 12740
Location: ____________________ **** vegan zombie **** GRRAAIIINNSS _______
|
| Posted: Fri, 30th Jul 2010 18:10 Post subject: |
|
|
i already thought that it might be for a game's collision detection, because otherwise you usually dont have to compute stuff like that. =)
if you need music for your game, tell me
|
|
| Back to top |
|
|
|
|
| Posted: Fri, 30th Jul 2010 18:32 Post subject: |
|
|
Hell yeah, I'll need some porny sounds
|
|
| Back to top |
|
|
|
|
| Posted: Sat, 31st Jul 2010 18:40 Post subject: |
|
|
So thanks to Leo's great idea of checking if the resulting point P is within the bounds of the imaginary rectangle opened between A and B, hereby I present version 3 of turbo_intersect
(btw. I added a resulting line, that resembles the result of the forces from A->B and C->D)
Basically the yellow line displays where the ball would move to, if two billiard balls hit each other
http://www.webwerkz.de/math/turbo_intersect_3.html
|
|
| Back to top |
|
|
Frant
King's Bounty
Posts: 24645
Location: Your Mom
|
| Posted: Sat, 31st Jul 2010 19:06 Post subject: |
|
|
|
|
|
| Back to top |
|
|
|
|
| Posted: Sat, 31st Jul 2010 19:28 Post subject: |
|
|
You are looking at it a bit simplified, but I'll go with the flow (look what Frant said )... Good start
"Quantum mechanics is actually, contrary to it's reputation, unbeliveably simple, once you take the physics out."
Scott Aaronson | chiv wrote: | | thats true you know. newton didnt discover gravity. the apple told him about it, and then he killed it. the core was never found. |

|
|
| Back to top |
|
|
|
|
| Posted: Sat, 31st Jul 2010 21:16 Post subject: |
|
|
Give us some insight
|
|
| Back to top |
|
|
| Page 1 of 2 |
All times are GMT + 1 Hour |
