generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: Challenge: 2D Line intersection

Previous Thread :: Next Thread 
awsumpwner27 is not online. awsumpwner27
Joined: 03 Sep 2011
Total Posts: 4389
25 Jan 2013 11:43 PM
Given two points, which make a line, a point and an angle which represent the origin of a ray, and its direction, find if the ray intersects with the line, and where intersects. Reminder: It's all in two dimensions.
Report Abuse
NilPirate is not online. NilPirate
Joined: 31 Jul 2010
Total Posts: 3077
26 Jan 2013 12:09 AM
I'm too lazy to make a script right now, but you can just find the angle of the line and then match the signs of the two angles. If they're both positive or negative, they'll intersect, and if not, they won't. If my math is wrong please tell me. :I
Report Abuse
NilPirate is not online. NilPirate
Joined: 31 Jul 2010
Total Posts: 3077
26 Jan 2013 12:10 AM
No wait, that doesn't work. Forget what I said.
Report Abuse
NilPirate is not online. NilPirate
Joined: 31 Jul 2010
Total Posts: 3077
26 Jan 2013 12:15 AM
Okay, so here's what should work. Find the angle of the line. If the angle of the ray is >= the angle of the line clockwise from vertical and <= angle of line +180, they won't intersect.
Report Abuse
Brandonhare is not online. Brandonhare
Joined: 02 May 2007
Total Posts: 11005
26 Jan 2013 12:18 AM
(assuming neither line is vertical)

Line through points A(x1, y1) and B(x2,y2):
gradient = (y2-y1)/(x2-x1)
line = (y-y1) = m(x-x1)
y = (x-x1)(y2-y1)/(x2-x1) + y1

Line from point C(x3,y3) and angle a:
Gradient = tan(a)
Line = (y-y3) = tan(a)(x-x3)
y = tan(a)(x-x3)+y3

Lines intersect if tan(a) ~= (y2-y1)/(x2-x1)

Solve simultaneously to find point of intersection:
Line through AB = line through C
(x-x1)(y2-y1)/(x2-x1)+y1 = (x-x3)tan(a) + y3
x(y2-y1)/(x2-x1) - xtan(a) = x1(y2-y1)/(x2-x1) -x3tan(a) - y1 + y3
x[(y2-y1)/(x2-x1) - tan(a)] = x1(y2-y1)/(x2-x1)-x3tan(a) - y1 + y3
x = (x1(y2-y1)/(x2-x1)-x3tan(a)-y1+y3)/((y2-y1)/(x2-x1)-tan(a))

Substitute x = (that) into line through C
y = tan(a)((x1(y2-y1)/(x2-x1)-x3tan(a)-y1+y3)/((y2-y1)/(x2-x1)-tan(a))-x3)+y3

Therefore:
Point of intersection =
((x1(y2-y1)/(x2-x1)-x3tan(a)-y1+y3)/((y2-y1)/(x2-x1)-tan(a)) , tan(a)((x1(y2-y1)/(x2-x1)-x3tan(a)-y1+y3)/((y2-y1)/(x2-x1)-tan(a))-x3)+y3)
Report Abuse
Brandonhare is not online. Brandonhare
Joined: 02 May 2007
Total Posts: 11005
26 Jan 2013 12:19 AM
Wait I forgot a ray only goes in one direction.
Report Abuse
Armachedes is not online. Armachedes
Joined: 30 May 2009
Total Posts: 3177
26 Jan 2013 12:26 AM
To qualify on your definition,

We have three coplanar points A, B, and P and an angle "a" relative to some arbitrary direction. Determine if the ray leaving from P along angle "a" intersects line segment AB.

If we give point A coordinates (x1, y1), point B coordinates (x2, y2), and point P coordinates (x3, y3) and simply define "a" to be relative to the positive x axis, then the aforementioned ray will cross AB if there exists a point along that ray that is also in the line AB.

Using the point-slope form of a linear equation, we can see that the line AB is in fact defined by

y - y1 = ((y1 - y2) / (x1 - x2)) (x - x1)

Similarly, using the point-slope form again, but also using tan(a) as the slope of the line (this can be shown to be correct by geometry by constructing the right triangle consisting of angle "a" opposite dy and adjacent to dx), we have the equation

y - y3 = tan(a) (x - x3)

Putting both sides in terms of y and equating the two equations gets the equality

((y1 - y2) / (x1 - x2)) (x - x1) + y1 = tan(a) (x - x3) + y3

The lines do intersect if there is a real solution to this problem. I'm lazy, so I handed this over to W|A, and you can find the algebra there by putting the above equation and then adding "for x". In the end, the solution is:

Assuming

-x1 tan(a)+x2 tan(a)+y1-y2!=0
x1-x2!=0

The solution for x is:

x = (-x1 x3 tan(a)+x2 x3 tan(a)-x1 y2+x1 y3+x2 y1-x2 y3)/(-x1 tan(a)+x2 tan(a)+y1-y2)

Obviously, if you put this value into any two of the equations derived you'll get the y value of the intersection, should it exist.
Report Abuse
Armachedes is not online. Armachedes
Joined: 30 May 2009
Total Posts: 3177
26 Jan 2013 12:30 AM
Oh and you can avoid these calculations altogether by demonstrating that the angle "a" is not "pointed towards" the line. Using the same definition as before, if angle "a" is not between

tan((x1 - x3) / (y1 - y3))

and

tan((x2 - x3) / (y2 - y3))

Then there is no solution.
Report Abuse
Armachedes is not online. Armachedes
Joined: 30 May 2009
Total Posts: 3177
26 Jan 2013 12:30 AM
*those tangents should be inverse tangents.
Report Abuse
xXxMoNkEyMaNxXx is not online. xXxMoNkEyMaNxXx
Joined: 03 Oct 2008
Total Posts: 3120
26 Jan 2013 03:35 AM
This is too easy...
Convert to slope intercept.
y=m1x+b1=m2x+b2
x=(m2-m1)/(b1-b2)
plug x into either original to get y

Now everyone do parabola-plane intersection! In 3D woo!
Parabola is represented by 3 vectors; acceleration, velocity, and position; versus time, plane is represented by normal and origin.
WHEN DOES THING HIT SURFACE
Report Abuse
TeamDman is not online. TeamDman
Joined: 04 Dec 2009
Total Posts: 897
26 Jan 2013 06:21 AM
When God tells it to.

"Don't believe everything you read online" - Abraham Lincoln
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
26 Jan 2013 07:34 AM
Umm... Why hasn't anyone just used ROBLOX's rays?
Report Abuse
awsumpwner27 is not online. awsumpwner27
Joined: 03 Sep 2011
Total Posts: 4389
27 Jan 2013 03:33 AM
There are rays in Roblox, but there are no lines. Even if you simulated a line by having two adjacent bricks, where at least one of them is on an ignore list, depending on the position of the ray relative to the bricks, there would be cases of false positives.

Because you cannot make a part infinitely thin, there will always be faces of the parts that can be intersected that you don't want the ray to intersect. If you have the ray pointing right at the end of the line, and nudge it a bit, the ray could intersect with the face of the brick that isn't representing the line.

Why don't you do some math to check if that case has occurred? Because then you'd be halfway there to making your own line intersection algorithm without Roblox.
Report Abuse
xXxMoNkEyMaNxXx is not online. xXxMoNkEyMaNxXx
Joined: 03 Oct 2008
Total Posts: 3120
27 Jan 2013 03:39 AM
Nobod gon solve my problem? :c
Report Abuse
Gaahl is not online. Gaahl
Joined: 19 Jun 2012
Total Posts: 964
27 Jan 2013 04:20 PM
idk how to do super smart math lol i am 14
Report Abuse
Armachedes is not online. Armachedes
Joined: 30 May 2009
Total Posts: 3177
27 Jan 2013 04:33 PM
An object with acceleration a, velocity v, and position x will have a position x = 0 when:

a!=0 and t = -(sqrt(v^2-2 a x)+v)/a
a!=0 and t = (sqrt(v^2-2 a x)-v)/a
a = 0 and v!=0 and t = -x/v

Nonreal answers indicate the object never has x = 0 in the proper sense of time.

This is not a 3D problem, as it should be obvious by now.

A real 3D problem would be if I ask for the intersection of two functions f and g that are defined as

f(R^2) --> R (aka f(x,y) = z)
g(R^2) --> R (aka g(x,y) = z)

And the math will work out the same perfectly nicely because we can always solve third-degree equations. Same thing for functions in 4D, because quartic functions are generally solvable. However, by the Abel-Ruffini theorem, we can't always solve this case for a 5D intersection. This is basically because an equation in the 5th degree doesn't have a solvable Galois group.

qed
Report Abuse
xXxMoNkEyMaNxXx is not online. xXxMoNkEyMaNxXx
Joined: 03 Oct 2008
Total Posts: 3120
27 Jan 2013 07:46 PM
Here's the problem in vectors:

Vectors:
d - An arbitrary position.
a,v,p - uniform Acceleration, init. Velocity, and init. Position.
n,p0 - Describes the plane. 'n' is a unit vector normal to the plane, 'p0' is a point on the plane.
Scalars: t

Plane: dot(n,d-p0)=0
Parabola: d=a/2*t^2+v*t+p

*Put parabola into plane*
dot(n,a/2*t^2+v*t+p-p0)=0

Solve for t. :D

Remember, this is a VECTOR equation.
Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image