Stop Microsoft
Miscellaneous => Programming & Networking => Topic started by: TheQuirk on 29 January 2006, 21:08
-
Ladies and gentlemen, it's time for another programming challenge. This one deals with circles and lines, so some math will be required.
A picture is worth a thousand words, so I'll start with an illustration I drew.
(http://img368.imageshack.us/img368/126/line2gu.jpg)
Your mission: Find the length of the bold curve.
Input: Your program should read a file called "INPUT," which is in the following format:
x_i
y_i
x_f
y_f
n
x_1 y_1 r_1
x_2 y_2 r_2
...
x_n y_n r_n
Example:
1
10
10
1
1
5 5 4
(x_i denotes the x-coordinate of the BEGINNING of the curve; y_i denotes of y-coordinate of the BEGINNING of the curve; x_f denotes the x-coordinate of the END of the curve; y_f denotes the y-coordinate of the END of the curve; n denotes the number of circles there are; x_j denotes the x-coordinate of the center of circle j; y_j denotes the y-coordinate of the center of circle j; r_j denotes the radius of circle j.)
None of the circles touch or intersect, and all the figures belong to the first quadrant/the two axes.
Output: your program should output the length of the curve to a file called "OUTPUT."
The following math things may prove useful.
The equation of a line with slope a and y-intercept b is y = ax + b.
The slope can be found by taking two points which belong to the line, (x_1, y_1) and (x_2, y_2), and performing the following operation:
y_2 - y_1
a = ---------
x_2 - x_1
The distance between two points with coordiantes (x_1, y_1) and (x_2, y_2) equals sqrt((x_2 - x_1)^2 + (y_2 - y_1)^2)
The standard equation of a circle of radius r with center at (x_0, y_o) is::
(x - x_0)^2 + (y - y_0)^2 = r^2
Note that any positive number has TWO square roots. E.g. sqrt(4) = {-2, 2}, not just 2.
A quadratic equation is an equation in the form ax^2 + bx + c = 0. The solution is this:
-b - sqrt(b^2 - 4ac)
x_1 = --------------------
2a
-b + sqrt(b^2 - 4ac)
x_2 = --------------------
2a
Note that if b^2 - 4ac > 0, then there are two solutions; if b^2 - 4ac = 0, there is one solution; if b^2 - 4ac < 0, then there are no real solutions. (The expression b^2 - 4ac is called the discriminate, and is usually represented by the capital letter D.)
When making algebraic manipulations, don't forget about the domain! For example, suppose you have to solve the following equation:
(sqrt(x))^2 = -15
The answer is "no solution"--NOT -15. The square root function has the domain [0, +inf)!
The formula for the length of an arc is:
s = Ar
Where A is the measure of the angle in radians, and r is the radius of the circle.
In addition, I suggest looking up the Law of Cosines (or, alternatively, Pythagorean
-
[offtopic]
(sqrt(x))^2 = -15
The answer is "no solution"--NOT -15. The square root function has the domain (0, +inf)!
Not intending to be a nit or anything, but isn't (√x)^2 == x, where x ≥ 0? Sorry for the tangent, I'm just trying to see if I correctly remember my Calculus classes.
[/offtopic]
-
[OFFTOPIC]The square root of anything squared is the absolute value of that something ... meaning a positive number[/OFFTOPIC]
-
[offtopic]
Not intending to be a nit or anything, but isn't (√x)^2 == x, where x ≥ 0? Sorry for the tangent, I'm just trying to see if I correctly remember my Calculus classes.
[/offtopic]
If you use complex numbers it works, if you algebraically cancel the two operations out it works. If you attempt the find the Real root your screwed.
-
Will the circles ever overlap the end points of the line?
-
If you use complex numbers it works, if you algebraically cancel the two operations out it works. If you attempt the find the Real root your screwed.
You have already lost.
The correct answer is always "42."
Having said that, 42. QED. :D
-
http://illhostit.com/files/3913162470455711/curve_q.png
Whenever the curve is going around a circle it can go around it clockwise or anti-clockwise, does it always go clockwise or should it go for the shortest route?
-
Shortest route, and no, the circles don't overlap.
About the (sqrt(x))^2 = x thing: for x >= 0, yes, (sqrt(x))^2 = x is correct. What a lot of people do, though, is forget that the square root function has a domain of [0; inf) and solve things like (sqrt(x))^2 = -1 in the real number system.
-
Let's take this thing apart piece piece!
Before we write any code, we have to answer a few questions:
a) How do we represent the line mathematically?
b) How do we represent the circles mathematically?
c) How do we check whether the line touches/intersects a given circle?
d) If the line intersects a given circle, what is the arc length which is "created"?
-
a)
slope = (y2-y1)/(x2-x1);
b = y1 - (slope * x1);
the line's equation is then:
y = b + (slope * x);
or maybe:
y = y1-m(x+x1);
or if you prefer:
y = y1 - (((y2-y1)/(x2-x1)) * (x+x1));
Even though the order of operations covers most of the math, I still use parentheses, for clarity.
So is that enough? Or do we need to build some kind of array of points that satisfy the equation?
-
Should be enough.
-
Should be enough.
You're sooooooo helpful.
Okay,
(b)
how about:
y = q + sqrt(r^2 - (x-p)^2);
where p,q is the center, and r is the radius
-
Well, what else was I supposed to say? You don't need an array because there are infinitely many possibilities of locations and radii of circles, so you can't just have an array with all the, say, points with integer coordinates and check whether they belong to the circles or not.
Anyway!
y = q + sqrt(r^2 - (x-p)^2);
Almost. That only gives you half a circle. This is what it should be:
y = q +- sqrt(r^2 - (x-p)^2);
-
c) set the two y= equations above equal and solve? But what variable do we solve for? There are 7 unknowns, and that's for only one circle.
-
What are the other six unknowns?
-
<-- Wonders what possible use / real world application this rather complicated programming challange has ... I dunno, maybe it doesn't have a purpose other than to be challanging. Hmmm ... maybe I can come up with one that is a little more appilcable.
-
Aside from the arc-length bit, it seems to be a rather straightforward CAD application of some sort.
-
What are the other six unknowns?
whoa, step back a second. I guess the only thing to solve for is x. x in terms of 7 variables. Probably need to solve it twice, to account for the +/- thing.
My shitty math skills produced:
x = (b + p - q -r)/(1-m);
and
x = (-b -p + q + r)/(1-m);
but that probably isn't right
I suppose that if this equation has a rational answer, then the line does in fact intersect the circle, isn't that what we're getting at here?
As far as the point, one possible use for something like this is as a control mechanism for vector graphics. You might have a matrix that defines a line and a matrix that defines a circle, and want to know where, if at all, they intersect.
-
uh oh...2 matrices?
-
Aside from the arc-length bit, it seems to be a rather straightforward CAD application of some sort.
CAD programs can/should be able to tell you the length of arcs, lines etc.
So you could modify/build a simple CAD program to do this. I was thinking of doing it with SVG and Javascript, but, nah..
-
<-- Wonders what possible use / real world application this rather complicated programming challange has ... I dunno, maybe it doesn't have a purpose other than to be challanging. Hmmm ... maybe I can come up with one that is a little more appilcable.
The point of computer science isn't writing applicable programs. If you open a CS book, you'll find that a lot of what's discussed has very little, if any, application to the real world.
http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP
A lot of math has no application. Should we stop studying math?
Something I should mention: Before we solve the general question, which has n circles, let's solve a specific case, in which the line intersects one circle, and doesn't intersect a second circle.
Anyway, that solution for x doesn't seem right. I haven't looked at what all the variables mean, but generally, if you're solving a quadratic, you should be using the quadratic formula (which involes a square and a square root). I wrote down part of the solution on a sheet of paper, but as it turns out, the scanner I was going to use isn't working, so I'll have to scan it some time later today (or type it all up in LaTeX).
-
The point of computer science isn't writing applicable programs. If you open a CS book, you'll find that a lot of what's discussed has very little, if any, application to the real world.
Programming books, however, are all about the applications. And those are far more common than CS books. In fact, I don't think the local Barnes&Noble actually has any true CS books.
-
Well, I agree with all that. Except math does have a lot of applications, and the parts that are not applicable are probably incorrect. As for this particular challange, I brought up this issue because I found it to be way too specific (any other arrangement of the objects in the figure would result in a useless program) and I mean I just think that it's just too damn challanging and too little motivation :(
-
But, if Quirk and I manage to get through it, we'll be better programmers.
(actually, he has probably already written it, so it's just me getting better)
-
Well, I agree with all that. Except math does have a lot of applications, and the parts that are not applicable are probably incorrect. As for this particular challange, I brought up this issue because I found it to be way too specific (any other arrangement of the objects in the figure would result in a useless program) and I mean I just think that it's just too damn challanging and too little motivation :(
I think you misunderstood the challenge. You are given a random number of circles with random coordinates. The progam's task is to read and parse the data, and then calculate the length of the path.
Anyway, back to the challenge. I wasn't able to get to a scanner today, so I'll just type everything up real quick in LaTeX. Stay tuned.
-
There. I'll add more stuff to it as we progress. This is actually a dvi file, not a pdf, so change the extension once you download it (the pdf was too large to upload).
[verwijderd door de beheerder]
-
Whoah ... so it's like making a mini CAD program ?!? Damn ... well I give up
-
Whoah ... so it's like making a mini CAD program ?!? Damn ... well I give up
To an extent. But building a mini CAD program would make this challenge pretty simple, and building a mini CAD program would have plenty of uses.
-
Uh, how do I download this file? Clicking the link causes the browser to handle it as a PDF (which it cannot do). Trying to save the link target fails as well, because it tries to save attachment.php. I'm using Firefox, and have had the same problem in Linux and Windows.
-
I can save it, I just don't know what program can view it ...
-
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.
-
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
-
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)
-
kdvi works too.
-
## 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
-
Thoughts?
-
I dunno, it looks complex enough to work. How do you go about compiling it ?
-
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).
-
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]
-
Hmmm ... just tried it ... seems to work ok.
-
I can see your lips moving, but I can't hear a word you're saying...
-
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:
(http://www.triple-bypass.net/download/mathstuff.jpg)
-
Well, then here's the output of kittens.m
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
-
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?
-
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]
-
I foolighly left my laptop's power adapter in Houston, so I haven't been able to visit the forum much. Anyway, mobrien_12's solution seems spot on (though granted, I don't think he needs my seal of approval :)).
Edit: Saw last message. I don't think you'll be able to do anything without having to revert back to using coordinates.
-
OK, I figured out how to handle the problem.
Calculate the distance between the endpoint of the line and the center of the circle ("s" in the attached diagram). We already know the distance from the circle center to the line (or it's infinite extension) ("d" in the diagram). We find the projection of "s" along the line ("p" in the diagram) using simple trig (we have a right triangle). If the projection is longer than the line, the circle center is not next to the line and we discard it. If, as shown in the figure, the projection is shorter than the line, then the circle is actually next to the line and there is no problem.
But in thinking up this solution I realized that the original challenge was missing one specification. What to do if the line goes into the circle but does not come out?
In other words, what if an endpoint is located within one of the circles?
I say we should ignore the circle in that particular case because we don't have both the beginning and end points are defined on it to tell us the path to take when walking around the edge.
[verwijderd door de beheerder]
-
I was thinking about this earlier. I was going to include a simple test in my version. Once I know the 2 points where the line intersects the circle, I will test the x values with relation to the x values on my line. Given that a straight line has a 1 to 1 relationship between the domain and the range. For example, let's say my line runs from (5,2) to (25,8). If one of the x values of the intersection points is > 25 or < 5, then we know that the line segment of interest enters the circle but does not leave it (even though the infinitely extended line does). At that point, I agree, the circle should be discarded.
Currently, my biggest challenge is figuring out how to separate the input. Your Octave program uses a loop inside the filestream to assign the data to the variables. I just have to figure out how to do that in C (my C-skills are kinda weak).
-
Meh, having some trouble with the beginning of the program. All I have so far is the code to read the data, and then print it, to verify it is working. But it doesn't work.
#include
#include
main()
{
const float pi=3.14159;
FILE *fRead;
char filename[20];
float x1, y1;
float x2, y2;
int i, numcirc;
float circlex[15], circley[15], radius[15];
fRead = fopen("file1.dat", "r");
if (fRead==NULL) {
printf("File unavailable\n");
return 1;
}
fscanf(fRead, "%f", x1);
fscanf(fRead, "%f", y1);
fscanf(fRead, "%f", x2);
fscanf(fRead, "%f", y2);
fscanf(fRead, "%d", numcirc);
if (numcirc>15) {
printf("too many circles, aborting\n");
return 1;
}
for(i=0; i fscanf(fRead, "%f%f%f", circlex[i], circley[i], radius[i]);
}
fclose(fRead);
printf("x1 is %f\n", x1);
printf("y1 is %f\n", y1);
printf("x2 is %f\n", x2);
printf("y2 is %f\n", y2);
printf("numcirc is %d\n", numcirc);
printf("circles:\n");
for(i=0; i printf("%f %f %f", circlex[i], circley[i], radius[i]);
}
printf("That's all the data I got/n");
return 0;
}If the file doesn't exist, it prints "file unavailable" and exits, like I expected. But if the file does exist, all I get is "Bus error". Compiling and running on a Mac. Any ideas? I've never used file pointers or file streams before, so that's probably where the problem is.
Also, is there a way to get around setting the size of my arrays? I would rather just have radius[] be open, so I could process any number of circles. But declaring them without a size gives a syntax error.
-
The problem is the fscanf statements.
You have this format
fscanf(fid, formatstring, variable)
You need
fscanf(fid, formatstring, &variable)
-
(http://www.forumspile.com/Emoticons/Explode.gif)
-
[offtopic] Yeah, that's why I don't like to use C++ for non-important programs that you wanna make work fast. It usually takes a decent amount of debugging to get working, and it's just things so obscure that you don't notice them EVEN WHILE STARING AT THEM !!! Usually the best thing is to get someone else to check your code, like I did often in my computer science class. I usually use bash, cuz it's convenient, and I don't care about portability to Window$ ... all unix based OSs such as Linux, Solaris, BSD have a bourne compatible shell ... easy
P.S. That's a really cool smiley (http://www.forumspile.com/Emoticons/Explode.gif)[/offtopic]
-
I gots skillz!(http://www.forumspile.com/Emoticons/Ninja-Invisible.gif)
(http://www.forumspile.com/Emoticons/Poke.gif)
(http://www.forumspile.com/Emoticons/Mexican_wave.gif)
(http://www.forumspile.com/Emoticons/Emoticons-Thread_recap.gif)
-
(http://www.forumspile.com/Emoticons/Shoot-from_left.gif)(http://www.forumspile.com/Emoticons/Mexican_wave.gif)(http://www.forumspile.com/Emoticons/Shoot-from_right.gif)
(http://www.forumspile.com/Emoticons/Shoot-Right_wins.gif)
-
(http://www.forumspile.com/Emoticons/Explode.gif)
Oh my god, we killed Kenny!
-
[offtopic] Yeah, that's why I don't like to use C++ for non-important programs that you wanna make work fast. It usually takes a decent amount of debugging to get working, and it's just things so obscure that you don't notice them EVEN WHILE STARING AT THEM !!![/offtopic]
[offtopic]
One of the reasons I like Octave for prototyping is that it is easy to work with, that and it's just really really powerful for math. It has a lot of support for math that other languages just dont.
I've done huge code prototypes on Octave that would have probably taken twice the time or maybe been impossible with my skills to prototype directly on C.
But you can't beat compiled code for overall performance. When I was in grad school, there was this guy who was running lots of number crunching for his thesis. He used matlab, but his computations were so heavy that he ended up going to the computer lab and monopolizing 3-4 computers for several hours at a time, over months, just running them all in parallel grinding matlab. If he stopped being lazy, and turned his code into C, he would have been able to crunch the code so much faster and on one machine.
By the way, Bash works very well on WindowsXP through Cygwin. I think I'd be going freaking insane without it.
[/offtopic]
-
[offtopic]Oh yeah Cygwin ... I forgot about that.[/offtopic]
-
Okay, so I have a version that appears to be working. Quick question, though: we know that if the discriminant of the quadratic equation is less than zero, the line and the circle don't intersect. If it is greater than zero, then the line and circle do intersect, at the solution points. What happens if the discriminant equals zero? That means there is one solution, or rather, 2 identical solutions. Doesn't this mean that the line is vertical?
Furthermore, how should we deal with vertical lines? If the x-coordinates are identical, the slope will be undefined. I guess I have to include a couple more if statements.
-
if the descriminant is 0 then there is one root meaning that the line is tangent to the circle (it touches the circle at a single point ... rare indeed)
-
if the descriminant is 0 then there is one root meaning that the line is tangent to the circle (it touches the circle at a single point ... rare indeed)
How could you tell? I think you would get the same solution for a tangent or for a vertical line.
Anyway, my program cannot handle vertical lines yet. Or tangents.
-
Hmmm ... yeah, this is too damn hard.
-
Why am I unable to post my code?
Not Acceptable
An appropriate representation of the requested resource /forums/editpost.php could not be found on this server.
-
There's some stupid bug in the system if you have a couple of characters one right after the other the whole post gets borked. I can't remember the sequence... we had a thread on it last year, but it never got fixed.
Try posting chunks of it with edit to find out what is crashing the system. That's what I had to do last time one of my posts triggered this bug.
Alternatatively you could compress and upload it as a tgz or bz2 file.
Please do it, I want to see the code :)
-
Wow, this thread has taken off.
Re: vertical lines, since we have this:
[(y2 - y1)/(x2 - x1)]x + k = y
We could multiply both sides by (x2 - x1) and see what that gets us (there won't be division by 0).
Re: Matlab, I was always under the impression that Matlab could actually do lots of computations faster than compiled C.
-
Why am I unable to post my code?
The keyword you can't post is:
f open
So why can I post it ? Because there are two spaces between f and open instead of one :)
-
The keyword you can't post is:
f open
So why can I post it ? Because there are two spaces between f and open instead of one :)
But I could post fopen??
f opan
f op
f ope
f opep
g open
but f with a space followed by open barfs the system.
WTF kind of bug is this?
-
mobrien: put a space between the f and open. Using two spaces works, ala: f open
Not Acceptable
An appropriate representation of the requested resource /forums/editpost.php could not be found on this server.
That is a classy error message if ever I saw one.
-
OK this bug needs to be a sticky somewhere.
-
Re: Matlab, I was always under the impression that Matlab could actually do lots of computations faster than compiled C.
Certain matrix calculations yes, because it has optimized compiled libraries that take care of them. It has superior support or complex numbers as well.
In general, however, for very large codebases, it's slow as a basset hound on a hot summer day after eating a steak. It is a scripting language.
You need to be a pretty experienced Matlab or Octave coder to be able to take advantage of the vector/matrix nature of the languages properly, and that will help, but if you want to speed up the calculations you need to either recode in C or Fortran 9x or take the slowest parts of the code base and turn those into C. You can link compiled C code into Matlab or Octave, and that speeds things up a hell of a lot, but that requires you to not be a lazy bastard.
There is a Matlab compiler now... not sure how its performance compares to C.
-
just testing.
testing
-
I didn't understand M_Obrien's geometry, so I used the Law of Cosines. As displayed in the following image:
(http://www.triple-bypass.net/download/lawcosines.png)
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
-
Updated solution to fix the problem mentioned before.
## 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
Tested with the following data.
0
0
10
10
2
5 5 1
20 20 2
With the following results
total number of circles intersected
1
length of line w/o circles factored in
14.142
final path length after circles
15.284
Actual answer is 15.28372827
Final answer is rounded off to 3 decimal places so the answer is fully correct.
-
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....
-
Output from Worker's program.
15.282185
Actual answer is 15.28372827
Looks good!
-
I noticed that too. At what stage do our calculation differences come from?
-
Well you used float for all your numbers (not recommended), might wanna use double for better precision.
-
If I understood this math, I would probably get the challenge.
-
Could be. acos, sqrt, and pow all return doubles, so the program is probably running some internal float>>double conversions in a few places.
-
Yeah, something like that ... I always use double for any non-integer.
-
It would be interesting to see if it gets more decimal places correct using double precision.
As it is, there's only 0.1% error.
-
Wow, this thread has taken off.
Re: vertical lines, since we have this:
[(y2 - y1)/(x2 - x1)]x + k = y
We could multiply both sides by (x2 - x1) and see what that gets us (there won't be division by 0).
Been thinking about this. You could do this but for a vertical line you are multiplying both sides by zero then, which gets you down to the fundamental problem: a vertical line segment is not a function of x. The entire coordinate-type algorithm is based around y being a function of x so it falls apart at this case.
The vector-analysis algorithm that I used doesn't need y to be a function of x.
This doesn't mean that the coordinate-type algorithm can't do it.
Just test to see if it is a vertical line. If so, then simply rotate the coordinate system by 90 degrees and you have a horizontal line. Then the algorithm will work.
-
Would it be ghetto to write a whole other routine just for dealing with verticals? It's a much easier task. Say our vertical line was x=5. You could just plug that into the circle equation and solve for y. If you get 2 different real y values, then the circle intersects the line, and you can continue from there. It would probably be more elegant to write the routine in a way that didn't depend on the slope of the line (or distinct functions of variables), but I think for something as simple and specific as this, maybe a case solution might be better.
WWAD?
(what would Adobe do?)
:P
-
Would it be ghetto to write a whole other routine just for dealing with verticals? It's a much easier task. Say our vertical line was x=5. You could just plug that into the circle equation and solve for y. If you get 2 different real y values, then the circle intersects the line, and you can continue from there. It would probably be more elegant to write the routine in a way that didn't depend on the slope of the line (or distinct functions of variables), but I think for something as simple and specific as this, maybe a case solution might be better.
WWAD?
(what would Adobe do?)
:P
Eh, simplest solution is the best I guess. I was just trying to think of how to make the existing code work for the one special case... I thought that would be the easiest. If a second routine to handle it would be easier, it's probably better to go that way...
-
Been thinking about this. You could do this but for a vertical line you are multiplying both sides by zero then, which gets you down to the fundamental problem: a vertical line segment is not a function of x. The entire coordinate-type algorithm is based around y being a function of x so it falls apart at this case.
The vector-analysis algorithm that I used doesn't need y to be a function of x.
This doesn't mean that the coordinate-type algorithm can't do it.
Just test to see if it is a vertical line. If so, then simply rotate the coordinate system by 90 degrees and you have a horizontal line. Then the algorithm will work.
Aye, the point is that you would get (y2-y1) + k(x2-x1) = y(x2-x1) => y2-y1 = 0 which is obviously false, thus pointing out that it's a vertical line. This is how we generally solved problems which involved coordinates.
(For what it's worth, however, I think your method is a lot nicer.)
-
But I really like the idea that we have two completely different solutions which give the same answers!!! And the code base is about the same length for each!
And you notice how that the challenge was put down a few months ago, but when we all worked together we knocked it out in a week or so? This has really been FUN!
I was able to fix the special cases in my approach that messed it up, maybe this weekend we can fix the vertical line case in the coordinates! :)
-
Just started my new job, so I haven't had much spare time to mess with this yet. But I have a plan to deal with vertical lines and tangents that I think will be cool. I also want to recast everything as doubles, just to see what the change is.
-
#include
#include
#include
#define TRUE 1
#define FALSE 0
int main()
{
/* variable declarations */
/* file read/write variables */
typedef int bool;
bool transpose;
/* temporary "shuffle" variable used to transpose coordinates */
float tempcoord;
/* variables declared from input */
float x1, y1, x2, y2;
int i, numcirc;
float circlex[15], circley[15], radius[15];
/* variables for internal use */
float slope, yint, rsquare, discrim, theta;
float aterm, bterm, cterm;
float u, j, v, w, high, low;
float total, chord, arc;
float intx1[15], intx2[15], inty1[15], inty2[15];
-
Modified worker's program to take care of vertical lines... the tangent's still need to be done. Don't think I can do that...
It works :)
Tested with this data
5
0
5
10
2
5 5 1
20 20 2
CAN'T POST THE CODE..... CAN'T FIGURE OUT WHAT'S MAKING IT BARF.... there's no f open in there.
GAH
I left some troubleshooting printf statements in there.... sorry it's getting late. I also commented out the scanfs becasue I didn't want to type in the file names while troubleshooting... easy enought to uncomment them.
[verwijderd door de beheerder]
-
Wow
-
What an exciting Friday night, programming in C. :cool:
Here's my latest version:
http://www.triple-bypass.net/download/circleline2.txt
It deals with vertical lines and tangents, and even has a function!
Too bad it doesn't work.
For some reason, my logically flawless method of catching tangents doesn't seem to work. Here's the data I tested with:
0
5
10
5
1
5 6 1
Overall, the whole program doesn't work. It ends up writing "nan" to the output file. Which makes me think that there is something really screwy going on. Notice that all the floats are now doubles - could that be to blame? Or maybe it's the function not returning properly. Honestly, the thing I find most difficult about programming, by far, is understanding variable scope. It seems like it would be so much easier to just have the function use the same variables the program does. Any suggestions?
-
I wrote a bunch of thing, but after I looked at the previous posts, it turned out that I didn't need to write them! So, useless post. Looking at code now.
-
Any suggestions?
The logic seems good... the only problem seems to be that in the shuffle you somehow broke the discriminant calculations. Actually, I broke them too when I was making the changes I posted above, and it took a while to figure it out then, so I know it's really easy to break them when shuffling ... In my case I lost the slope= line and everything went to hell :)
It's probably something really simple to fix.
I put the troubleshooting frprintf statements that I was using earlier into this latest version and you can see the difference for the basic test case
0
0
10
10
2
5 5 1
20 20 2
terms a, b c discrim 1.000000 -0.000000 0.000000 0.000000
circle # 1 does not intersect the line
terms a, b c discrim 1.000000 -0.000000 0.000000 0.000000
circle # 2 does not intersect the line
terms a, b c discrim 2.000000 -20.000000 49.000000 8.000000
terms a, b c discrim 2.000000 -80.000000 796.000000 32.000000
circle # 2 does not intersect the line
-
I could probably fix it, by adding the contents of the function back into main. I just figured it was stupid to write the exact same code twice. That's what functions are for, right? I think the program as it stands right now looks terrible, and requires too much maintenance. All those ifs and elses, with the attendant braces and indents, are difficult to keep up with. Then again, it would be even more of a pain in the ass to keep passing array variables back and forth through blackbox functions. What's a boy to do?
I was reading the criticisms of C on wikipedia. Too easy to get something wrong, and too hard to get something right. I think that's somewhat accurate.
-
But, as you wrote it, the function has nothing to do with the discriminant calculation. It calculates path length. The discriminant is used first to decide if the function should be called or not. The discriminant calculation is what is broken.
I'm pretty sure this is a little bug and has nothing to do with your decision to split repeated code off into a function, which I totally agree is what is the issue... nor is it particularly more difficlult in C in this case I think...even Octave is a pain in the ass when you have a hiccup. This is just a little glitch you picked up when shuffling your code around. :)
-
Suggestion: Why not make a function where you pick which variable is independent, and which is dependent? That way you could have something along the lines of the following.
if (x1 == x2) {
happyfunction(y1, y2, x1, x1);
}
else {
happyfunction(x1, x2, y1, y2);
}
-
Suggestion: Why not make a function where you pick which variable is independent, and which is dependent? That way you could have something along the lines of the following.
if (x1 == x2) {
happyfunction(y1, y2, x1, x1);
}
else {
happyfunction(x1, x2, y1, y2);
}
Hmm. That's a good idea for my variation on Worker's code, rather than alter the way the data is loaded into variables...
-
After inserting a bazillion little printf statements at various places, I have found that my program is no longer reading the data from the file properly. All potentially floating point values have been declared as doubles. I suppose for test purposes, they could all be read as integers, but for functionality, I want the input file to possible contain a decimal point.
Using %f statements, like:
fscanf(fRead, "%f%f%f", &circlex, &circley, &radius);
I get:
circlex[0]=0.000000
circley[0]=-0.000000
radius[0]=nan
If I switch them to %g, I get garbage for circlex, negative garbage for circley, and nan for radius.
WTF?
This worked when they were all floats. Does fscanf require double input to have a decimal place? Should I read the data as type float and convert to type double afterwards? This language is pissing me off right now.
-
The problem with converting float to double is some loss in accuracy. If you can't get it to work with doubles then just use float, but know that your answer may be slightly innacurate (not enough to mean too much).
-
Using %f statements, like:
fscanf(fRead, "%f%f%f", &circlex, &circley, &radius);
I get:
circlex[0]=0.000000
circley[0]=-0.000000
radius[0]=nan
Ah.. Found it. Double precisions have a different format code, becasue they are different kinds of variables. I never really used doubles, mostly becasue I never cared about the tiny benefits in accuracy they bring, so I didn't know this before. They take twice as much ram and unless you are on a 64-bit platform you take a computational power hit.
The format code is %lf instead of %f. Interestingly enough, you apply the same "l" (that's an "l" as in "long" not the number one) modifier to integers if you use double length integers.
Try this instead:
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", &numcirc);
printf("x1 %lf y1 %lf x2 %lf y2 %lf numcirc %i\n",x1,y1,x2,y2,numcirc);
if (numcirc>15) {
printf("too many circles, aborting\n");
return 1;
}
for(i=0; i fscanf(fRead, "%lf%lf%lf", &circlex[i], &circley[i], &radius[i]);
printf("circledata x %lf y %lf r %lf \n",circlex[i],circley[i],radius[i]);
}
fclose(fRead);
-
The program still returns NAN... tracked it down to the function. One small error.. the includes must be in front of the function too, it's not much different than writing them in separate files.
/* BEGIN THE CALCARC FUNCTION */
#include
#include
double calcarc(double update,double rad,double chord,int a)
{
/* variable declarations */
double theta;
double rsquare;
double arc;
printf( "In startof calcarc, current total is %lf\n", update);
rsquare = pow(rad, 2);
printf( "rsquare %lf, chordsquare, %lf\n", rsquare, pow(chord,2));
printf( "argument to acos is %lf\n", ( ( (2 * rsquare) - pow(chord, 2) ) / (2 * rsquare) ));
printf( "acos is %lf\n", acos( ( (2 * rsquare) - pow(chord, 2) ) / (2 * rsquare) ));
theta = acos( ( (2 * rsquare) - pow(chord, 2) ) / (2 * rsquare) );
printf( "theta %lf\n", theta);
if (theta == 0)
{
printf("In calcarc, circle # %d does not intersect the line (tangent)\n", a+1);
return update;
}
else
{
printf("In calcarc, circle # %d intersects the line, calculating arc distance\n", a+1);
arc = theta * rad;
update = update - chord + arc;
printf( "In endof calcarc, current total is %lf\n", update);
return update;
}
}
The problem is that acos is not defined for some reason.. it's returning NAN instead of 2pi. I can't figure out why right now.. gotta go to bed.
-
Out of 3 C books, including K&R, the %lf was mentioned only once. All other data pointed to %f or %e or %g being just fine for both floats and doubles.
Declaring the includes before the functions makes no sense whatsoever. I'm going to have to look that up. Especially since I have plans to make the distance calculations into functions.
-
Well, adding includes to the functions did nothing, as I sort of expected - that would not have made any sense, and there is no precedent for it anywhere on the net I could find.
However, after some serious searching, I did figure out why acos is returning nan. Consider the following bit of my calcarc function:
blah = (2 * rsquare - pow(chord, 2)) / (2 * rsquare);
printf("value of blah is %.25g\n", blah);
theta = acos(blah);
printf("value of theta is %g\n", theta);
This is the computation for the law of cosines, done in 2 steps to monitor what is being sent to acos. We all know (at least those of us who have read hundreds of web pages about math.h) that the acos function only accepts values -1 < x < 1. If you calculate it out by hand, you will find that the test data yields a value for blah of -1, totally legal. But then notice the output, and especially notice the 25 decimal places of precision:
value of blah is -1.000000000000001776356839
value of theta is nanBastard! Yes, ladies and gentlemen, we have a floating point math error! This value, which is so close to -1 it's not even funny, will cause acos to return nan. Read all about floating point math, and why it occasionally introduces such inaccuracies here:
http://en.wikipedia.org/wiki/Floating-point_number (http://en.wikipedia.org/wiki/Floating-point_number)
This type of error is also one of the reasons why my test for tangency might not work - you would have to get an extremely accurate return from acos to pass the test for x == 0.
Well, the most obvious solution is to switch the whole damn thing back to floats. The result of the above would probably be -1.000000, with the insignificant bytes at the end rounded off. Since acos accepts and returns a double, the acceptable float would be transformed into an acceptable double before running the function, and then the output would be transformed back into an acceptable float afterwards.
The lesson: increasing your accuracy can come back to bite you in the ass. I'm sticking with floats, unless someone asks me to do otherwise.
-
The %lf fixed the input problems for you too, right? I'm wondering if gcc went more strict on the formatting conventions in later versions.... maybe if we had used full warnings we would have caught it earlier.
I did notice that %f worked fine for the format strings for doubles in printf statements... output not input.
Well, adding includes to the functions did nothing, as I sort of expected - that would not have made any sense, and there is no precedent for it anywhere on the net I could find.
My C books had it, and the printf statements in the functions didn't work on my comp at all w/o them declared a second time. Dunno.
However, after some serious searching, I did figure out why acos is returning nan.
value of blah is -1.000000000000001776356839
value of theta is nan
Bastard! Yes, ladies and gentlemen, we have a floating point math error! This value, which is so close to -1 it's not even funny, will cause acos to return nan.
#$%^. What was the explodey head thing pofnlice used???
-
My C books had it, and the printf statements in the functions didn't work on my comp at all w/o them declared a second time. Dunno.
I think maybe you have linker problems. I'd test it on a Linux machine if I had access to one. I have been writing, compiling, and running this program on a Mac, using vi and gcc, and things work fine. Of my 3 C books, none of them mentioned multiple #includes for one file...
FYI, the %lf thing did work, thanks for that.
-
OK, no need to go back to single precision... was thinking about this... if we know that a floating point error can exist, we just have to sanity check the range and make sure that the acos won't mess up. Nothing wrong with sanity checks if you have a good physical reason to do them, and we do (there is no way a chord can be more than twice as long as two radii).
/* BEGIN THE CALCARC FUNCTION */
#include
#include
double calcarc(double update,double rad,double chord,int a)
{
/* variable declarations */
double theta;
double rsquare;
double arc;
double argument;
printf( "In startof calcarc, current total is %lf\n", update);
rsquare = pow(rad, 2);
printf( "rsquare %lf, chordsquare, %lf\n", rsquare, pow(chord,2));
argument=( ( (2 * rsquare) - pow(chord, 2) ) / (2 * rsquare) );
/* we know some floating point error can creep in and cause the range of the argument
to creep slightly above 1 when using double precision, thus we must sanity check
argument and make sure this doesn't happen or the trig functions choke */
if ( ( (fabs(argument)) > (1.0) ) && ( (floor(fabs(argument))) == (1) ) )
{
/* the next line will turn argument into +1 or -1, if appropriate. */
argument=argument/fabs(argument);
}
printf( "argument to acos is %lf\n", argument );
printf( "acos is %lf\n", acos(argument) );
theta = acos( argument );
if (theta == 0)
{
printf("In calcarc, circle # %d does not intersect the line (tangent)\n", a+1);
return update;
}
else
{
printf("In calcarc, circle # %d intersects the line, calculating arc distance\n", a+1);
arc = theta * rad;
update = update - chord + arc;
printf( "In endof calcarc, current total is %lf\n", update);
return update;
}
}
Result now :)
0
0
10
10
2
5 5 1
20 20 2
Original line length = 14.142136
Final path Length= 15.283728
Actual answer is 15.28372827
Thus perfect... but should be tested with an off axis case.
-
Much better, good job.
-
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?
-
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?
-
Hahahaha, rockstar = me.
Okay, here's the latest fully operational version of the circleline program:
http://www.triple-bypass.net/download/circleline3.txt (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:
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:
0
0
10
10
1
5 5 1powbook:~ lholcombe$ ./a.out
Enter a filename for input:
file1.dat
circle # 1 intersects the line, calculating arc distance
Enter a filename for output:
file1.outfile1.out:
15.2837
2. horizontal line with tangent circle
file2.dat:
0
5
10
5
1
5 6 1powbook:~ lholcombe$ ./a.out
Enter a filename for input:
file2.dat
circle # 1 does not intersect the line (tangent)
Enter a filename for output:
file2.outfile2.out:
10
3. vertical line with intersecting circle
file3.dat:
0
0
0
10
1
0 5 1powbook:~ lholcombe$ ./a.out
Enter a filename for input:
file3.dat
circle # 1 intersects the line, calculating arc distance
Enter a filename for output:
file3.outfile3.out:
11.1416
If anyone has any sensible suggestions for improving this program, please offer them.
-
Aces! Two completely different solutions in two different languages for the same problem with the same answer :)
-
Aces! Two completely different solutions in two different languages for the same problem with the same answer :)
Thats the UNIX way!
-
So where's the next problem to program?
-
So where's the next problem to program?
Make a CAD program, methinks.
-
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?
-
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.
-
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?
-
Penguin, your code seems to be calculating the lines alone and ignoring all the circles.
You could finish it... :)
-
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 :(
-
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 :)
/*
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