y=mx+c intersecting a circle

I'm trying to write a 3d computer game. When it comes to walls they're all straight lines between 2 points on the $xz$ plane. If the man is centered at $(i,k)$ the equation for their circle of influence is $(x-i)^2+(z-k)^2=r^2$. If the case of a wall having equation $x=c$ or $z=c$ I can solve this, but when the wall is sloping and is of the form $z=mx+c$, my powers of math fail me.

• Plug in your formula for $z$ and use the quadratic formula. Jun 2 '16 at 10:04
• @rhubarbdog Welcome to MSE. Please look at math.stackexchange.com/help/notation to see how to format math for this site. Jun 2 '16 at 10:13
• Is there some person, who is assigned the job to down vote questions by first timers ?
– user312097
Jun 2 '16 at 10:20
• @rhurbardog, your equations are two dimensional, they don't three dimensions to work.
– user312097
Jun 2 '16 at 10:24
• the y axis is stright up and down and will be accessed by jumping or catch an elevator, walking up hill or climbing a ladder Jun 3 '16 at 9:47

As suggested in comments, you can set $z=mx+c$ in the equation of circle, thus get $$(x-i)^2+(mx+c-k)^2=r^2\\ x^2-2ix+i^2+m^2x^2+2mx(c-k)+c^2-2ck+k^2=r^2$$ Now, we can write it as the quadratic equation $$(m^2+1)x^2+2(mc-mk-i)x+i^2+c^2+k^2-2kc-r^2=0$$and solve for $x$ (no, it is not pretty). Good luck!

If the question is "does the man's region of influence meet the wall?" rather than "WHERE does it meet the wall?", then things are easier: you merely need to compute the distance from the man $(i, k)$ to the nearest point on the wall. If this distance is less than $r$, then you've got your answer.

It's easier to compute the squared distance and check that it;'s less than $r^2$, however, avoiding a square root.

So how do you do this distance-checking?

First, writing wall-equations in the form $y = mx + b$ is a bad idea, even though it's what you're most familiar with from high-school, because it doesn't allow for $x = constant$ walls. Instead, it's best to write them in the form $$Ax + By + C = 0$$ where at least one of $A$ or $B$ is nonzero. If you have the $y = mx + b$ form, you can shuffle it around: $$y = mx + b \\ y - mx - b = 0\\ (-m)x + 1y + (-b) = 0$$ to get it in the $Ax + By + C = 0$ form, with $A = -m, B = 1, C = -b$. So this "general" form includes the one you're used to.

The second fact you need to know is that if you plug a point $(x, y) = (a, b)$ into the left side of the equation $$Ax + By + C = 0$$ to get $$Aa + Bb + C,$$ the resulting number is related to the distance from $(a, b)$ to the line. If the resulting number is zero, then the point's on the line, for instance!

Here's the rule: the distance from $(a, b)$ to the line defined by $$Ax + By + C = 0$$ is exactly $$d = \frac{Aa + Bb + C}{\sqrt{A^2 + B^2}}$$ so the squared distance is just $$d^2 = \frac{(Aa + Bb + C)^2}{A^2 + B^2}$$

Conclusion: to test whether the point $(i, k)$ is "close" to a wall defined by $y = mx + b$, do the following:

1. Let $A = -m, B = 1, C = -b$

2. Compute $s = Ai + Bk + C$.

3. Compute $\frac{s^2}{A^2 + B^2}$.

4. If the value in step 3 is less than $r^2$, then the man is within distance $r$ of the wall; if the value's grater than $r^2$, the man is farther than $r$ from the wall. If it's exactly $r^2$, the man is at distance $r$ from the wall.

As a little throwaway, the value $s$ that you computed may be positive or negative. For all points on one side of the line, it'll be positive; for all points on the other side, it'll be negative. If you want to switch these sides, you can replace $A, B, C$ with $-A, -B, -C$, and the line will not change, but the sign of $s$ will.