Hello ATer's, I'm here with another math puzzle for you (that which when solved will benefit the work load on one of my scratch programs, and could also be useful for others)

The Pieces
We are given:
-The slope of a line L.
-The point P1, which is on line L.
-The center of a circle C.
-The radius of circle C.
-We know that L intersects C at 1 (when its tangent) or 2 points. L does not miss C (they have been together for a long time )

The Puzzle

Some Background/context
Here is how I came about this puzzling puzzle:
I am working on a plat-former where the player can swing on a rope. Here is how it works:

That “goTo point where:…” code is how this problem came about. The circle in our puzzle is the circle created by the rope, the center of C is the grapple point and the radius is the rope length. The line is the trajectory of our player, the slope of L is:

and P1 is (playerX, playerY)

For now, here is what I do for that “goTo point where:…” code:

This works, but takes a lot of calculations for my program. I know we can do this in one calculation using math. Only, it is not an easy calculation to calculate. Here is where I got before giving up and turning to the famous ATer's:

1. (x - Cx)^2 + (y - Cy)^2 = r^2 // equation of a circle
2. (x - grappleX)^2 + (y - grappleY)^2 = (rope length)^2 // Substituting our variables into circle equation from line 1

3. y = mx + b // line equation
4. b = y - mx // solving for b from line equation on line 3
5. b = playerY - m(playerX) // substituting our variables into equation for b from line 4
6. y = (yVelocity/xVelocity) (x) + playerY - (yVelocity/xVelocity) (playerX) // substituting our variables and our new b from line 5 into line equation from line 3

7. y = sqrt((rope length)^2 - (x - grappleX)^2) + grappleY // Solving for y from our circle equation on line 2
8. sqrt((rope length)^2 - (x - grappleX)^2) + grappleY = (yVelocity/xVelocity) (x) + playerY - (yVelocity/xVelocity) (playerX) // setting our equations from line 6 and line 7 to equal each other, since we know they intersect at the same point.
9…. // I would try solving for x from the equation on line 8, but this is where I gave up. Just look at that narly beast!

There are probably easier ways, but I did this project ages ago which calculates the intersection of a line and a circle.

The source of the formula used is in the notes.

The relevant script is far right of the scripts section (there's only one sprite).

It uses two points on the line rather than point+slope, but should be adaptable.

The (near) point you need should correspond to “x inter near”, “z inter near”.

Can't remember how well it copes with the tangent case.

PutneyCat wrote:

There are probably easier ways, but I did this project ages ago which calculates the intersection of a line and a circle.

The source of the formula used is in the notes.

The relevant script is far right of the scripts section (there's only one sprite).

It uses two points on the line rather than point+slope, but should be adaptable.

The (near) point you need should correspond to “x inter near”, “z inter near”.

Can't remember how well it copes with the tangent case.

Holy Moley, I expected it to be a lot of blocks for the calculation, but thats at least 2 lots of blocks! Thanks for sharing that, it must have been a lot of work turning that Wolfram-Alpha page into scratch blocks O.o

I think you could probably trim it down quite a bit for your purposes. You don't need the far point, and (though I can't remember the details) I think the various angles were calculated for some other purpose in the project, and are not needed for the intersection point calculation itself.

PutneyCat wrote:

I think you could probably trim it down quite a bit for your purposes. You don't need the far point, and (though I can't remember the details) I think the various angles were calculated for some other purpose in the project, and are not needed for the intersection point calculation itself.

Ah, like the near angle? I don't see any other angles in it.

Edit: oh, and the far angle

PutneyCat wrote:

There are probably easier ways, but I did this project ages ago which calculates the intersection of a line and a circle.

The source of the formula used is in the notes.

The relevant script is far right of the scripts section (there's only one sprite).

It uses two points on the line rather than point+slope, but should be adaptable.

The (near) point you need should correspond to “x inter near”, “z inter near”.

Can't remember how well it copes with the tangent case.

Ok, I have snipped it down as much as I could and here is what I have now: Line-Circle Calculator.

I:
-renamed a lot of the variables for 2D space
-replaced dx and dz with xVel and yVel, which are passed into custom block
-removed x2 and z2, replaced with x + xvel and y+ yvel
-got rid of valid? and angle stuff
-got rid of the sgn variable, just because I don't want to have many new variables when I import this into my project.
-To account for cases where the line is tangent to the circle, just let the code run when Delta = 0 as well as > than 0
-I noticed everwhere dr was used, it was dr*dr, and when dr is calculated it is the sqrt(bunch of stuff), so I just had it calc the absolute value of that bunch of stuff and replaced all the dr*dr with dr.

It works pretty well so far, but it doesn't seem to go to the nearest point when there are two interceptions. Could be something to do with all the changes I made.

Also, I'm curious, there is a blank box in the setting y-intercept calculation. Was that supposed to be blank? What does it do?

edit: I just added back in the far intercept calculations, and then at the end compared the distances between the two intercepts to find the closer one. Works great now!

Tell me if I'm just blabbering because I don't know if this method would actually work, but it seems like it would take many less blocks by just calculating the perpendicular line's intersection to a tangent of the circle.

Also the method you put in your original post seems to be the most efficient way to calculate this problem out there (unless the way I just guessed above actually worked somehow) so maybe try condensing it, making it atomic, or pre-calculating variables/rounding

Wettining wrote:

Tell me if I'm just blabbering because I don't know if this method would actually work, but it seems like it would take many less blocks by just calculating the perpendicular line's intersection to a tangent of the circle.

Also the method you put in your original post seems to be the most efficient way to calculate this problem out there (unless the way I just guessed above actually worked somehow) so maybe try condensing it, making it atomic, or pre-calculating variables/rounding

Hmmm sounds like it could be easier, but a few questions I have: By perpendicular line, do you mean perpendicular to L? And if so, which perpendicular line to L would we use? (There are infinite). Also, which tangent to the circle would we use (also infinite here.)

My method used the least blocks, but the amount of calculations depended on how far out of the ropes radius the xVel and yVel took the player. For example: if the player was moving really quickly and moved 100 pixels out of the ropes radius, it would repeat those calculations 100 times before getting back into the ropes radius. For really small jumps out of the ropes radius it might take less calculations, like if it only took 5 or so repeats until it got back in. The nice thing about Putney Cat's method is it will always take just 1 iteration.

Wettining wrote:

Tell me if I'm just blabbering because I don't know if this method would actually work, but it seems like it would take many less blocks by just calculating the perpendicular line's intersection to a tangent of the circle.

Also the method you put in your original post seems to be the most efficient way to calculate this problem out there (unless the way I just guessed above actually worked somehow) so maybe try condensing it, making it atomic, or pre-calculating variables/rounding

Did you mean find the point on the circle where it has the same slope as the perpendicular line? If so, I thought it would work at first, but since the line is probably not perpendicular with the tangent line of the intersection point on the circle it won't work.

For others reading, here is the wolfram link from above: http://mathworld.wolfram.com/Circle-LineIntersection.html

I asked @TheLogFather about this problem, and he pointed out that while solving for the coordinates we should come upon a quadratic equation. Knowing this, I was able to finish solving for the points of interception using the equation of a line and circle.

1. y = mx + b // equation of a line
2. b = y - mx // solving for b
3. b = playerY - m(playerX) // plugging in our point

4. (x - Cx)^2 + (y - Cy)^2 = r^2 // equation of a circle
5. (y - Cy)^2 = r^2 - (x - Cx)^2 // isolate y term
6. y - Cy = sqrt(r^2 - (x - Cx)^2) // square-root each side
7. y = sqrt(r^2 - (x - Cx)^2) + Cy // isolate y

8. mx + b = sqrt(r^2 - (x - Cx)^2) + Cy // set equations from line 1 and line 8 equal to each other since they intersect at same y coordinate
9. mx + b - Cy = sqrt(r^2 - (x - Cx)^2) // move Cy over
10. (mx + b - Cy)^2 = r^2 - (x - Cx)^2 // square each side
11. (mx)^2 + b^2 + Cy^2 + 2mxb - 2bCy - 2mxCy = r^2 - (x - Cx)^2 // expand left side
12. (mx)^2 + b^2 + Cy^2 + 2mxb - 2bCy - 2mxCy = r^2 - x^2 -2xCx + Cx^2 // expand right side
13. (mx)^2 + x^2 + 2mxb - 2mxCy + 2xCx - r^2 - Cx^2 + b^2 + Cy^2 - 2bCy = 0 // move all terms to left side
14. (m^2 + 1)x^2 + (2mb - 2mCy + 2Cx)x + ( - r^2 - Cx^2 + b^2 + Cy^2 - 2bCy) = 0 // pull out x^2 from first 2 terms and x from next 3 terms

15. let A = (m^2 + 1) // because why not (but you will see why soon :P)
16. let B = (2mb - 2mCy + 2Cx) // same reason as line 15
17. let C = ( - r^2 - Cx^2 + b^2 + Cy^2 - 2bCy) // same reason as line 15
18. Ax^2 + Bx + C = 0 // substitute variables from lines 15, 16, and 17 into equation from line 14. This might look familiar, that's because its a quadratic equation!
19. x = (-B +- sqrt(B^2 - 4AC)) / (2A) //using quadratic formula, solve for x from line 18

From here we can substitute terms back into the equation on line 19 to solve for x! We do this once with a ‘+’ in the equation (where the ‘+-’ is) and once with a ‘-’.
Once we have both x's , we plug each back into our y = mx + b to solve for y's. The points we get from the two x's and two y's are the points of interception!

To put this into scratch code (with a few shortcuts to save total block usage):

If the line was tangent to the circle, both points will be the same point. Otherwise, we can compare distances between our defining point of the line and each of the interception points. Whichever distance is smaller is the point we are wanting!

If you want to use this formula in a more general case, like in a case where we don't know if the line will even intercept the circle, you would check if the quadraticInner variable is < 0

If it is, that means there is no interception point, but otherwise there is at least 1 interception point.

This seems to be about the same amount of blocks as @PutneyCat 's method (which comes from the Wolfram Alpha site @imfh posted above), although calculated differently. Differently, yet very similar looking…

Just use a system of equations to simplify the result. The system would be for the following:
y=mx+b
(x - Cx)^2 + (y - Cy)^2 = r^2
Using these, you would find y in the circle and substitute the equation for the circle into y in y=mx+b. Then, using algebra, you'd solve it the rest of the way.

AmazingMech2418 wrote:

Just use a system of equations to simplify the result. The system would be for the following:
y=mx+b
(x - Cx)^2 + (y - Cy)^2 = r^2
Using these, you would find y in the circle and substitute the equation for the circle into y in y=mx+b. Then, using algebra, you'd solve it the rest of the way.

Sorry, but I am a little confused, how is this different from what I posted in the first post and the post right before this one? Are you saying there is a more simple solution using algebra? If so, would you mind showing it? Thanks!

I made this project long ago which lets you draw a custom polygon then shoots a bullet which can detect whether it is inside or outside the shape.

Locomule wrote:

I made this project long ago which lets you draw a custom polygon then shoots a bullet which can detect whether it is inside or outside the shape.

Interesting, although I am not quite sure how it works, by the description. It says it compares the line the bullet travels on to the lines of the edges of the shape, but wouldn't that only work on the edges? Like if the bullet is inside the shape, it wouldn't be on any of the lines formed by the shape. Obviously it works, so I must not be understanding it correctly?

A handy tool, but doesn't work to well when we are dealing with a circle, as it would have infinite edges to calculate (or at least a lot if we want to approximate a circle)

Think of the shape as a closed line. The line is the perimeter of the shape, not the shape itself and has no width.
Being on one side of the line is “inside” the shape, being on the other side is “outside”. We only think of it that way because we closed the line into a loop.

Locomule wrote:

Think of the shape as a closed line. The line is the perimeter of the shape, not the shape itself and has no width.
Being on one side of the line is “inside” the shape, being on the other side is “outside”. We only think of it that way because we closed the line into a loop.

Ohh I see, so as long as it is on the “correct side” of each of the lines formed by the segments, it is inside the shape? That is an interesting way of detecting for a collision!

Right! I'm a high school drop so my mathematical solutions are often “interesting”
Now that I'm older I realize I had some kind of weird math anxiety, all my other classes were really easy. I got behind at Intermediate algebra and never caught up so you are all talking waaay over my head!

Locomule wrote:

Right! I'm a high school drop so my mathematical solutions are often “interesting”
Now that I'm older I realize I had some kind of weird math anxiety, all my other classes were really easy. I got behind at Intermediate algebra and never caught up so you are all talking waaay over my head!

Haha maybe being a drop helps you think outside the box more

Sometimes I wonder how much of math anxiety comes from the teacher and the class. I never liked math much until I got some awesome match teachers in my high school years who loved math and were enthusiastic to teach it. Those teachers really made math fun for me, and math became a lot easier at the same time. I even ended up making Math my major, which I attribute to those teachers!