The following is my solution to the “Square Digit Chains” problem posed by Programming Praxis; I’d usually post my solution as a comment on that ‘site, but I learned after I posted as a comment on that ‘site my solution to the “Emirps” problem posed by that ‘site that that ‘site doesn’t support images in comments.

Lacking a “recent-vintage personal computer” – my solutions to the problems posed by the aforementioned ‘site are programmed- and run- on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) – and wanting to test my understanding of: compiling a project using a Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition) project with multiple targets; compiling a project using the command line; and compiling a project using a makefile with multiple targets; understanding that might be necessary if I’m to release an executable of my SDL2 joystick interrogator utility, or of my entry for Ludum Dare 5, for the Raspberry Pi, I interpreted the instruction that I should abide by “the usual Project Euler rule that your computation may take no more than a minute of computation on a recent-vintage personal computer” as an invitation to compare two methods for arriving at the result:

  1. a “brute force” method: if n is a starting number in the range \left[ 1,9999999 \right], the number chains beginning with n are formed, so determining the number of chains beginning with n that will eventually arrive at 89;
  2. and what I thought would be a more-optimised method: if n is a starting number in the range \left[ 1,9999999 \right] then the minimum sum of the squares of the digits of n is 1\cdot 1^{2}=1 and the maximum sum of the squares of the digits of n is 7\cdot 9^{2}=567; therefore, a binary tree is populated with pairs of the starting numbers in the range \left[ 1,567 \right] and the numbers that those starting numbers will eventually arrive at, and – rather than forming the number chains beginning with n as in the “brute force” method – that binary tree is used to look up the numbers that the sum of the squares of the digits of n will eventually arrive at, so determining the number of chains beginning with n that will eventually arrive at 89.

The results were surprising: not only was the first, “brute force”, method faster than the second, more-optimised, method (when running on both Mac OS 9.2.2 (International English), the program compiled using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition), and Mac OS X 10.4.11, the program compiled using the command line: make method_1 and make method_2), but the first method arrived at the result in less than a minute (when running on Mac OS X 10.4.11) in spite of running on my aforementioned far from “recent-vintage personal computer”.

(I’m just trying to solve the problems posed by the aforementioned ‘site whilst I try to get a job; I’m well-aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

Output:

It is stated that a number chain is formed by continuously summing together the squares of the digits of a number to form a new number, terminating when the "new" number so formed has already been encountered earlier in the chain.

Eg.
	44 -> 32 -> 13 -> 10 -> 1 -> 1
Or eg.
	85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89

Furthermore, it is stated that any starting number will eventually arrive at either 1 or 89.

Fri Oct 19 09:00:00 2018

8581146 starting numbers in the range [ 1, 9999999 ] will eventually arrive at 89.

Fri Oct 19 09:00:18 2018

October 19th, 2018.cpp:

#include "printDateAndTime.h" /* <http://Gist.GitHub.com/sealfin/6d35f3a3958bd6797a0f> */
#include <stdio.h>
#include <stdlib.h>

unsigned int g_limit = 9999999;

unsigned int f_SumOfSquaresOfDigits( unsigned int p )
{
  unsigned int sum_of_squares_of_digits = 0;

  while( p > 0 )
  {
    const unsigned int digit = p % 10;

    p /= 10;
    sum_of_squares_of_digits += ( digit * digit );
  }
  return sum_of_squares_of_digits;
}

unsigned int g_numberOfStartingNumbersThatArriveAt89 = 0;

void p_DetermineNumberOfStartingNumbersThatArriveAt89( void );

int main( const int argc, const char * const argv[] )
{
  #ifndef __MWERKS__
  printf( "\n" );
  #endif

  printf( "It is stated that a number chain is formed by continuously summing together the squares of the digits of a number to form a new number, terminating when the \"new\" number so formed has already been encountered earlier in the chain.\n\n" );
  printf( "Eg.\n" );
  printf( "\t44 -> 32 -> 13 -> 10 -> 1 -> 1\n" );
  printf( "Or eg.\n" );
  printf( "\t85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89\n\n" );
  printf( "Furthermore, it is stated that any starting number will eventually arrive at either 1 or 89.\n\n" );

  p_PrintDateAndTime();
  p_DetermineNumberOfStartingNumbersThatArriveAt89();
  printf( "\n" );
  if( g_numberOfStartingNumbersThatArriveAt89 == 0 )
    printf( "No" );
  else
    printf( "%u", g_numberOfStartingNumbersThatArriveAt89 );
  printf( " starting number%s in the range [ 1, %u ] will eventually arrive at 89.\n\n", ( g_numberOfStartingNumbersThatArriveAt89 != 1 )?"s":"", g_limit );
  p_PrintDateAndTime();

  #ifndef __MWERKS__
  printf( "\n" );
  #endif

  exit( EXIT_SUCCESS );
}

method #1.cpp:

extern unsigned int g_limit;

unsigned int f_SumOfSquaresOfDigits( unsigned int p );

extern unsigned int g_numberOfStartingNumbersThatArriveAt89;

void p_DetermineNumberOfStartingNumbersThatArriveAt89( void )
{
  unsigned int i = 1;

  for( ; i <= g_limit; i ++ )
  {
    unsigned int k = i;

    while(( k != 1 ) && ( k != 89 ))
      k = f_SumOfSquaresOfDigits( k );
    if( k == 89 )
      g_numberOfStartingNumbersThatArriveAt89 ++;
  }
}

method #2.cpp:

#include "seal_tree.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_tree.h> */

static size_t f_NumberOfDigits( unsigned int p )
{
  if( p == 0 )
    return 1;

  size_t number_of_digits = 0;

  do
  {
    number_of_digits ++;
    p /= 10;
  }
  while( p > 0 );
  return number_of_digits;
}

extern unsigned int g_limit;

typedef struct t_NumberArrivesAt_TreeNode_struct
{
  unsigned int m_number;
  bool m_arrivesAtSet;
  unsigned int m_arrivesAt;
}
t_NumberArrivesAt_TreeNode;

class NumberArrivesAt_Tree : public seal_Tree<t_NumberArrivesAt_TreeNode, unsigned int>
{
  public:
    NumberArrivesAt_Tree( void )
    {
      p_SetNumber( 1 );
      p_SetArrivesAt( 1 );
      p_SetNumber( 89 );
      p_SetArrivesAt( 89 );
    }

    void p_SetNumber( unsigned int p )
    {
      t_NumberArrivesAt_TreeNode n;

      n.m_number = p;
      n.m_arrivesAtSet = false;
      seal_Tree<t_NumberArrivesAt_TreeNode, unsigned int>::p_Set( n );
    }

    void p_SetArrivesAt( unsigned int p )
    {
      p_SetArrivesAt( m_root, p );
    }

  private:
    void p_SetArrivesAt( struct t_seal_TreeNode<t_NumberArrivesAt_TreeNode> * const p_n, const unsigned int p_arrivesAt )
    {
      if( p_n != NULL )
      {
        p_SetArrivesAt( p_n->m_l, p_arrivesAt );
        if( !p_n->m_content.m_arrivesAtSet )
        {
          p_n->m_content.m_arrivesAtSet = true;
          p_n->m_content.m_arrivesAt = p_arrivesAt;
        }
        p_SetArrivesAt( p_n->m_r, p_arrivesAt );
      }
    }

  public:
    unsigned int f_GetArrivesAt( unsigned int p )
    {
      return f_Get( p ).m_arrivesAt;
    }

  private:
    t_seal_TREE_BRANCH_DIRECTION f_Compare_TT( t_NumberArrivesAt_TreeNode p_old, t_NumberArrivesAt_TreeNode p_new )
    {
      if( p_new.m_number < p_old.m_number )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_new.m_number == p_old.m_number )
        return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
    }

    t_seal_TREE_BRANCH_DIRECTION f_Compare_TU( t_NumberArrivesAt_TreeNode p_content, unsigned int p_identifier )
    {
      if( p_identifier < p_content.m_number )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_identifier == p_content.m_number )
        return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
    }

    t_NumberArrivesAt_TreeNode f_IsNotInTree( unsigned int p )
    {
    }
};

unsigned int f_SumOfSquaresOfDigits( unsigned int p );

extern unsigned int g_numberOfStartingNumbersThatArriveAt89;

void p_DetermineNumberOfStartingNumbersThatArriveAt89( void )
{
  unsigned int i = 1;
  const unsigned int limit = f_NumberOfDigits( g_limit ) * 9 * 9;
  NumberArrivesAt_Tree number_arrives_at;

  for( ; i <= limit; i ++ )
  {
    unsigned int k = i;

    while( !number_arrives_at.f_IsInTree( k ))
    {
      number_arrives_at.p_SetNumber( k );
      k = f_SumOfSquaresOfDigits( k );
    }
    number_arrives_at.p_SetArrivesAt( number_arrives_at.f_GetArrivesAt( k ));
  }
  for( i = 1; i <= g_limit; i ++ )
    if( number_arrives_at.f_GetArrivesAt( f_SumOfSquaresOfDigits( i )) == 89 )
      g_numberOfStartingNumbersThatArriveAt89 ++;
}

Makefile:

error:
	echo "Sorry, an error occurred: you must specify either \"method_1\" or \"method_2\"."

common: printDateAndTime.h printDateAndTime.c October\ 19th,\ 2018.cpp
	g++ -c printDateAndTime.c
	g++ -c October\ 19th,\ 2018.cpp

method_1: common method\ \#1.cpp
	g++ -c method\ \#1.cpp
	g++ printDateAndTime.o method\ \#1.o October\ 19th,\ 2018.o -o Method\ \#1
	rm printDateAndTime.o
	rm method\ \#1.o
	rm October\ 19th,\ 2018.o

method_2: common seal_tree.h method\ \#2.cpp
	g++ -c method\ \#2.cpp
	g++ printDateAndTime.o method\ \#2.o October\ 19th,\ 2018.o -o Method\ \#2
	rm printDateAndTime.o
	rm method\ \#2.o
	rm October\ 19th,\ 2018.o
Advertisements

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 controller with an analogue stick to play I’ve begun to develop a utility to interrogate the capabilities of various controllers; and, as I feel that the SDL2 documentation is lacking with regards to the joystick support offered by that library, I’ve posted – in addition to an executable of that utility for Mac OS X (and I want to release executables for additional platforms – the Raspberry Pi in particular – in the future) – the source code to that utility to GitHub for the benefit both of myself and of others.

Note that to use the utility you will need to have SDL2_image – in addition to SDL2 – installed.

Amongst the changes in version 2.0 of the utility are that:

  • the utility now features support for multiple controllers;
  • the utility now features detection of POV hats (and, contrary to what I wrote in the past, the D-pad of the Sony PlayStation 2 DualShock 2 controller is not disabled in analogue mode – rather, it is in that mode detected as being a POV hat (at least using my PlayStation-to-USB adapter));
  • the utility now features preliminary detection of trackballs – “preliminary” as neither of my controllers (the other being a Sony PlayStation 3 DualShock 3) features a trackball;
  • the utility now features preliminary detection of whether or not a controller has haptic capabilities – “preliminary” as neither of my controllers has been detected as having haptic capabilities in spite of both of my controllers having haptic capabilities (although my adapter or my OS (Mac OS X 10.6 Snow Leopard) might be to blame).

The following is my solution to the “8/10 Palindromes” problem posed by Programming Praxis; I’d usually post my solution as a comment on that ‘site, but I learned after I posted as a comment on that ‘site my solution to the “Emirps” problem posed by that ‘site that that ‘site doesn’t support images in comments.

My solution is known to run on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) on both Mac OS 9.2.2 (International English) (my solution interpreted using Leonardo IDE 3.4.1) and Mac OS X 10.4.11 (my solution compiled using the command line: make).

(I’m just trying to solve the problems posed by the aforementioned ‘site whilst I try to get a job (and I’ve solved this problem in particular to test my understanding of: compiling a project using the command line; compiling a project using a makefile; and compiling a project wherein a function is defined – not just declared – in a header file, and wherein that function is subsequently invoked in multiple source code files; understanding that might be necessary if I’m to release an executable of my SDL2 joystick interrogator utility, or of my entry for Ludum Dare 5, for the Raspberry Pi); I’m well-aware that my solutions to the problems posed by the aforementioned ‘site are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

int to string.h:

#include <stdlib.h>
#include <limits.h>

typedef unsigned long
#ifndef LEONARDO
long
#endif
t_UnsignedLongInt;

static size_t f_NumberOfDigits( unsigned int p_int, const unsigned int p_base )
{
  if( p_int == 0 )
    return 1;
  else
  {
    size_t number_of_digits = 0;

    while( p_int > 0 )
    {
      number_of_digits ++;
      p_int /= p_base;
    }
    return number_of_digits;
  }
}

const char * const f_IntToString( unsigned int p_int, const unsigned int p_base )
{
  static char *string = NULL;
  t_UnsignedLongInt divisor = 1;
  size_t i = 0;

  if( p_base == 0 )
  {
    if( string != NULL )
      free( string );
    string = NULL;
    return NULL;
  }
  if( string == NULL )
  {
    const size_t octal = f_NumberOfDigits( UINT_MAX, 8 ) + 1;
    const size_t denary = f_NumberOfDigits( UINT_MAX, 10 ) + 1;
    size_t string_length;

    if( octal > denary )
      string_length = octal;
    else
      string_length = denary;
    string = ( char* )malloc( sizeof( char ) * string_length );
  }
  if( p_int == 0 )
  {
    string[ 0 ] = '0';
    string[ 1 ] = '\0';
    return string;
  }
  while( p_int / divisor > 0 )
    divisor *= p_base;
  divisor /= p_base;
  while( divisor > 0 )
  {
    const unsigned int digit = p_int / divisor;

    p_int -= ( digit * divisor );
    divisor /= p_base;
    string[ i ++ ] = '0' + digit;
  }
  string[ i ] = '\0';
  return string;
}

int to octal string.c:

const char * const f_IntToString( unsigned int p_int, const unsigned int p_base );

const char * const f_IntToOctalString( const unsigned int p )
{
  return f_IntToString( p, 8 );
}

int to denary string.c:

const char * const f_IntToString( unsigned int p_int, const unsigned int p_base );

const char * const f_IntToDenaryString( const unsigned int p )
{
  return f_IntToString( p, 10 );
}

July 10th, 2018.c:

#include "int to string.h"
#include "seal_bool.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_bool.h> */
#include <string.h>
#include <ctype.h>
#include <stdio.h>

bool f_StringToInt( const char * const p_input, unsigned int * const p_output )
/*
Returns true if:
* p_input points to a string comprised of – and only of – one or more digits in the range [ 0, 9 ];
* and the number represented by the string pointed to by p_input is in the range [ 0, UINT_MAX ].
*/
{
  size_t i = 0;
  bool any_digits_encountered = false;
  t_UnsignedLongInt number = 0;

  for( ; i < strlen( p_input ); i ++ )
  {
    const char c = p_input[ i ];

    if( isdigit( c ))
    {
      any_digits_encountered = true;
      number *= 10;
      if( number > UINT_MAX )
        return false;
      number += ( c - '0' );
      if( number > UINT_MAX )
        return false;
    }
    else
      return false;
  }
  if( !any_digits_encountered )
    return false;
  *p_output = number;
  return true;
}

bool f_IsPalindrome( const char * const p )
{
  size_t i = 0, k = strlen( p ) - 1;

  while( i < k )
  {
    if( p[ i ] != p[ k ] )
      return false;
    i ++;
    k --;
  }
  return true;
}

const char * const f_IntToOctalString( const unsigned int p );
const char * const f_IntToDenaryString( const unsigned int p );

int main( const int argc, const char * const argv[] )
{
  const size_t index = 
  #ifdef LEONARDO
  0
  #else
  1
  #endif
  ;
  bool error_occurred = argc - 1 != index;
  unsigned int limit;

  if( !error_occurred )
    error_occurred = !f_StringToInt( argv[ index ], &limit );
  #ifndef LEONARDO
  printf( "\n" );
  #endif
  if( !error_occurred )
  {
    t_UnsignedLongInt i = 0;
    unsigned int number_of_palindromes = 0, *palindromes;

    for( ; i <= limit; i ++ )
      if( f_IsPalindrome( f_IntToOctalString( i )))
        if( f_IsPalindrome( f_IntToDenaryString( i )))
        {
          if( number_of_palindromes == 0 )
            palindromes = ( unsigned int* )malloc( sizeof( unsigned int ));
          else
            palindromes = ( unsigned int* )realloc( palindromes, sizeof( unsigned int ) * ( number_of_palindromes + 1 ));
          palindromes[ number_of_palindromes ++ ] = i;
        }
    printf( "The integer" );
    if( number_of_palindromes > 1 )
      printf( "s" );
    printf( " in the range [ 0, %u ] that ", ( unsigned int )limit );
    if( number_of_palindromes > 1 )
      printf( "are" );
    else
      printf( "is a" );
    printf( " palindrome" );
    if( number_of_palindromes > 1 )
      printf( "s" );
    printf( " in both octal and denary " );
    if( number_of_palindromes > 1 )
      printf( "are" );
    else
      printf( "is" );
    printf( ": " );
    for( i = 0; i < number_of_palindromes; i ++ )
    {
      if( i > 0 )
      {
        if( number_of_palindromes != 2 )
          printf( "," );
        printf( " " );
        if( i + 1 == number_of_palindromes )
          printf( "and " );
      }
      printf( "%u", palindromes[ i ] );
    }
    printf( ".\n" );
    free( palindromes );
    f_IntToString( 0, 0 );
  }
  else
    printf( "This program must be passed, via the command line, a denary integer in the range [ 0, %u ]; this program will then print (in denary) the integers from zero to (and including) that integer that are palindromes in both octal and denary.\n", ( unsigned int )UINT_MAX );
  #ifndef LEONARDO
  printf( "\n" );
  #endif
  if( !error_occurred )
    exit( EXIT_SUCCESS );
  else
    exit( EXIT_FAILURE );
}

Makefile:

main: int\ to\ string.h int\ to\ octal\ string.c int\ to\ denary\ string.c seal_bool.h July\ 10th,\ 2018.c
	gcc -c int\ to\ octal\ string.c
	gcc -c int\ to\ denary\ string.c
	gcc int\ to\ octal\ string.o int\ to\ denary\ string.o July\ 10th,\ 2018.c -o July\ 10th,\ 2018

As yesterday was the deadline for the submission of solutions to the problems posed by WJEC GCSE Computer Science for the unit 3 (“Developing Computing Solutions”) controlled assessment, today I’m posting my solution to one of the two problems posed: “Lucky Name Numbers”.

(I’m not studying for that qualification – I developed my solution to that problem as part of an investigation into improving the teaching and assessment of that qualification (and of GCSEs in the STEM subjects more generally) and making the teaching and assessment of those qualifications available to more students (more specifically to students who are studying at schools which don’t offer those qualifications or who are, like myself, not in secondary education).)


Deacon

01Sep16

I’ve just achieved the rank of “deacon” at CodeAbbey for solving one hundred and five problems.


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+by=0x+by=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 );
}

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 😦
}

Fanatic

29Jun16

I’ve just achieved the rank of “fanatic” at CodeAbbey for solving eighty-five problems.


[…]

The Advent Programming Contest, being organized by the IEEE Student Branch Klagenfurt[,] will provide a new problem every day from December 1st to December 24th. You can submit solutions any day until the contest ends on December 26[th]. You can choose to use C, C++, C#, Java, Perl, Python 2.x or Python 3.x as programming language.

[…]

Until a solution is correct you can submit your program as often as you want (but please don’t spam our server).

[…]

The event is open to everyone.

[…]

If you want to participate, please register at http://mooshak.nes.aau.at/ (Registration is also possible after 1st December)[.]

– Wilfried Elmenreich

Source: Advent Programming Contest 2015 [Self-Organizing Networked Systems, 30th November 2015]


Interrogating a Sony PlayStation 2 DualShock 2 controller; I've yet to figure out why SDL2 reports that the DualShock 2 has five axes (although my PlayStation-to-USB adapter might be to blame), I've yet to figure out a solution – which doesn't involve a ⅓ axis dead zone – to the problem of the thumbsticks on the DualShock 2 not always returning all the way to the origin when they're released, and I last touched a DualShock 2 a long, long time ago so I'd forgotten that the D-pad is disabled in analogue mode :/

Interrogating a Sony PlayStation 2 DualShock 2 controller; I’ve yet to figure out why SDL2 reports that the DualShock 2 has five axes (although my PlayStation-to-USB adapter might be to blame), I’ve yet to figure out a solution – which doesn’t involve a ⅓ axis dead zone – to the problem of the thumbsticks on the DualShock 2 not always returning all the way to the origin when they’re released, and I last touched a DualShock 2 a long, long time ago so I’d forgotten that the D-pad is disabled in analogue mode :/

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 controller with an analogue stick to play I’ve begun to develop a utility to interrogate the capabilities of various controllers – and as I feel that the SDL2 documentation is lacking with regards to the joystick support offered by that library I’m posting here the source code to the third version of that utility, for the benefit both of myself and of others.

SDL2 joystick interrogator.mm:

#include <SDL2/SDL.h>
#include "seal_intToString.h"
#include "seal_stringConcatenation.h"
#include "seal_stringQueue.h"
#include "seal_tree.h"
#include "seal_tileBackground.h"

void p_StringToTileBackground( const char * const p_string, seal_TileBackground *p_tileBackground )
{
  const size_t transparent_sub_texture = 10 /* '0'..'9' */ + 26 /* 'A'..'Z' */ + 5 /* '+', '-', '.', '(', ')' */;
  p_tileBackground->p_SetAllSubTextures( transparent_sub_texture );
  size_t i = 0;
  int x = 0, y = p_tileBackground->f_Height() - 1;
  for( ; i < strlen( p_string ); i ++, x ++ )
  {
    const char character = p_string[ i ];
    size_t sub_texture = transparent_sub_texture;
    if(( character >= '0' ) && ( character <= '9' ))
      sub_texture = character - '0';
    else
      if(( character >= 'a' ) && ( character <= 'z' ))
        sub_texture = character - 'a' + 10;
      else
        if(( character >= 'A' ) && ( character <= 'Z' ))
          sub_texture = character - 'A' + 10;
        else
          switch( character )
          {
            case '+': sub_texture = 36; break;
            case '-': sub_texture = 37; break;
            case '.': sub_texture = 38; break;
            case '(': sub_texture = 39; break;
            case ')': sub_texture = 40;
          }
    if( character == '\n' )
    {
      x = -1;
      y --;
    }
    else
      p_tileBackground->p_SetSubTexture( x, y, sub_texture );
  }
}

static seal_Texture *g_font;
static seal_TileBackground *g_number_of_joysticks_background;

void p_UpdateNumberOfJoysticksBackground( void )
{
  const int number_of_joysticks = SDL_NumJoysticks();
  char *number_of_joysticks_string = f_seal_IntToString( number_of_joysticks, false );
  char *message = f_seal_ConcatenateStrings(( number_of_joysticks == 0 )?( char* )"No":number_of_joysticks_string, " joystick", ( number_of_joysticks == 1 )?"":"s", " detected.", NULL );
  free( number_of_joysticks_string );
  p_StringToTileBackground( message, g_number_of_joysticks_background );
  free( message );
}

typedef struct t_JoystickTreeNode_struct
{
  SDL_JoystickID m_instanceId;
  bool m_open;
  SDL_Joystick *m_joystick;

  seal_TileBackground *m_nameBackground;

  int m_numberOfButtons;
  bool *m_buttonPressed;
  seal_TileBackground *m_buttonsPressedBackground;

  int m_numberOfAxes;
  Sint16 *m_axis;
  seal_TileBackground *m_axesBackground;
}
t_JoystickTreeNode;

class JoystickTree : public seal_Tree<t_JoystickTreeNode*, SDL_JoystickID>
{
  private:
    t_JoystickTreeNode *m_mostRecentlyAdded;

  public:
    JoystickTree( void )
    {
      m_mostRecentlyAdded = NULL;
    }

    void p_Open( const Sint32 p )
    {
      SDL_Joystick *joystick = SDL_JoystickOpen( p );
      const SDL_JoystickID instanceId = SDL_JoystickInstanceID( joystick );
      t_JoystickTreeNode *n = f_Get( instanceId );
      if( n == NULL )
      {
        n = ( t_JoystickTreeNode* )malloc( sizeof( t_JoystickTreeNode ));
        p_Set( n );
      }
      n->m_instanceId = instanceId;
      n->m_open = true;
      n->m_joystick = joystick;

      const char * const name = ( SDL_JoystickName( joystick ) != NULL )?SDL_JoystickName( joystick ):"NULL";
      n->m_nameBackground = new seal_TileBackground( g_font, strlen( name ), 1 );
      p_StringToTileBackground( name, n->m_nameBackground );

      n->m_numberOfButtons = SDL_JoystickNumButtons( joystick );
      n->m_buttonPressed = ( bool* )malloc( sizeof( bool ) * n->m_numberOfButtons );
      int i = 0;
      for( ; i < n->m_numberOfButtons; i ++ )
        n->m_buttonPressed[ i ] = SDL_JoystickGetButton( joystick, i );
      n->m_buttonsPressedBackground = new seal_TileBackground( g_font, 13, n->m_numberOfButtons + 1 );
      p_UpdateButtonsPressedBackground( n );

      n->m_numberOfAxes = SDL_JoystickNumAxes( joystick );
      n->m_axis = ( Sint16* )malloc( sizeof( Sint16 ) * n->m_numberOfAxes );
      for( i = 0; i < n->m_numberOfAxes; i ++ )
        n->m_axis[ i ] = SDL_JoystickGetAxis( joystick, i );
      n->m_axesBackground = new seal_TileBackground( g_font, 13, n->m_numberOfAxes + 1 );
      n->m_axesBackground->p_SetBottomLeftX( n->m_buttonsPressedBackground->f_Right());
      p_UpdateAxesBackground( n );

      n->m_nameBackground->p_SetBottomLeftY( n->m_buttonsPressedBackground->f_Top());

      m_mostRecentlyAdded = n;
    }

    void p_Close( const Sint32 p )
    {
      t_JoystickTreeNode *n = f_Get( p );
      if(( n != NULL ) && ( n->m_open ))
        p_Delete( n );
    }

    void p_PressButton( const SDL_JoystickID p_instanceId, const Uint8 p_button )
    {
      t_JoystickTreeNode *n = f_Get( p_instanceId );
      if(( n != NULL ) && ( n->m_open ))
      {
        n->m_buttonPressed[ p_button ] = true;
        p_UpdateButtonsPressedBackground( n );
      }
    }

    void p_ReleaseButton( const SDL_JoystickID p_instanceId, const Uint8 p_button )
    {
      t_JoystickTreeNode *n = f_Get( p_instanceId );
      if(( n != NULL ) && ( n->m_open ))
      {
        n->m_buttonPressed[ p_button ] = false;
        p_UpdateButtonsPressedBackground( n );
      }
    }

    void p_MoveAxis( const SDL_JoystickID p_instanceID, const Uint8 p_axis, const Sint16 p_value )
    {
      t_JoystickTreeNode *n = f_Get( p_instanceID );
      if(( n != NULL ) && ( n->m_open ))
      {
        n->m_axis[ p_axis ] = p_value;
        p_UpdateAxesBackground( n );
      }
    }

    void p_Render( void )
    {
      if(( m_mostRecentlyAdded != NULL ) && ( m_mostRecentlyAdded->m_open ))
      {
        m_mostRecentlyAdded->m_nameBackground->p_Render();
        m_mostRecentlyAdded->m_buttonsPressedBackground->p_Render();
        m_mostRecentlyAdded->m_axesBackground->p_Render();
      }
    }

  private:
    t_seal_TREE_BRANCH_DIRECTION f_Compare_TT( t_JoystickTreeNode *p_old, t_JoystickTreeNode *p_new )
    {
      if( p_new->m_instanceId < p_old->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_new->m_instanceId > p_old->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
    }

    t_seal_TREE_BRANCH_DIRECTION f_Compare_TU( t_JoystickTreeNode *p_content, SDL_JoystickID p_identifier )
    {
      if( p_identifier < p_content->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_identifier > p_content->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
    }

    t_JoystickTreeNode *f_IsNotInTree( SDL_JoystickID p )
    {
      return NULL;
    }

    void p_Delete( t_JoystickTreeNode *p )
    {
      if( p->m_open )
      {
        p->m_open = false;
        SDL_JoystickClose( p->m_joystick );
        delete p->m_nameBackground;
        free( p->m_buttonPressed );
        delete p->m_buttonsPressedBackground;
        free( p->m_axis );
        delete p->m_axesBackground;
      }
    }

    void p_UpdateButtonsPressedBackground( t_JoystickTreeNode *p )
    {
      seal_StringQueue sQ;
      if( p->m_numberOfButtons == 0 )
        sQ.p_Push(( char* )"No buttons" );
      else
      {
        sQ.p_Push(( char* )"Buttons (" );
        char *number_of_buttons = f_seal_IntToString( p->m_numberOfButtons, false );
        sQ.p_Push( number_of_buttons );
        free( number_of_buttons );
        sQ.p_Push(( char* )")\n" );
      }
      int i = 0;
      for( ; i < p->m_numberOfButtons; i ++ )
      {
        if(( p->m_numberOfButtons >= 100 ) && ( i < 100 ))
          sQ.p_Push(( char* )" " );
        if(( p->m_numberOfButtons >= 10 ) && ( i < 10 ))
          sQ.p_Push(( char* )" " );
        char *i_string = f_seal_IntToString( i, false );
        sQ.p_Push( i_string );
        free( i_string );
        sQ.p_Push(( char* )" .. " );
        sQ.p_Push(( char* )(( !p->m_buttonPressed[ i ] )?"Up":"Down" ));
        if( i + 1 < p->m_numberOfButtons )
          sQ.p_Push(( char* )"\n" );
      }
      char *s = sQ.f_String();
      p_StringToTileBackground( s, p->m_buttonsPressedBackground );
      free( s );
    }

    void p_UpdateAxesBackground( t_JoystickTreeNode *p )
    {
      seal_StringQueue sQ;
      if( p->m_numberOfAxes == 0 )
        sQ.p_Push(( char* )"No axes" );
      else
      {
        sQ.p_Push(( char* )"Axes (" );
        char *number_of_axes = f_seal_IntToString( p->m_numberOfAxes, false );
        sQ.p_Push( number_of_axes );
        free( number_of_axes );
        sQ.p_Push(( char* )")\n" );
      }
      int i = 0;
      for( ; i < p->m_numberOfAxes; i ++ )
      {
        char *i_string = f_seal_IntToString( i, false );
        sQ.p_Push( i_string );
        free( i_string );
        sQ.p_Push(( char* )" .. " );
        char *axis = f_seal_IntToString( p->m_axis[ i ], true );
        sQ.p_Push( axis );
        free( axis );
        if( i + 1 < p->m_numberOfAxes )
          sQ.p_Push(( char* )"\n" );
      }
      char *s = sQ.f_String();
      p_StringToTileBackground( s, p->m_axesBackground );
      free( s );
    }
};

int main( const int argc, const char * const argv[] )
{
  const int W = 494, H = 304;

  SDL_Init( SDL_INIT_VIDEO | SDL_INIT_JOYSTICK );
  SDL_Window *window = SDL_CreateWindow( "SDL2 joystick interrogator", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W, H, SDL_WINDOW_OPENGL );
  SDL_GLContext context = SDL_GL_CreateContext( window );

  glMatrixMode( GL_PROJECTION );
  glLoadIdentity();
  glOrtho( 0, W, 0, H, -1, 1 );
  glMatrixMode( GL_MODELVIEW );
  glClearColor( 0.5, 0.5, 0.5, 1.0 );
  glEnable( GL_TEXTURE_2D );
  glEnableClientState( GL_VERTEX_ARRAY );
  glEnableClientState( GL_TEXTURE_COORD_ARRAY );

  g_font = new seal_Texture( "font.png", 19, 19 );
  g_number_of_joysticks_background = new seal_TileBackground( g_font, 23, 1 );
  g_number_of_joysticks_background->p_SetBottomLeftY( H - 19 );
  JoystickTree *joysticks = new JoystickTree();

  p_UpdateNumberOfJoysticksBackground();

  bool quit = false;
  do
  {
    SDL_Event event;
    while( SDL_PollEvent( &event ))
      switch( event.type )
      {
        case SDL_QUIT:
          quit = true;
          break;
        case SDL_JOYDEVICEADDED:
          p_UpdateNumberOfJoysticksBackground();
          joysticks->p_Open( event.jdevice.which );
          break;
        case SDL_JOYDEVICEREMOVED:
          p_UpdateNumberOfJoysticksBackground();
          joysticks->p_Close( event.jdevice.which );
          break;
        case SDL_JOYBUTTONDOWN:
          joysticks->p_PressButton( event.jbutton.which, event.jbutton.button );
          break;
        case SDL_JOYBUTTONUP:
          joysticks->p_ReleaseButton( event.jbutton.which, event.jbutton.button );
          break;
        case SDL_JOYAXISMOTION:
          joysticks->p_MoveAxis( event.jaxis.which, event.jaxis.axis, event.jaxis.value );
      }
    glClear( GL_COLOR_BUFFER_BIT );
    g_number_of_joysticks_background->p_Render();
    joysticks->p_Render();
    SDL_GL_SwapWindow( window );
  }
  while( !quit );

  delete joysticks;
  delete g_number_of_joysticks_background;
  delete g_font;

  SDL_GL_DeleteContext( context );
  SDL_DestroyWindow( window );
  SDL_Quit();
  return 0;
}

font.png:

font