A programming challenge all up in your face.

[worker201]

Try a LaTEX reader.  Or run dvips on it to make a PostScript file.  If you have neither, maybe it's update time for you.

[piratePenguin]

I can save it, I just don't know what program can view it ...

evince, the GNOME document viewer can. Rename it to .dvi. You might have to install some package to get the DVI support.. I ain't in Ubuntu atm so I can't find it ..

@worker: ALT + click the link to force-save, apparantly. I can't test it here on gnu/linux 'cause alt + click = move window.

If you're on gnu/linux you might need to go into Edit > Prefs > Content > File Types and remove the download action for pdf/whatever

[H_TeXMeX_H]

Ok, found one ... xdvi. I kept trying tetex, tex, dvi, tetex-dvi, tetex-xdvi, then finally xdvi. (They're not all real I was just trying blindly)

[mobrien_12]

kdvi works too.

[mobrien_12]

Code: [Select]

## Solution to Quirk's challenge problem
## Written by M O'Brien.  Copyright 2006.
## Licenced to others under GPL.
## Language is GNU Octave ([url]http://www.octave.org[/url])

## READ DATA FILE
fileid=fopen("data.dat","rt");
[x1,count]=fscanf(fileid,"%f",1);
[y1,count]=fscanf(fileid,"%f",1);
[x2,count]=fscanf(fileid,"%f",1);
[y2,count]=fscanf(fileid,"%f",1);
[numcircles,count]=fscanf(fileid,"%d",1);
for k=1:numcircles
  [circledat,count]=fscanf(fileid,"%f %f %f",3);
  circx(k)=circledat(1);
  circy(k)=circledat(2);
  radius(k)=circledat(3);
endfor
fclose(fileid);

##  Start the interesting stuff

linelength=sqrt( (x2-x1)**2 + (y2-y1)**2);
totalpathlength=linelength;
numcirclesintersected=0;
for k=1:numcircles
  ##--------------------------------------------------------------------
  ## calculate distance between circle center and the line.
  numerator=abs((x2-x1)*(y1-circy(k)) - \
		(x1-circx(k))*(y2-y1) );
  denominator=sqrt( (x2-x1)**2 + (y2-y1)**2 );
  disttoline=numerator/denominator;
  ##--------------------------------------------------------------------

  if (disttoline < radius(k))
    ## the line is intersecting the current circle, forming a chord.
    ## Only use less than because if it is equal, it is a tangent line
    ## and will not affect the path extension at all
    numcirclesintersected=numcirclesintersected+1;
    halfangle=acos(disttoline/radius(k));
    chordlength=2*radius(k)*sin(halfangle);
    arclength=2*halfangle*radius(k);
    pathdifference=arclength-chordlength;
  else
    ## Line does not interesect the circle.
    pathdifference=0;
  endif
  
  totalpathlength=totalpathlength+pathdifference;

endfor

## final output comes now
disp("total number of circles intersected"),disp(numcirclesintersected);
disp("length of line w/o circles factored in"), disp(linelength);
disp("final path length after circles"), disp(totalpathlength);

fileid=fopen("output.dat","wt");
fprintf(fileid,"%f",totalpathlength);
fclose(fileid);

## end program

[mobrien_12]

Thoughts?

[H_TeXMeX_H]

I dunno, it looks complex enough to work. How do you go about compiling it ?

[worker201]

Thoughts?

I'm still trying to figure the math out (and figure out how to download shit that lies about its content in Firefox).  Once that is all over, I should be in a better position to evaluate your program, and perhaps compare it to whatever language mine gets written in (probably perl or C).

[mobrien_12]

TeXMeX:  Octave is a scripting language.   All you have to do is put the contents into a file in the same directory as data.dat and call it "linecircles.m" or "kittens.m" or whatever.  

In that directory you would type "octave" on the bash command line and get the octave command line.  Then you would type "linecircles" or "kittens" or whatever and it would run the .m script.

Worker:  The idea of the math is as follows.  Find the distance between the center of the circle and the line, which according to vector analysis is along another line perpendicular to the first line.  If this is less than the radius of the circle then the line intersects the circle.  We then have a right triangle based on the radius to the intersection point and the distance from the center of the circle to the line.  You can use trig to find the angle, and then the length of the original line which we have to remove from the total path length (the chord) because we walk along the edge of the circle instead (the arclength).

From the angle we get the arc length which we add to the totaldistance.

If you subtract the chordlength from the arclength you get the extra path you take from walking around the circle.  You can just add this to the original line length and it makes the code a little more compact.

The attached figure should show some of this.

I'd really like to see this in a compiled language, but Octave is really really good for prototyping math algorithms.

[verwijderd door de beheerder]

[H_TeXMeX_H]

Hmmm ... just tried it ... seems to work ok.

[pofnlice]

I can see your lips moving, but I can't hear a word you're saying...

[worker201]

Haha, I finally figured out how to download that goddamm thing.  It wasn't nearly as hard as I thought.  Just right click and save as.  I figured that since it was giving me 'attachment.php' that it was some intermediary thing.  But it's the real file.  I don't know why I couldn't get kittens.pdf, but oh well.

Anyway, here's the actual content of the file:

[H_TeXMeX_H]

Well, then here's the output of kittens.m

Code: [Select]

octave kittens.m
GNU Octave, version 2.9.8 (i686-redhat-linux-gnu).
Copyright (C) 2006 John W. Eaton.
This is free software; see the source code for copying conditions.
There is ABSOLUTELY NO WARRANTY; not even for MERCHANTIBILITY or
FITNESS FOR A PARTICULAR PURPOSE.  For details, type `warranty'.

Additional information about Octave is available at http://www.octave.org.

Please contribute if you find this software useful.
For more information, visit http://www.octave.org/help-wanted.html

Report bugs to  (but first, please read
http://www.octave.org/bugs.html to learn how to write a helpful report).

total number of circles intersected
 1
length of line w/o circles factored in
 12.728
final path length after circles
 15.999

it was run with the data.dat containing the original example:
1
10
10
1
1
5 5 4

Looks like it might be working ... I'm just too lazy to check the answer

[worker201]

Okay, here's some math that somebody can check for me:

k = slope, u = b-q, r = radius, (p,q) = center of circle
from Quirk's math example:
k^2x^2 + 2kux + u^2 = r^2 -x^2 + 2px - p^2

let j = u^2 - r^2 + p^2, therefore:
k^2x^2 + 2kux + j = -x^2 + 2px
k^2x^2 + x^2 + 2kux -2px + j = 0
x^2(k^2 + 1) + 2x(ku -p) + j = 0

to get it into canonical ax^2 + bx +c form:
let v = k^2 + 1, let w = ku - p, therefore:
vx^2 + 2wx + j = 0

a simple(!) quadratic should finish it from here, giving us values for x in terms of program constants.  If my math is okay.  Anybody want to check it?

[mobrien_12]

It does seem to be working, here is some simplified data that I hand calculated

0
0
10
10
1
5 5 1


total number of circles intersected
 1
length of line w/o circles factored in
 14.142
final path length after circles
 15.284


But I do find one problem.  The formula I used for calculating the distance of the circle center from the line is from vector analysis, and assumes the line is actually next to the circle (essentially infinitly long, but defined by two points, and would work with Quirks original data and his original sketch).   In the following case, the program thinks the circle is intercepted, and adds the extra path length for the circle.

This should be fixable in the If statement... any ideas?

[verwijderd door de beheerder]