### Line-line collision detection investigation (part one)

09Jul16

I recently rebooted development of a project I tried to develop for the Ludum Dare 20 contest held in April 2011, the theme of which was “It’s dangerous to go alone! Take this!”

As the project will require a function for performing line-line collision detection, and as I’m interested in whether it is possible to program that function using the knowledge I’ve gained-, and the abilities I’ve developed-, studying the Introductory Algebra Review (MA004) and Visualizing Algebra (MA006) courses offered by Udacity, I’ve begun an investigation into programming that function.

In this first part of the investigation, I investigate programming a function for performing line-line collision detection when the two lines are infinite in length.

★ ★ ★

The inputs to the function for performing line-line collision detection will be two lines (hereafter $A$ and $B$), with a line being two pairs of $x$ and $y$ coordinates – viz., $\left\{ \left( x_{1},y_{1} \right),\left( x_{2},y_{2} \right) \right\}$.

If a line is not a vertical line, it is possible to determine the slope ($m$) of that line thusly:
$m=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$
A horizontal line – viz., a line where $y_{1}=y_{2}$ – has a slope of $0$, as $m=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$$m=\frac{0}{x_{2}-x_{1}}$$m=0$.
A vertical line – viz., a line where $x_{1}=x_{2}$ – has an undefined slope, as $m=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$$m=\frac{y_{2}-y_{1}}{0}$$m=$undefined.

If a line is not a vertical line, it is possible to determine the $y$-intercept ($b$) of that line by rearranging the equation for a line in slope-intercept form ($y=mx+b$) thusly:

1. $y=mx+b$
2. $y-b=mx+b-b$$y-b=mx$
3. $y-y-b=mx-y$$-b=mx-y$
4. $-1\left( -b \right)=-1\left( mx-y \right)$$b=-mx+y$

If a line is not a vertical line, it is possible to make $x$ the subject of the equation for a line in slope-intercept form by rearranging that equation thusly:

1. $y=mx+b$
2. $y-b=mx+b-b$$y-b=mx$
3. $\frac{y-b}{m}=\frac{mx}{m}$$\frac{y-b}{m}=x$$x=\frac{y-b}{m}$

If neither of the two lines is a vertical line, and if at most one of the two lines is a horizontal line, it is possible to arrive at a formula for the $x$ coordinate where the two lines intersect by setting the slope-intercept form equations for the two lines equal to each other and rearranging thusly:

1. $m_{A}x+b_{A}=m_{B}x+b_{B}$
2. $m_{A}x+b_{A}-b_{A}=m_{B}x+b_{B}-b_{A}$$m_{A}x=m_{B}x+b_{B}-b_{A}$
3. $m_{A}x-m_{B}x=m_{B}x-m_{B}x+b_{B}-b_{A}$$m_{A}x-m_{B}x=b_{B}-b_{A}$
4. $\left( x \right)\left( m_{A}-m_{B} \right)=b_{B}-b_{A}$
5. $\frac{\left( x \right)\left( m_{A}-m_{B} \right)}{\left( m_{A}-m_{B} \right)}=\frac{b_{B}-b_{A}}{\left( m_{A}-m_{B} \right)}$$x=\frac{b_{B}-b_{A}}{m_{A}-m_{B}}$

This formula cannot be used if either or both of the two lines is a vertical line, as either $m_{A}$ or/and $m_{B}$ will be undefined.
Similarly, this formula cannot be used if both of the two lines are horizontal lines, as $m_{A}=m_{B}$, so $m_{A}-m_{B}=0$, and so $x=\frac{b_{B}-b_{A}}{m_{A}-m_{B}}$$x=\frac{b_{B}-b_{A}}{0}$$x=$undefined.

If neither of the two lines is a vertical line, and if at most one of the two lines is a horizontal line, it is possible to arrive at a formula for the $y$ coordinate where the two lines intersect by setting the slope-intercept form equations for the two lines – rearranged to make $x$ the subject of those equations – equal to each other and rearranging thusly:

1. $\frac{y-b_{A}}{m_{A}}=\frac{y-b_{B}}{m_{B}}$
2. $\left( m_{A} \right)\left( m_{B} \right)\left( \frac{y-b_{A}}{m_{A}} \right)=\left( m_{A} \right)\left( m_{B} \right)\left( \frac{y-b_{B}}{m_{B}} \right)$$\left( m_{B} \right)\left( y-b_{A} \right)=\left( m_{A} \right)\left( y-b_{B} \right)$
3. $\left( m_{B} \right)\left( y-b_{A} \right)=\left( m_{A} \right)\left( y-b_{B} \right)$$m_{B}y-m_{B}b_{A}=m_{A}y-m_{A}b_{B}$
4. $m_{B}y-m_{B}b_{A}+m_{A}b_{B}=m_{A}y-m_{A}b_{B}+m_{A}b_{B}$$m_{B}y-m_{B}b_{A}+m_{A}b_{B}=m_{A}y$
5. $m_{B}y-m_{B}y-m_{B}b_{A}+m_{A}b_{B}=m_{A}y-m_{B}y$$-m_{B}b_{A}+m_{A}b_{B}=m_{A}y-m_{B}y$
6. $-m_{B}b_{A}+m_{A}b_{B}=\left( y \right)\left( m_{A}-m_{B} \right)$
7. $\frac{-m_{B}b_{A}+m_{A}b_{B}}{\left( m_{A}-m_{B} \right)}=\frac{\left( y \right)\left( m_{A}-m_{B} \right)}{\left( m_{A}-m_{B} \right)}$$\frac{-m_{B}b_{A}+m_{A}b_{B}}{m_{A}-m_{B}}=y$$y=\frac{-m_{B}b_{A}+m_{A}b_{B}}{m_{A}-m_{B}}$

This formula cannot be used if either or both of the two lines is a vertical line, as either $m_{A}$ or/and $m_{B}$ will be undefined.
Similarly, this formula cannot be used if both of the two lines are horizontal lines, as $m_{A}=m_{B}$, so $m_{A}-m_{B}=0$, and so $y=\frac{-m_{B}b_{A}+m_{A}b_{B}}{m_{A}-m_{B}}$$y=\frac{-m_{B}b_{A}+m_{A}b_{B}}{0}$$y=$undefined.

★ ★ ★

If both of the two lines are horizontal lines, then the two lines collide – and are coincident – if $y_{A}=y_{B}$, otherwise the two lines are parallel.

If both of the two lines are vertical lines, then the two lines collide – and are coincident – if $x_{A}=x_{B}$, otherwise the two lines are parallel.

If $A$ is a horizontal line and $B$ is a vertical line, then the two lines collide, and the coordinates at which the two lines collide are $\left( x_{B},y_{A} \right)$.

If $A$ is a vertical line and $B$ is neither a horizontal nor a vertical line, then the two lines collide, and the coordinates at which the two lines collide are $\left( x_{A},m_{B}x_{A}+b_{B} \right)$.

If neither of the two lines is a vertical line, at most one of the two lines is a horizontal line, and the two lines are neither coincident nor parallel, then the two lines collide, and the coordinates at which the two lines collide are $\left( \frac{b_{B}-b_{A}}{m_{A}-m_{B}},\frac{-m_{B}b_{A}+m_{A}b_{B}}{m_{A}-m_{B}} \right)$.

If the two lines are coincident, then the two lines collide.

#ifndef LEONARDO
#error "This program requires Leonardo IDE to run."
#endif

#include "seal_stringToInt_C.h"

/**
View( Out 0 );
ViewOrigin( Out 100, Out 100, 0 );

// y-axis.
Line( Out L, Out X1, Out -100, Out X2, Out 100, 0 )
For I:InRange( I, 0, 20 )
Assign L = ( I != 10 )?-2:-1
Assign X1, X2 = -100 + I * 10;

// x-axis.
Line( Out L, Out -100, Out Y1, Out 100, Out Y2, 0 )
For I:InRange( I, 0, 20 )
Assign L = ( I != 10 )?-2:-1
Assign Y1, Y2 = -100 + I * 10;

LineColor( -1, Out Grey, 0 );
LineColor( -2, Out LightGrey, 0 );
LineStyle( -2, Out Dashed, 0 );

PointShape( _, Out Round, 0 );
PointSize( _, Out 3, 0 );
**/

typedef struct t_Coordinates_struct
{
double m_x, m_y;
}
t_Coordinates;

typedef enum
{
k_LINE_TYPE__STANDARD,
k_LINE_TYPE__HORIZONTAL,
k_LINE_TYPE__VERTICAL
}
t_LineType;

typedef struct t_Line_struct
{
t_Coordinates m_begin, m_end;
double m_slope /* m. */, m_yIntercept /* b. */;
t_LineType m_type;
}
t_Line;

void p_DetermineSlopeAndTypeOfLine( t_Line *p )
{
const double delta_x = p->m_end.m_x - p->m_begin.m_x;
if( delta_x == 0 )
p->m_type = k_LINE_TYPE__VERTICAL;
else
{
const double delta_y = p->m_end.m_y - p->m_begin.m_y;
if( delta_y == 0 )
{
p->m_slope = 0;
p->m_type = k_LINE_TYPE__HORIZONTAL;
}
else
{
p->m_slope = delta_y / delta_x;
p->m_type = k_LINE_TYPE__STANDARD;
}
}
}

void p_DetermineYInterceptOfLine( t_Line *p )
{
p->m_yIntercept = -1 * p->m_slope * p->m_begin.m_x + p->m_begin.m_y;
}

#define M_ASSIGN_ARGUMENT_TO_COORDINATE( p_line, p_coordinates /* begin or end. */, p_coordinate /* x or y. */ ) \
p_line .m_ ## p_coordinates .m_ ## p_coordinate = f_seal_StringToInt_C( argv[ i ] );                                   \
if(( f_seal_StringToInt_Error_C() != k_seal_STRING_TO_INT_ERROR_C__NONE )                                              \
|| ( p_line .m_ ## p_coordinates .m_ ## p_coordinate < -10 )                                                         \
|| ( p_line .m_ ## p_coordinates .m_ ## p_coordinate > 10 ))                                                         \
{                                                                                                                      \
error_occurred = true;                                                                                               \
goto l_ERROR_OCCURRED;                                                                                               \
}                                                                                                                      \
i ++;

void p_PrintLine( const char * const p_lineName, const t_Line * const p_line )
{
printf( "%s: { ( %d, %d ), ( %d, %d ) }", p_lineName, ( int )p_line->m_begin.m_x, ( int )p_line->m_begin.m_y, ( int )p_line->m_end.m_x, ( int )p_line->m_end.m_y );
if( p_line->m_type != k_LINE_TYPE__STANDARD )
printf( " (%sal)", ( p_line->m_type == k_LINE_TYPE__HORIZONTAL )?"Horizont":"Vertic" );
printf( "\n" );
printf( "   m = " );
if( p_line->m_type != k_LINE_TYPE__VERTICAL )
printf( "%f", p_line->m_slope );
else
printf( "Undefined" );
printf( "\n" );
printf( "   b = " );
if( p_line->m_type != k_LINE_TYPE__VERTICAL )
printf( "%f", p_line->m_yIntercept );
else
printf( "Undefined" );
printf( "\n" );
}

typedef enum
{
k_LINE_LINE_COLLISION_DETECTED__NO = 0,
k_LINE_LINE_COLLISION_DETECTED__YES,
k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT
}
t_LineLineCollisionDetected;

typedef struct t_LineLineCollision_struct
{
t_LineLineCollisionDetected m_detected;
t_Coordinates m_at;
}
t_LineLineCollision;

t_LineLineCollision f_LineLineCollision( const t_Line * const p_a, const t_Line * const p_b )
{
t_LineLineCollision collision;
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__NO;
if(( p_a->m_type == k_LINE_TYPE__VERTICAL )
&& ( p_b->m_type == k_LINE_TYPE__VERTICAL ))
{
if( p_a->m_begin.m_x == p_b->m_begin.m_x )
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
return collision;
}
if(( p_a->m_type == k_LINE_TYPE__HORIZONTAL )
&& ( p_b->m_type == k_LINE_TYPE__HORIZONTAL ))
{
if( p_a->m_begin.m_y == p_b->m_begin.m_y )
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
return collision;
}
if(( p_a->m_type == k_LINE_TYPE__HORIZONTAL )
&& ( p_b->m_type == k_LINE_TYPE__VERTICAL ))
{
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
collision.m_at.m_x = p_b->m_begin.m_x;
collision.m_at.m_y = p_a->m_begin.m_y;
return collision;
}
if(( p_a->m_type == k_LINE_TYPE__VERTICAL )
&& ( p_b->m_type == k_LINE_TYPE__HORIZONTAL ))
{
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
collision.m_at.m_x = p_a->m_begin.m_x;
collision.m_at.m_y = p_b->m_begin.m_y;
return collision;
}
if(( p_a->m_type == k_LINE_TYPE__STANDARD )
&& ( p_b->m_type == k_LINE_TYPE__VERTICAL ))
{
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
collision.m_at.m_x = p_b->m_begin.m_x;
collision.m_at.m_y = p_a->m_slope * p_b->m_begin.m_x + p_a->m_yIntercept;
return collision;
}
if(( p_a->m_type == k_LINE_TYPE__VERTICAL )
&& ( p_b->m_type == k_LINE_TYPE__STANDARD ))
{
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
collision.m_at.m_x = p_a->m_begin.m_x;
collision.m_at.m_y = p_b->m_slope * p_a->m_begin.m_x + p_b->m_yIntercept;
return collision;
}
if( p_a->m_slope == p_b->m_slope )
{
if( p_a->m_yIntercept == p_b->m_yIntercept )
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
return collision;
}
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
collision.m_at.m_x = ( p_b->m_yIntercept - p_a->m_yIntercept ) / ( p_a->m_slope - p_b->m_slope );
collision.m_at.m_y = ( -1 * p_b->m_slope * p_a->m_yIntercept + p_a->m_slope * p_b->m_yIntercept ) / ( p_a->m_slope - p_b->m_slope );
return collision;
}

int main( const int argc, const char * const argv[] )
{
bool error_occurred = false;
if( argc != 8 )
error_occurred = true;
else
{
t_Line A, B;
int i = 0;
t_LineLineCollision collision;
M_ASSIGN_ARGUMENT_TO_COORDINATE( A, begin, x )
M_ASSIGN_ARGUMENT_TO_COORDINATE( A, begin, y )
M_ASSIGN_ARGUMENT_TO_COORDINATE( A, end, x )
M_ASSIGN_ARGUMENT_TO_COORDINATE( A, end, y )
/**
Point( Out 1, Out X, Out Y, 0 )
Assign X = A.m_begin.m_x * 10 Y = A.m_begin.m_y * -10;
Point( Out 1, Out X, Out Y, 0 )
Assign X = A.m_end.m_x * 10 Y = A.m_end.m_y * -10;
PointColor( 1, Out Magenta, 0 );
Line( Out 1, Out X1, Out Y1, Out X2, Out Y2, 0 )
Assign X1 = A.m_begin.m_x * 10 Y1 = A.m_begin.m_y * -10
Assign X2 = A.m_end.m_x * 10 Y2 = A.m_end.m_y * -10;
LineColor( 1, Out Magenta, 0 );
**/
p_DetermineSlopeAndTypeOfLine( &A );
if( A.m_type != k_LINE_TYPE__VERTICAL )
p_DetermineYInterceptOfLine( &A );
p_PrintLine( "A", &A );

M_ASSIGN_ARGUMENT_TO_COORDINATE( B, begin, x )
M_ASSIGN_ARGUMENT_TO_COORDINATE( B, begin, y )
M_ASSIGN_ARGUMENT_TO_COORDINATE( B, end, x )
M_ASSIGN_ARGUMENT_TO_COORDINATE( B, end, y )
#undef M_ASSIGN_ARGUMENT_TO_COORDINATE
/**
Point( Out 2, Out X, Out Y, 0 )
Assign X = B.m_begin.m_x * 10 Y = B.m_begin.m_y * -10;
Point( Out 2, Out X, Out Y, 0 )
Assign X = B.m_end.m_x * 10 Y = B.m_end.m_y * -10;
PointColor( 2, Out Cyan, 0 );
Line( Out 2, Out X1, Out Y1, Out X2, Out Y2, 0 )
Assign X1 = B.m_begin.m_x * 10 Y1 = B.m_begin.m_y * -10
Assign X2 = B.m_end.m_x * 10 Y2 = B.m_end.m_y * -10;
LineColor( 2, Out Cyan, 0 );
**/
p_DetermineSlopeAndTypeOfLine( &B );
if( B.m_type != k_LINE_TYPE__VERTICAL )
p_DetermineYInterceptOfLine( &B );
p_PrintLine( "B", &B );

collision = f_LineLineCollision( &A, &B );
if( !collision.m_detected )
printf( "No c" );
else
printf( "C" );
printf( "ollision detected" );
if( collision.m_detected == k_LINE_LINE_COLLISION_DETECTED__YES )
{
printf( " at ( %f, %f )", collision.m_at.m_x, collision.m_at.m_y );
/**
Ellipse( Out 0, Out TopLeftX, Out TopLeftY, Out 6, Out 6, 0 )
Assign TopLeftX = collision.m_at.m_x * 10 - 2
Assign TopLeftY = collision.m_at.m_y * -10 - 2;
EllipseFrameColor( 0, Out LightGreen, 0 );
**/
}
else
if( collision.m_detected == k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT )
printf( " – the lines are coincident" );
printf( ".\n" );

l_ERROR_OCCURRED:;
}
if( error_occurred )
printf( "Sorry, an error occurred: this program expects to have passed to it eight integer ([ -10, 10 ]) arguments.\n" );
while( true ); // The lines declared in this function are no longer drawn after this function terminates 😦
}