A programming challenge all up in your face.

[H_TeXMeX_H]

Much better, good job.

[worker201]

What happens when the decimal point error occurs in the other direction?  Meaning, what if we got -0.99999999999999934442 instead of -1?  Didn't happen in this particular case, but I bet it could.

I think a momentary recast of the argument sent to acos would work better.  Wouldn't have to change all the variables, just that one.  The return from acos will be a double no matter what value you give it.  So why not make it a value with acceptable precision?

[mobrien_12]

What happens when the decimal point error occurs in the other direction?  Meaning, what if we got -0.99999999999999934442 instead of -1?  Didn't happen in this particular case, but I bet it could.

I think a momentary recast of the argument sent to acos would work better.  Wouldn't have to change all the variables, just that one.  The return from acos will be a double no matter what value you give it.  So why not make it a value with acceptable precision?

Yup, but it will just be imprecision then, tiny tiny numerical error.  If the absolute value gets greater than one it's tragic because it breaks the trig function.  

Nothing wrong with error creating a tiny bit of imprecision, it will be smaller than the decimals you see with single precision...we just have to sanity check the data to make sure it doesn't break something.  Your stuff works!

Now does it work with tangents and vertical lines?

[worker201]

Hahahaha, rockstar = me.

Okay, here's the latest fully operational version of the circleline program:
http://www.triple-bypass.net/download/circleline3.txt

It has been cleaned up a bit - at first it made sense to document every step of the messy quadratic equation.  Now, extraneous assignments and variables have been removed.  The calculation of circle arcs and the calculation of distances are both functions, and instead of returning a variable, they return an expression - again, removing unnecessary steps that were once invaluable.

The decimal point error has been corrected, and I am now getting nice accurate values with doubles.  Here's the method:

Code: [Select]

double theta;
double rsquare;
double arc;
float stepone;

rsquare = pow(rad, 2);
stepone = (2 * rsquare - pow(chord, 2)) / (2 * rsquare);
theta = acos(stepone);

By declaring stepone, the argument passed to acos, as a float, I forced the Cosine Law calculation to return a float.  Since all the variables in the equation are doubles, the result is automatically a double.  Because of the declaration, however, the result is converted into a float.  The result is that the double value is truncated to float precision.  Even if you viewed the value of stepone (in the testfile) to 25 places, it is still just -1.  stepone then gets converted back to a double when it is passed to acos.  As you will see below, the results are great.

Also, since the results of acos are precise enough to pass the "== 0" test, my tangent-catcher works.  And vertical lines are handled appropriately, using the calcarc and distancer function just as well as the normal lines.  Horizontal lines are also dealt with appropriately.

Results:

1. normal test case
file1.dat:

Code: [Select]

0
0
10
10
1
5 5 1

Code: [Select]

powbook:~ lholcombe$ ./a.out
Enter a filename for input:
file1.dat
circle # 1 intersects the line, calculating arc distance
Enter a filename for output:
file1.out

file1.out:

Code: [Select]

15.2837

2. horizontal line with tangent circle

file2.dat:

Code: [Select]

0
5
10
5
1
5 6 1

Code: [Select]

powbook:~ lholcombe$ ./a.out
Enter a filename for input:
file2.dat
circle # 1 does not intersect the line (tangent)
Enter a filename for output:
file2.out

file2.out:

Code: [Select]

10

3. vertical line with intersecting circle

file3.dat:

Code: [Select]

0
0
0
10
1
0 5 1

Code: [Select]

powbook:~ lholcombe$ ./a.out
Enter a filename for input:
file3.dat
circle # 1 intersects the line, calculating arc distance
Enter a filename for output:
file3.out

file3.out:

Code: [Select]

11.1416

If anyone has any sensible suggestions for improving this program, please offer them.

[mobrien_12]

Aces!  Two completely different solutions in two different languages for the same problem with the same answer

[solemnwarning]

Aces!  Two completely different solutions in two different languages for the same problem with the same answer

Thats the UNIX way!

[worker201]

So where's the next problem to program?

[piratePenguin]

So where's the next problem to program?

Make a CAD program, methinks.

[worker201]

Did ya happen to notice that it took like 3 weeks to produce a 175 line program?  How long do you think a CAD program would take?

[H_TeXMeX_H]

Well, it doesn't always take that long to make a program (especially if you're not using C or C++). Like it took me 4-6 hours to make a shell script (360 lines or more) that I could use to manage the installation of things like OpenOffice and Firefox which aren't available from the FC repo, or if they are available they are broken or fucked up versions. I also helps bypass some of the dependency problems of RPM.

[piratePenguin]

Wow.. I just went through my old (old) programming crap and found the start I made to this challenge.. and it ain't bad! Dated 05-Feb-2006. Jesus I can't believe this!

http://piratepenguin.is-a-geek.com/~declan/crap/old-stuff/programming/c/curve_challenge/main.c or http://illhostit.com/files/cd815a8f0c8a59847303fe1067003ab0/main.c

It uses glib (linked lists FTW!), so install glib2.0-dev or whatever and compile with: 'gcc main main.c `pkg-config --cflags --libs glib-2.0` -lm'. (WTF: o with a hyphen (-) before it triggers that Forbidden message bug crap)

(it prints the INPUT, and records to stdout and to OUTPUT)

[declan@localhost curve_challenge]$ ./main
line.p1.x: 0
line.p1.y: 0
line.p2.x: 10
line.p2.y: 10
num_circles: 1

circle->c.x: 5
circle->c.y: 5
circle->r: 1

The length of the curve is: 14.142136  [proper answer is apparently 15.2837]

 -- modify input --

[declan@localhost curve_challenge]$ ./main
line.p1.x: 0
line.p1.y: 5
line.p2.x: 10
line.p2.y: 5
num_circles: 1

circle->c.x: 5
circle->c.y: 6
circle->r: 1

The length of the curve is: 10.000000

 -- modify input --

[declan@localhost curve_challenge]$ ./main
line.p1.x: 0
line.p1.y: 0
line.p2.x: 0
line.p2.y: 10
num_circles: 1

circle->c.x: 0
circle->c.y: 5
circle->r: 1

The length of the curve is: 10.000000

Hehheh the tangent stuff works! (I think that's the *only* time it gets it right.. It wasn't complete and I don't feel like completing it, and the bits I don't have are probably the hardest - and why I never bothered to finish it)

Maybe it doesn't work with multiple circles either.. I should comment more heh.

[declan@localhost curve_challenge]$ ./main
line.p1.x: 5
line.p1.y: 0
line.p2.x: 5
line.p2.y: 10
num_circles: 2

circle->c.x: 5
circle->c.y: 5
circle->r: 1

circle->c.x: 20
circle->c.y: 20
circle->r: 2

The length of the curve is: 10.000000

Is that right/wrong?

[mobrien_12]

Penguin, your code seems to be calculating the lines alone and ignoring all the circles.  

You could finish it...

[piratePenguin]

Penguin, your code seems to be calculating the lines alone and ignoring all the circles.  

You could finish it...

Yeah, well, it doesn't do a bad job of it! :p

I looked a bit at the code, and it hurts my eyes, and unfortunetly I don't have time for that anymore

[mobrien_12]

Ok, now that I got Worker to figure out all the problems that might arise in C for me

Here's the vector solution in C.. some of his code blatently ripped off

Code: [Select]

/* 
   vectsoln.c Vector solution in C form
*/

#include 
#include 
#include 
#define TRUE 1
#define FALSE 0
#define FILENAMELENGTH 40
int main()
{
  /* variable declarations */
  
  /* file read/write variables */
  FILE *fRead;
  FILE *fWrite;
  char infilename[FILENAMELENGTH];
  char outfilename[FILENAMELENGTH];
  /* boolean variable type defined */
  typedef int bool;
    
  /* variables declared from input */
  double x1, y1, x2, y2; 
  int i, numcircles;
  double circx[15], circy[15], radius[15];
  
  /* variables of importance */
  double linelength, totalpathlength;
  int numcirclesintersected=0;
  
  /* booleans of interest */
  bool EndNotInCircle, LineInRange, LineLongEnough;

  /* variables for intermediate calculations */
  double s1,s2,p1,p2,disttoline,numerator;
    
  double halfangle, arclength, chordlength, pathdifference;
  
  /* opening the file and reading contents into variables */
  /* printf("Enter a filename for input:\n");
    scanf("%s", &infilename); */
  strncpy(infilename,"data.dat",40);
  fRead =fopen(infilename, "r");
  if (fRead==NULL) 
    {
    printf("input file unavailable\n");
    return 1;
    }
  fscanf(fRead, "%lf", &x1);
  fscanf(fRead, "%lf", &y1);
  fscanf(fRead, "%lf", &x2);
  fscanf(fRead, "%lf", &y2);
  fscanf(fRead, "%d", &numcircles);
  printf("x1 %f y1 %f x2 %f y2 %f numcircles %i\n",x1,y1,x2,y2,numcircles);
    
  if (numcircles>15) 
    {
    printf("too many circles, aborting\n");
    return 1;
    }
  else
    {
    printf("%i circles in file.\n",numcircles);
    for(i=0; i      {
	printf("loading circle %i\n",i);
	fscanf(fRead, "%lf%lf%lf", &circx[i], &circy[i], &radius[i]);
	printf("circledata x %f y %f r %f \n",circx[i],circy[i],radius[i]);
      }
    }

  fclose(fRead);

  /* finished loading data (whew) Start interesting stuff */
  
  linelength = sqrt(pow(x2-x1, 2) + pow(y2-y1, 2));
  totalpathlength=linelength;
  for (i=0; i    {
      numerator=fabs( (x2-x1)*(y1-circy[i]) - (x1-circx[i])*(y2-y1) );
      disttoline= numerator/linelength;
      s1=sqrt( pow((circx[i]-x1),2) + pow((circy[i]-y1),2) );
	/* s2 is distance from line endpoint 2 to center circle */
      s2=sqrt( pow((circx[i]-x2),2) + pow((circy[i]-y2),2) );
	/* p1 is the projection of s1 along the line (vector component) */
      p1=sqrt( pow(s1,2) - pow(disttoline,2) );
	/*  p2 is the projection of s2 along the line (vector component) */
      p2=sqrt( pow(s2,2) - pow(disttoline,2) );
    

	if  ( ( s1 < radius[i] ) || ( s2 < radius[i] ) )
	  { 
	    EndNotInCircle=FALSE;
	  }
	else
	  { 
	    EndNotInCircle=TRUE;
	  }
	
	if ( disttoline < radius[i] )
	  { 
	    LineInRange = TRUE;
	  }
	else
	  {
	    LineInRange = FALSE;
	  }
	
	if  ( ( p1 < linelength ) && ( p2 < linelength ) )
	  { 
	    LineLongEnough=TRUE;
	  }
	else
	  { 
	    LineLongEnough=FALSE;
	  }

	/* key conditional for intersecting a circle */
	if (EndNotInCircle==TRUE && LineInRange==TRUE && LineLongEnough==TRUE)
	  {
	    numcirclesintersected++;
	    halfangle=acos(disttoline/radius[i]);
	    chordlength=2*radius[i]*sin(halfangle);
	    arclength=2*halfangle*radius[i];
	    pathdifference=arclength-chordlength;
	  }
	else
	  {
	    pathdifference=0;
	  }
  
	totalpathlength=totalpathlength+pathdifference;
	
    }

  printf("Total number of circles intersected: %d\n",numcirclesintersected);
  printf("Original path Length %f\n",linelength);
  printf("Final path Length %f\n",totalpathlength);
  /* writing the output to a file */
  /**printf("Enter a filename for output:\n");
     scanf("%s", &outfilename);*/
  strncpy(outfilename,"out.dat",40);
  fWrite = fopen(outfilename, "w");
  if (fWrite==NULL) 
    {
      printf("output file unavailable\n");
      return 1;
    }
  fprintf(fWrite, "%f\n", totalpathlength);
  fclose(fWrite);
  
  return 0;
  
}

0
0
10
10
2
5 5 1
20 20 2

Total number of circles intersected: 1
Original path Length 14.142136
Final path Length 15.283728