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

29Jul16

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 second part of the investigation, I investigate programming a function for performing line-line collision detection when the two lines are finite in length.

★ ★ ★

If a line is imagined to be enclosed in a rectangle where $\left( x_{1},y_{1} \right)$ are the coordinates of a corner of the rectangle and $\left( x_{2},y_{2} \right)$ are the coordinates of the diagonally opposite corner of the rectangle, then $w$ is the width of the rectangle – viz., $w=\left| x_{2}-x_{1} \right|$ – and $h$ is the height of the rectangle – viz., $h=\left| y_{2}-y_{1} \right|$.

It is possible to determine the horizontal midpoint ($s$) of a line thusly: $s=\frac{x_{2}-x_{1}}{2}+x_{1}$$s=\frac{x_{2}-x_{1}+2x_{1}}{2}$$s=\frac{x_{2}+x_{1}}{2}$$s=\frac{x_{1}+x_{2}}{2}$.

Similarly, it is possible to determine the vertical midpoint ($t$) of a line thusly: $t=\frac{y_{2}-y_{1}}{2}+y_{1}$$t=\frac{y_{2}-y_{1}+2y_{1}}{2}$$t=\frac{y_{2}+y_{1}}{2}$$t=\frac{y_{1}+y_{2}}{2}$.

★ ★ ★

The following table specifies the algorithm to be used to detect if two lines, which are finite in length, collide.

 Horizontal line Vertical line Non-horizontal, non-vertical line Horizontal line 1. 3. 4. Vertical line 3. 2. 3. Non-horizontal, non-vertical line 4. 3. 4. if non-coincident, 5. if coincident or partially coincident

1. In the first part of this investigation, it was stated that two horizontal lines that are infinite in length collide – and are coincident – if $y_{A}=y_{B}$, otherwise the two lines are parallel; now, with the two lines being constrained to being finite in length, two horizontal lines collide – and are coincident or partially coincident – if $y_{A}=y_{B}$ and if the distance between the horizontal midpoints of the two lines is less than half of the sum of the widths of the two lines – viz., if $\left| s_{A}-s_{B} \right|<\frac{w_{A}+w_{B}}{2}$.

2. In the first part of this investigation, it was stated that two vertical lines that are infinite in length collide – and are coincident – if $x_{A}=x_{B}$, otherwise the two lines are parallel; now, with the two lines being constrained to being finite in length, two vertical lines collide – and are coincident or partially coincident – if $x_{A}=x_{B}$ and if the distance between the vertical midpoints of the two lines is less than half of the sum of the heights of the two lines – viz., if $\left| t_{A}-t_{B} \right|<\frac{h_{A}+h_{B}}{2}$.

An amendment: In the first part of this investigation, it was stated that:

“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)$.”

And that:

“If $A$ is neither a horizontal nor a vertical 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},m_{A}x_{B}+b_{A} \right)$.”

As the slope-intercept form equation for a horizontal line takes the form $y=mx+b$$y=0x+b$$y=b$, the second of the passages quoted above – amended to constrain $A$ from being a vertical line, not from being either a horizontal or a vertical line – obviates the first of the passages quoted above.

3. In the first part of this investigation, it was stated that two lines that are infinite in length collide if the first of the two lines ($A$) is not a vertical line and if the second of the two lines ($B$) is a vertical line, and that the coordinates at which the two lines collide ($C$) are $\left( x_{B},m_{A}x_{B}+b_{A} \right)$; now, with the two lines being constrained to being finite in length, the two lines collide if:

1. the distance between the $x$ coordinate at which the two lines would collide if they were infinite in length and the horizontal midpoint of the non-vertical line is less than half the width of that line – viz., if $\left| x_{\mbox{C}}-s_{A} \right|<\frac{w_{A}}{2}$;
2. and the distance between the $y$ coordinate at which the two lines would collide if they were infinite in length and the vertical midpoint of the non-vertical line is either zero or less than half the height of that line – viz., if $\left| y_{\mbox{C}}-t_{A} \right|=0$ or $\left| y_{\mbox{C}}-t_{A} \right|<\frac{h_{A}}{2}$;
3. and the distance between the $y$ coordinate at which the two lines would collide if they were infinite in length and the vertical midpoint of the vertical line is less than half the height of that line – viz., if $\left| y_{\mbox{C}}-t_{B} \right|<\frac{h_{B}}{2}$.

4. In the first part of this investigation, it was stated that two lines that are infinite in length collide if the first of the two lines ($A$) is neither a horizontal nor a vertical line, the second of the two lines ($B$) is not a vertical line, and the two lines are neither coincident nor parallel, and that the coordinates at which the two lines collide ($C$) 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)$; now, with the two lines being constrained to being finite in length, the two lines collide if:

1. the distance between the $x$ coordinate at which the two lines would collide if they were infinite in length and the horizontal midpoint of the non-horizontal, non-vertical line is less than half the width of that line – viz., if $\left| x_{\mbox{C}}-s_{A} \right|<\frac{w_{A}}{2}$;
2. and the distance between the $y$ coordinate at which the two lines would collide if they were infinite in length and the vertical midpoint of the non-horizontal, non-vertical line is less than half the height of that line – viz., if $\left| y_{\mbox{C}}-t_{A} \right|<\frac{h_{A}}{2}$;
3. and the distance between the $x$ coordinate at which the two lines would collide if they were infinite in length and the horizontal midpoint of the non-vertical line is less than half the width of that line – viz., if $\left| x_{\mbox{C}}-s_{B} \right|<\frac{w_{B}}{2}$;
4. and the distance between the $y$ coordinate at which the two lines would collide if they were infinite in length and the vertical midpoint of the non-vertical line is either zero or less than half the height of that line – viz., if $\left| y_{\mbox{C}}-t_{B} \right|=0$ or $\left| y_{\mbox{C}}-t_{B} \right|<\frac{h_{B}}{2}$.

5. In the first part of this investigation, it was stated that if two lines that are infinite in length are coincident, then those two lines collide; now, with the two lines being constrained to being finite in length, two coincident or partially coincident lines collide if the distance between the horizontal midpoints of the two lines is less than half of the sum of the widths of the two lines – viz., if $\left| s_{A}-s_{B} \right|<\frac{w_{A}+w_{B}}{2}$.

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

#include <math.h>
#include <stdlib.h>
#include <syscall.h>
#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;

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

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

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

typedef enum
{
k_LINE_TYPE__HORIZONTAL,
k_LINE_TYPE__VERTICAL,
k_LINE_TYPE__NON_HORIZONTAL_AND_NON_VERTICAL
}
t_LineType;

typedef struct t_Line_struct
{
t_Coordinates m_begin, m_end;
double m_width /* w. */, m_height /* h. */, m_horizontalMidpoint /* s. */, m_verticalMidpoint /* t. */, m_slope /* m. */, m_yIntercept /* b. */;
t_LineType m_type;
}
t_Line;

t_Line f_NewLine( const double p_x1, const double p_y1, const double p_x2, const double p_y2 )
{
t_Line line;
line.m_begin.m_x = p_x1;
line.m_begin.m_y = p_y1;
line.m_end.m_x = p_x2;
line.m_end.m_y = p_y2;
line.m_width = fabs( p_x2 - p_x1 );
line.m_height = fabs( p_y2 - p_y1 );
line.m_horizontalMidpoint = ( p_x1 + p_x2 ) / 2;
line.m_verticalMidpoint = ( p_y1 + p_y2 ) / 2;
{
const double delta_x = p_x2 - p_x1;
if( delta_x == 0 )
line.m_type = k_LINE_TYPE__VERTICAL;
else
{
const double delta_y = p_y2 - p_y1;
if( delta_y == 0 )
{
line.m_slope = 0;
line.m_yIntercept = p_y1;
line.m_type = k_LINE_TYPE__HORIZONTAL;
}
else
{
line.m_slope = delta_y / delta_x;
line.m_yIntercept = -1 * line.m_slope * p_x1 + p_y1;
line.m_type = k_LINE_TYPE__NON_HORIZONTAL_AND_NON_VERTICAL;
}
}
}
return line;
}

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;

// The following function assumes that p_collision->m_detected == k_LINE_LINE_COLLISION_DETECTED__NO.
// It would be helpful if Leonardo IDE treated the inline qualifier as a no-op if it doesn't support that qualifier…
static /* inline */ bool f_LineLineCollision_Algorithm3( const t_Line * const p_a, const t_Line * const p_b, t_LineLineCollision *p_collision )
{
if(( p_a->m_type != k_LINE_TYPE__VERTICAL )
&& ( p_b->m_type == k_LINE_TYPE__VERTICAL ))
{
p_collision->m_at.m_x = p_b->m_begin.m_x;
p_collision->m_at.m_y = p_a->m_slope * p_b->m_begin.m_x + p_a->m_yIntercept;

// i.
if( !( fabs( p_collision->m_at.m_x - p_a->m_horizontalMidpoint ) < p_a->m_width / 2 ))
goto l_END_OF_FUNCTION;

// ii.
{
const double d = fabs( p_collision->m_at.m_y - p_a->m_verticalMidpoint );
if( !(( d == 0 ) || ( d < p_a->m_height / 2 )))
goto l_END_OF_FUNCTION;
}

// iii.
if( !( fabs( p_collision->m_at.m_y - p_b->m_verticalMidpoint ) < p_b->m_height / 2 ))
goto l_END_OF_FUNCTION;

p_collision->m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
l_END_OF_FUNCTION:return true;
}
return false;
}

// The following function assumes that p_b->m_type != k_LINE_TYPE__VERTICAL, that the two lines are neither coincident nor parallel, and that p_collision->m_detected == k_LINE_LINE_COLLISION_DETECTED__NO.
// Again, it would be helpful if Leonardo IDE treated the inline qualifier as a no-op if it doesn't support that qualifier…
static /* inline */ bool f_LineLineCollision_Algorithm4( const t_Line * const p_a, const t_Line * const p_b, t_LineLineCollision *p_collision )
{
if( p_a->m_type == k_LINE_TYPE__NON_HORIZONTAL_AND_NON_VERTICAL )
{
p_collision->m_at.m_x = ( p_b->m_yIntercept - p_a->m_yIntercept ) / ( p_a->m_slope - p_b->m_slope );
p_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 );

// i.
if( !( fabs( p_collision->m_at.m_x - p_a->m_horizontalMidpoint ) < p_a->m_width / 2 ))
goto l_END_OF_FUNCTION;

// ii.
if( !( fabs( p_collision->m_at.m_y - p_a->m_verticalMidpoint ) < p_a->m_height / 2 ))
goto l_END_OF_FUNCTION;

// iii.
if( !( fabs( p_collision->m_at.m_x - p_b->m_horizontalMidpoint ) < p_b->m_width / 2 ))
goto l_END_OF_FUNCTION;

// iv.
{
const double d = fabs( p_collision->m_at.m_y - p_b->m_verticalMidpoint );
if( !(( d == 0 ) || ( d < p_b->m_height / 2 )))
goto l_END_OF_FUNCTION;
}

p_collision->m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
l_END_OF_FUNCTION:return true;
}
return false;
}

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;

// Algorithm 1.
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 )
if( fabs( p_a->m_horizontalMidpoint - p_b->m_horizontalMidpoint ) < ( p_a->m_width + p_b->m_width ) / 2 )
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
return collision;
}

// Algorithm 2.
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 )
if( fabs( p_a->m_verticalMidpoint - p_b->m_verticalMidpoint ) < ( p_a->m_height + p_b->m_height ) / 2 )
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
return collision;
}

if( f_LineLineCollision_Algorithm3( p_a, p_b, &collision ))
return collision;
if( f_LineLineCollision_Algorithm3( p_b, p_a, &collision ))
return collision;

// Algorithm 5.
if( p_a->m_slope == p_b->m_slope )
{
if( p_a->m_yIntercept == p_b->m_yIntercept )
if( fabs( p_a->m_horizontalMidpoint - p_b->m_horizontalMidpoint ) < ( p_a->m_width + p_b->m_width ) / 2 )
collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
return collision;
}

if( f_LineLineCollision_Algorithm4( p_a, p_b, &collision ))
return collision;
f_LineLineCollision_Algorithm4( p_b, p_a, &collision );
return collision;
}

FILE *g_file = NULL;

void p_Cleanup( void )
{
if( g_file != NULL )
fclose( g_file );
}

char *f_ReadStringFromFile( FILE *p_file, const char p_expectedTerminatorCharacter, char *p_actualTerminatorCharacter, bool *p_endOfFileEncountered )
{
char c, *s = ( char* )malloc( sizeof( char ));
size_t s_length = 1;
*p_endOfFileEncountered = true;
while( fscanf( p_file, "%c", &c ) != EOF )
{
if(( c == '\n' ) || ( c == p_expectedTerminatorCharacter ))
{
*p_actualTerminatorCharacter = c;
*p_endOfFileEncountered = false;
break;
}
s = realloc( s, s_length + 1 );
s[ s_length - 1 ] = c;
s_length ++;
}
s[ s_length - 1 ] = '\0';
return s;
}

int f_ReadCoordinateFromFile( FILE *p_file, const char p_expectedTerminatorCharacter, const bool p_endOfFileMayBeEncountered, bool *p_endOfFileEncountered, const char * const p_coordinateLabel, const char p_lineLabel )
{
char actual_terminator_character, *s = f_ReadStringFromFile( p_file, p_expectedTerminatorCharacter, &actual_terminator_character, p_endOfFileEncountered );
int coordinate;
if( *p_endOfFileEncountered && !p_endOfFileMayBeEncountered )
{
free( s );
fprintf( stderr, "Sorry, an error occurred: the end of the test data file was unexpectedly encountered whilst trying to read the %s coordinate of line %c.\n", p_coordinateLabel, p_lineLabel );
exit( EXIT_FAILURE );
}
if( !*p_endOfFileEncountered && ( actual_terminator_character != p_expectedTerminatorCharacter ))
{
free( s );
fprintf( stderr, "Sorry, an error occurred: an end of line was unexpectedly encountered whilst trying to read the %s coordinate of line %c.\n", p_coordinateLabel, p_lineLabel );
exit( EXIT_FAILURE );
}
coordinate = f_seal_StringToInt_C( s );
if( f_seal_StringToInt_Error_C() != k_seal_STRING_TO_INT_ERROR_C__NONE )
{
fprintf( stderr, "Sorry, an error occurred: the string \"%s\" could not be converted into an int/the %s coordinate of line %c.\n", s, p_coordinateLabel, p_lineLabel );
free( s );
exit( EXIT_FAILURE );
}
free( s );
if(( coordinate < -10 ) || ( coordinate > 10 ))
{
fprintf( stderr, "Sorry, an error occurred: the %s coordinate of line %c is not [ -10, 10 ].\n", p_coordinateLabel, p_lineLabel );
exit( EXIT_FAILURE );
}
return coordinate;
}

t_Line f_ReadLineFromFile( FILE *p_file, bool *p_endOfFileEncountered, const char p_lineLabel )
{
int x1, y1, x2, y2;
x1 = f_ReadCoordinateFromFile( p_file, ' ', false, p_endOfFileEncountered, "x1", p_lineLabel );
y1 = f_ReadCoordinateFromFile( p_file, ' ', false, p_endOfFileEncountered, "y1", p_lineLabel );
x2 = f_ReadCoordinateFromFile( p_file, ' ', false, p_endOfFileEncountered, "x2", p_lineLabel );
y2 = f_ReadCoordinateFromFile( p_file, ( p_lineLabel == 'A' )?' ':'\n', p_lineLabel != 'A', p_endOfFileEncountered, "y2", p_lineLabel );
return f_NewLine( x1, y1, x2, y2 );
}

void main( void )
{
t_Line A;
/**
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 );
**/
bool end_of_file_encountered;
t_Line B;
/**
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 );
**/
t_LineLineCollision collision;
/**
Ellipse( Out 3, 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;
**/
bool collision_detected = false;
/**
EllipseFrameColor( 3, Out C, 0 )
Assign C = ( !collision_detected )?Magenta:LightGreen;
**/
atexit( p_Cleanup );
printf( "Please select the test data file.\n" );
printf( "\n" );
{
char file_path[ 1024 ];
if( GetFileDialog( file_path ) == 0 )
{
fprintf( stderr, "Sorry, an error occurred: no test data file was selected.\n" );
exit( EXIT_FAILURE );
}
if(( g_file = fopen( file_path, "r" )) == NULL )
{
fprintf( stderr, "Sorry, an error occurred: the selected test data file \"%s\" could not be opened.\n", file_path );
exit( EXIT_FAILURE );
}
}
do
{
A = f_ReadLineFromFile( g_file, &end_of_file_encountered, 'A' );
B = f_ReadLineFromFile( g_file, &end_of_file_encountered, 'B' );
collision.m_at.m_x = 0;
collision.m_at.m_y = 0;
collision = f_LineLineCollision( &A, &B );
collision_detected = collision.m_detected != k_LINE_LINE_COLLISION_DETECTED__NO;
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 );
else
if( collision.m_detected == k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT )
printf( " – the lines are coincident" );
printf( ".\n" );
printf( "\n" );
printf( "Please press the Return key to %s.", ( !end_of_file_encountered )?"continue":"quit this program" );
{
char ignored_char;
bool ignored_bool;
free( f_ReadStringFromFile( stdin, '\n', &ignored_char, &ignored_bool ));
}
if( !end_of_file_encountered )
printf( "\n" );
}
while( !end_of_file_encountered );
exit( EXIT_SUCCESS );
}