Author Topic: A programming challenge all up in your face.  (Read 14438 times)

TheQuirk

  • VIP
  • Member
  • ***
  • Posts: 2,154
  • Kudos: 315
Re: A programming challenge all up in your face.
« Reply #45 on: 27 September 2006, 04:06 »
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.
« Last Edit: 27 September 2006, 04:30 by TheQuirk »

mobrien_12

  • VIP
  • Member
  • ***
  • Posts: 2,138
  • Kudos: 711
    • http://www.geocities.com/mobrien_12
Re: A programming challenge all up in your face.
« Reply #46 on: 28 September 2006, 03:11 »
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]
In brightest day, in darkest night, no evil shall escape my sight....

worker201

  • Global Moderator
  • Member
  • ***
  • Posts: 2,810
  • Kudos: 703
    • http://www.triple-bypass.net
Re: A programming challenge all up in your face.
« Reply #47 on: 28 September 2006, 05:48 »
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).

worker201

  • Global Moderator
  • Member
  • ***
  • Posts: 2,810
  • Kudos: 703
    • http://www.triple-bypass.net
Re: A programming challenge all up in your face.
« Reply #48 on: 28 September 2006, 10:43 »
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.
 
Code: [Select]
#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.

mobrien_12

  • VIP
  • Member
  • ***
  • Posts: 2,138
  • Kudos: 711
    • http://www.geocities.com/mobrien_12
Re: A programming challenge all up in your face.
« Reply #49 on: 28 September 2006, 16:45 »
The problem is the fscanf statements.  

You have this format

fscanf(fid, formatstring, variable)

You need

fscanf(fid, formatstring, &variable)
In brightest day, in darkest night, no evil shall escape my sight....

pofnlice

  • Member
  • **
  • Posts: 999
  • Kudos: 650
Re: A programming challenge all up in your face.
« Reply #50 on: 28 September 2006, 17:18 »
Quote from: "Orethrius"
After all, running Windows without a decent anti-virus is like walking through a Red Light District after eating five metric tonnes of Viagra.

H_TeXMeX_H

  • Member
  • **
  • Posts: 1,988
  • Kudos: 494
    • http://draconishinobi.50webs.com/
Re: A programming challenge all up in your face.
« Reply #51 on: 28 September 2006, 23:16 »
[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 [/offtopic]

pofnlice

  • Member
  • **
  • Posts: 999
  • Kudos: 650
Re: A programming challenge all up in your face.
« Reply #52 on: 28 September 2006, 23:21 »
I gots skillz!





Quote from: "Orethrius"
After all, running Windows without a decent anti-virus is like walking through a Red Light District after eating five metric tonnes of Viagra.

H_TeXMeX_H

  • Member
  • **
  • Posts: 1,988
  • Kudos: 494
    • http://draconishinobi.50webs.com/
Re: A programming challenge all up in your face.
« Reply #53 on: 28 September 2006, 23:27 »



mobrien_12

  • VIP
  • Member
  • ***
  • Posts: 2,138
  • Kudos: 711
    • http://www.geocities.com/mobrien_12
Re: A programming challenge all up in your face.
« Reply #54 on: 29 September 2006, 01:22 »
Quote from: pofnlice

Oh my god, we killed Kenny!
In brightest day, in darkest night, no evil shall escape my sight....

mobrien_12

  • VIP
  • Member
  • ***
  • Posts: 2,138
  • Kudos: 711
    • http://www.geocities.com/mobrien_12
Re: A programming challenge all up in your face.
« Reply #55 on: 29 September 2006, 01:47 »
Quote from: H_TeXMeX_H
[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]
In brightest day, in darkest night, no evil shall escape my sight....

H_TeXMeX_H

  • Member
  • **
  • Posts: 1,988
  • Kudos: 494
    • http://draconishinobi.50webs.com/
Re: A programming challenge all up in your face.
« Reply #56 on: 29 September 2006, 02:28 »
[offtopic]Oh yeah Cygwin ... I forgot about that.[/offtopic]

worker201

  • Global Moderator
  • Member
  • ***
  • Posts: 2,810
  • Kudos: 703
    • http://www.triple-bypass.net
Re: A programming challenge all up in your face.
« Reply #57 on: 29 September 2006, 23:49 »
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.

H_TeXMeX_H

  • Member
  • **
  • Posts: 1,988
  • Kudos: 494
    • http://draconishinobi.50webs.com/
Re: A programming challenge all up in your face.
« Reply #58 on: 30 September 2006, 00:38 »
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)

worker201

  • Global Moderator
  • Member
  • ***
  • Posts: 2,810
  • Kudos: 703
    • http://www.triple-bypass.net
Re: A programming challenge all up in your face.
« Reply #59 on: 30 September 2006, 01:09 »
Quote from: H_TeXMeX_H
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.