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.

  • $\begingroup$ Plug in your formula for $z$ and use the quadratic formula. $\endgroup$ Jun 2 '16 at 10:04
  • $\begingroup$ @rhubarbdog Welcome to MSE. Please look at math.stackexchange.com/help/notation to see how to format math for this site. $\endgroup$
    – almagest
    Jun 2 '16 at 10:13
  • 2
    $\begingroup$ Is there some person, who is assigned the job to down vote questions by first timers ? $\endgroup$
    – user312097
    Jun 2 '16 at 10:20
  • $\begingroup$ @rhurbardog, your equations are two dimensional, they don't three dimensions to work. $\endgroup$
    – user312097
    Jun 2 '16 at 10:24
  • $\begingroup$ 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 $\endgroup$
    – rhubarbdog
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.