Miscellaneous > Programming & Networking
A programming challenge all up in your face.
worker201:
I didn't understand M_Obrien's geometry, so I used the Law of Cosines. As displayed in the following image:
I can't deal with tangent lines, vertical lines, or datfiles with more than 16 circles. Otherwise, it seems to work fine.
http://www.triple-bypass.net/download/circleline.txt
mobrien_12:
Updated solution to fix the problem mentioned before.
--- Code: ---
## Solution to Quirk's challenge problem Version 2
## Written by M O'Brien. Copyright 2006.
## Licenced to others under GPL.
## Language is GNU Octave (http://www.octave.org)
## 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 distace from the line to the center of circle
## formula is from vector analysis but can be found with web
## search
numerator=abs((x2-x1)*(y1-circy(k)) - \
(x1-circx(k))*(y2-y1) );
disttoline=numerator/linelength;
## define some intermediate variables to make later equations readable
## s1 is distance from line endpoint 1 to center circle
s1=sqrt( (circx(k)-x1)**2 + (circy(k)-y1)**2 );
## s2 is distance from line endpoint 2 to center circle
s2=sqrt( (circx(k)-x2)**2 + (circy(k)-y2)**2 );
## p1 is the projection of s1 along the line (vector component)
p1=sqrt( s1**2 - disttoline**2 );
## p2 is the projection of s2 along the line (vector component)
p2=sqrt( s2**2 - disttoline**2 );
## these are boolean, true or false
## check to see if a line endpoint is inside the circle
EndInCircle= ( ( s1 < radius(k) ) | ( s2 < radius(k) ) );
LineInRange= (disttoline < radius(k));
LineLongEnough = ( ( p1 < linelength ) & ( p2 < linelength ) );
if ( (!EndInCircle) & (LineInRange) & (LineLongEnough) )
## 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
--- End code ---
Tested with the following data.
--- Code: ---
0
0
10
10
2
5 5 1
20 20 2
--- End code ---
With the following results
--- Quote ---
total number of circles intersected
1
length of line w/o circles factored in
14.142
final path length after circles
15.284
--- End quote ---
Actual answer is 15.28372827
Final answer is rounded off to 3 decimal places so the answer is fully correct.
mobrien_12:
Worker, I tried to compile your code but get errors.... it says sqrt and acos is undefined.
I just did gcc circleline.c, and I do have math.h on my system. Do I need a special library?
EDIT: nevermind... forgot about the -lm to link to the math library....
mobrien_12:
Output from Worker's program.
--- Quote ---
15.282185
--- End quote ---
Actual answer is 15.28372827
Looks good!
worker201:
I noticed that too. At what stage do our calculation differences come from?
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version