So finally I am answering my own question after months of work.
The entire problem is quite complicated, but worth solving, since the final collision handling is really worth it.
This explanation is copied here from my webpage, where the math solution is more detailed and supported with more images plus wolfram mathematica notebooks.
This describes how the collision between the objects in the game is being handled.
Circle - Line collision
If collision between circle and line segment (which is line limited on interval <a,b> is resolved, then, using
line segment, other geometrical shapes can be created (such as triangle or polygon), and thus, the collision between
them and circle is already solved.
Definitions
Term line reffers to infinite line, not line segment
Let $C$ be circle with centre $C_s = (c_x, c_y)$ that we want to move
Let $L_s$ be Line Segment defined by 2 points, $A, B$. $L$ might collide circle $C$
Let $L$ be Line defined also by 2 points, $A, B$
Let $v=(v_x, v_y)$ be vector, defining the movement of the circle $C$
Let $v'$ be the final movement vector (the result)
$L_s$ touches $C \Leftrightarrow C$ and $L_s$ have exactly $1$ intersection point
$L_s$ collides $C \Leftrightarrow C$ and $L_s$ have exactly $2$ intersection points
Objective
Imagine, that being given movement vector $v$, the circle $C$ would
collide $L_s$ during movement, if we move $C$ by $v$.
The objective is to determine vector $v'$ such as, when moving $C$
by vector $v'$, then $C$ will collide $L_s$
in exactly one point.
Mathematical solution
The problem is divided to 6 cases, all of them will be discussed below.
- If $C$ does not touch nor collides line $L_s$ before movement begins
Case1: $C$ will collide $L_s$ during movement at one of points $A$ or $B$, where $A$, $B$ are points defining the line $L_s$
Case2: $C$ will collide $L_s$ during movement at point $P$. Let $M$ be, set of all points on line $L_s$. Then, for $P$
applies: $P \in \{M\} / \{A, B\} $
Case3: $C$ will not collide $L_s$ during movement at all
- If $C$ touches $L_s$ before movement begins
Case4: $C$ will collide $L_s$ during movement
Case5: $C$ will not collide $L_s$ during movement
Case6: $C$ collides $L_s$ before movement begins
Circle - Line segment intersection relationship
To solve all the cases, we need to first check for relation between $C$ and $L$ (do they collide each other? Or touch?)
Circle touches Line segment
For this, following statements apply:
Let $P$ be set of all intersection points between $C$ and $L$. Applies $|P| \in \{0,1,2\}$
If $|P|=0 $, then $C$ does not touch $L_s$
If $|P|=1 \wedge P \in L $, then $C$ touches $L_s$
If $ |P|=2 \wedge P_x,P_y \in P: P_x = B \wedge P_y \notin L_s \wedge |A C_s| >= r $, then $C$ touches $L_s$
If $|P|=2 \wedge P_x,P_y \in P: P_x = A \wedge P_y \notin L_s \wedge |B C_s| >= r $, then $C$ touches $L_s$
To explain the math above in plain words:
If $C$ and $L$ have 0 intersection points, then they do not touch.
If $C$ and $L$ have 1 intersection point, then they touch.
If $C$ and $L$ have 2 intersection points:
- If one of the intersection points is $A$, and the other intersection point
does not lie on the line segment $L_s$ and the B point lies outside the circle, then they touch
- If one of the intersection points is $B$, and the other intersection point
does not lie on the line segment $L_s$ and the A point lies outside the circle, then they touch
Circle collides Line segment
For this, following statements apply:
Let $P$ be set of all intersection points between $C$ and $L$. Applies $|P| \in \{0,1,2\}$
If $|P| \in \{0,1\} $, then $C$ does not collide $L_s$
If $|P|=2 \wedge P_x,P_y \in P: P_x \in L_s \wedge P_y \in L_s $, then $C$ collides $L_s$
If $|P|=2 \wedge P_x,P_y \in P: P_x = A \wedge |B C_s| >= r $, then $C$ collides $L_s$
If $|P|=2 \wedge P_x,P_y \in P: P_x = B \wedge |A C_s| >= r $, then $C$ collides $L_s$
To explain the math above in plain words:
If $C$ and $L$ have 0 r 1 intersection points, then they do not collide.
If $C$ and $L$ have 2 intersection points:
- If both intersection points lie on $L_s$, then they collide
- If one of the intersection points is $A$, and the other intersection point
does not lie on the line segment $L_s$ and the $B$ point lies inside or on the circle, then they collide
- If one of the intersection points is $B$, and the other intersection point
does not lie on the line segment $L_s$ and the $A$ point lies inside or on the circle, then they collide
Case 1:
$C$ will collide
$L_s$ during movement at one of points
$A$ or
$B$, where
$A$,
$B$ are points defining the line
$L_s$
To solve this, similar mathematical approach is used as in case2.
It is strongly recomended to read that first, and then come back here for better understanding...
By taking circle equation and line equation and combining them together, the point A (later also B) is plugged into
the equations. If there is solution, and the final movement vector $v$ matches criteria
(smaller than original movement vector, etc...for more details, read through case2),
then the circle is considered to be colliding line segment at point A (or B, respectivelly).
Case 2:
$C$ will collide
$L_s$ during movement at point
$P$. Let
$M$ be, set of all points on line
$L_s$. Then, for
$P$
applies:
$P \in \{M\} / \{A, B\} $
Let's reiterate, that $L$ is line, not a line segment. For simplicity, I will explain the solution on LINE,
understanding that narrowing the solution down for line segment involves limitation on interval and adding few other edge cases to entire solution.
Let's start by having the equation of circle $C$:
$$(x-c_x)^2+(y-c_y)^2=r^2$$
Now, we perform translation of the centre by vector $v$:
$$(x-(c_x+v_x))^2+(y-(c_y+v_y))^2=r^2$$
However, we do not know how far to move the circle to get exactly one intersection point with $L$.
Therefore, we use parameter $t$:
$$(x-(c_x+v_x*t))^2+(y-(c_y+v_y*t))^2=r^2$$
The equation above describes all circles, that are moved on the line defined by movement vector $v'$
Now, we will solve system of 2 equations:
$$(x-(c_x+v_x*t))^2+(y-(c_y+v_y*t))^2=r^2$$
$$a*x+b*y+c=0$$
Where the second equation is the equation of $L$ in general form
We express $x$ from the line equation (alternativelly, $y$ must be expressed in some cases to avoid diving by 0):
$$x=\frac{-b*y-c}{a}$$
That value is plugged into the circle equation to get:
$$(\frac{-b*y-c}{a}-(c_x+v_x*t))^2+(y-(c_y+v_y*t))^2=r^2$$
Now, considering $t$ as the polynom variable, if discriminant equals 0, then there is exactly one solution
(circle collides line in one point only)
$$Discriminant[(\frac{-b*y-c}{a}-(c_x+v_x*t))^2+(y-(c_y+v_y*t))^2-r^2,y]=0$$
The discriminant is then:
$$D=-(\frac{1}{a^2})*
4 *(c^2 + 2 a c c_x + a^2 c_x^2 + 2 b c c_y + 2 a b c_x c_y + b^2 c_y^2 -
a^2 r^2 - b^2 r^2 + 2 a c t v_x + 2 a^2 c_x t v_x + 2 a b c_y t v_x +
a^2 t^2 v_x^2 + 2 b c t v_y + 2 a b c_x t v_y + 2 b^2 c_y t v_y +
2 a b t^2 v_x v_y + b^2 t^2 v_y^2)$$
Considering some input values for circle centre, movement vector, radius, etc., this would be
more readable result:
$$D=-4(28-36*t+9t^2$$
The thing left is to compute the $t$, which is the movement vector multiplier.
Final solution vectors (if the solutions exist) will be:
$v'_1 = (v_x * t_1, v_y * t_1)$
$v'_2 = (v_x * t_2, v_y * t_2)$
Of course, the final vectors $v'_1, v'_2$ might not face in same direction as $v'$.
In that case, the solution is discarted.
Moreover, if $|t_1| > 1 \lor |t_2| > 1)$, then $t_1$, respectivelly $t_2$ is discarted.
That is because we require final vector to have same or smaller length then the original move vector
Case 3:
$C$ will not collide
$L_s$ during movement at all
If none of Case1 or
Case2 holds and yields a solution,
then the circle will not collide line segment at all during movement.
Case 4 and 5:
$C$ touches
$L_s$ before movement begins, and
$C$ will (or not) collide
$L_s$ during movement
For this one, imagine following figure:
touchMoveIllustration1
- Let $t$ be tangent to $C$ in point $P$, which is touch point of $C$ and $L_s$ (in this example, $P=A$)
- Let $u=|AE|$, $v=|AD|$ be two movement vectors, where we position them to begin in touch point $P=A$
- $u=|AE|$ represents movement that would be allowed, whereas $v=|AD|$ represents movement that would NOT be allowed
In general case, imagining vector $u=|AD|$, then movement of $C$ using vector $u$ is valid $\iff D$ is on
same side of line $t$ as centre of circle $C$ or $D \in t$
Case 6:
$C$ collides
$L_s$ before movement begins
Trivial case, when is done check for whether $C$ collides $L_s$, and if so, then no movement is done...
Best Answer
I assume the line is vertical. Otherwise rotate the figure to make it so, and rotate back when the following is done. Or if you prefer, the following gives the coordinates of the point you are looking for in a coordinate system I choose, and you have to make a change of coordinates to find them in your original coordinate system.
I also assume $O$ is at coordinates $(0,0)$, the larger circle $\mathscr C$ has radius $R=\sqrt{h^2+k^2}$, and the vertical line $AB$ cuts the horizontal axis at point $H(a,0)$.
We want the point $M(x,y)$ on $\mathscr C$ such that the circle of center $M$ and radius $r$ is tangent to $AB$. This means that $x+r=a$, and from $x^2+y^2=R^2$ we can find $y$.