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-by-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-by-b=mx
  3. \frac{y-b}{m}=\frac{mx}{m}\frac{y-b}{m}=xx=\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}}=yy=\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 😦
}
Advertisements


No Responses Yet to “Line-line collision detection investigation (part one)”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: