Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   a tricky program (http://www.go4expert.com/forums/a-tricky-program-t25589/)

sadam 22Apr2011 03:38

a tricky program
 
I'm having a problem with a program in C and i would appreciate if anyone could helped me.

In this program we have to help a driver reach his destination, from (xs,ys) to (xt,yt). The problem is that his movement across the line L which connects the 2 points is blocked by circles blocks. So when the driver reaches each of this blocks he has to drive to the side of the smallest arc from the two arcs which the line L separates the circle bock, and then continue his movement on line L.

The programm should works as follows :
1) we should read the data from the program route.dat, the first line has the coordinates of the driver, the second line has the coordinates of the destination, the third line has the number of the blocks,nobst (an integer). The next nobst lines have the coordinates of the center of each circle block and its radius. The blocks are maximum 20.
We also suppose that :
i) xs<xt, so the line which connects the start point and the last point is not vertical and the the start point is always at the left of the finish one
ii) the circle blocks are not intersected
iii) the x-coordinate cx of the center of each circle satisfies xs<cx<xt
iv) the line L which connects the start point and the finish point does not necessarily intersects all the circle blocks

2) the output of the program should consists of only one line with the command
printf(”%f\n”, dist); where dist is the distance from the start point and the finish point

3) the math part of this program is about the arc length and the chord length. If d is the distance from the center of a circle block to the line which connects the start point and the finish point then cosu=d/r, so u=cos^-1(d/r). The arc length is given from s=r.u.
Finally a line intersects a circle if the distance of the center of the circle to the line is smaller than the radius of the circle

4) we can use this data for the route.dat:
0.0 10.0
15.0 0.0
4
2.0 7.5 1.75
3.0 3.0 1.0
7.0 5.0 2.0
12.0 1.7 1.5


So far i have done this:

Code:
Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.t>

struct point {
double x;
double y;
};

struct line {
double a; /* Slope */
double b; /* y-intercept */
};

struct circle {
double cx, cy; /* Center coordinates */
double r;        /* Circle radius */
};

void ReadFile( const char *filename, point *x, point *y, int *nobst )
{
    FILE *file;
    int i;
    if (( file = fopen( filename, "r" )) == NULL )
    {
        printf ( "Error opening file!\n" );
        exit(1);
        }
    fscanf( file, "%lf %lf", &point->x, &point->y );
    fscanf( file, "%lf %lf", &point->x, &point->y );
    fscanf( file, "%d", nobst );
    for( i = 0; i <*nobst )
    {
        fscanf( file, "%lf %lf %1f", &circle.cx,&circle.cy,&circle.r)
    }
    fclose( file );
}

/* Distance between two points */
double PointToPoint(sturct point *p, struct point *q);

/* Distance between a point and a line */
double PointToLine(struct point *p, struct line *l);



int main()
{
    Point x;
    Point y;
    int nobst;
    ReadFile( "route.dat", &x, &y, &nobst );
}

Thank you very much

xpi0t0s 22Apr2011 17:11

Re: a tricky program
 
You've not done much yet. This isn't as difficult as it looks; there are several things you need to do, so break it down into tasks and debug as you go along.

Quote:

The programm should works as follows :
Great, so you've been given the outline. That saves a lot of bother and gives you some assumptions you can work with.

Quote:

1) we should read the data from the program route.dat, the first line has the coordinates of the driver,
the second line has the coordinates of the destination, the third line has the number of the blocks,nobst (an integer).
The next nobst lines have the coordinates of the center of each circle block and its radius. The blocks are maximum 20.
OK, so as a starting point you can write a program that reads the file and displays what it has found, with relevant labels. This way you can be sure you've understood the data format.
So the data you've given as an example might result in the following output:
Driver drives from (0.0, 10.0) to (15.0, 0.0)
There are 4 blocks
Block 1 is at (2.0, 7.5) and has radius 1.75
Block 2 is at (3.0, 3.0) and has radius 1.0
Block 3 is at (7.0, 5.0) and has radius 2.0
Block 4 is at (12.0, 1.7) and has radius 1.5

Quote:

We also suppose that :
i) xs<xt, so the line which connects the start point and the last point is not vertical and the the start point is always at the left of the finish one
Great, so we can use "easy" maths like y=mx+c, which is prone to infinities when lines are vertical. It's easier than the kind of maths that doesn't have that problem.
Always worth validating the data before proceeding though, just in case the test data has some wrong data.

Quote:

ii) the circle blocks are not intersected
That will also make the program easier; again it's worth checking, if you want. (You might get extra marks)

Quote:

iii) the x-coordinate cx of the center of each circle satisfies xs<cx<xt
Again, this makes the program easier and could be checked for possible extra credit.

Quote:

iv) the line L which connects the start point and the finish point does not necessarily intersects all the circle blocks
So what you'll need is an algorithm to determine the zero, one or two points where a line L intersects a circle. This should be easy enough to find; just Google it (try "line intersects circle").
If zero then you can ignore that circle.
If 1 then you can also ignore the circle because L is tangential to it and no deviation is necessary.

If 2 then you'll need to work out which is the shorter arc. Do you have any idea how to do that? (Hint: try drawing it out on paper and see if you can see anything that might help you centre on a solution).

sadam 22Apr2011 18:29

Re: a tricky program
 
I'm really confused right now, how will i use the slope of the line L and how to check which of the two arcs is smaller?
can you write me something in C to make it easier to understand?
unfortunately i have been trying for days without any progress and the deadline is nearby :disappoin

xpi0t0s 22Apr2011 22:40

Re: a tricky program
 
Probably you're trying to do too much. Split it down into simple tasks, have a go and see how far you get.

Try what I said. Google for an algorithm - and you might even find code already written - for how to find the two points where a line intersects a circle.

Have a think about how you might determine which of the two arcs is smaller. Draw it out on some paper and see if you can find an approach that will let you centre (<- that word is a REALLY BIG HINT) on a solution.

sadam 23Apr2011 02:03

Re: a tricky program
 
Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXCIRCLES 20

struct point {
double x;
double y;
};

struct line {
double a; /* Slope */
double b; /* y-intercept */
};

struct circle {
double cx, cy; /* Center coordinates */
double r; /* Circle radius */
};

void ReadFile( const char *filename, point *x, point *y, int *nobst )
{
    FILE *file;
    int i;
    if (( file = fopen( filename, "r" )) == NULL )
    {
        printf ( "Error opening file!\n" );
        exit(1);
        }
    fscanf( file, "%lf %lf", &point->x, &point->y );
    fscanf( file, "%lf %lf", &point->x, &point->y );
    fscanf( file, "%d", nobst );
    for( i = 0; i <*nobst )
    {
        fscanf( file, "%lf %lf %1f", &circle.cx,&circle.cy,&circle.r)
    }
    fclose( file );
}

/* Distance between two points */
double PointToPoint(sturct point *p, struct point *q);

/* Distance between a point and a line */
double PointToLine(struct point *p, struct line *l);



int main()
{
    point s;
    point t;
    int nobst;
    circle c[MAXCIRCLES];
    ReadFile( "route.dat", &x, &y, &nobst );

    line l;
    point close;
    double d;
    double xray = 0.0;
    double around = 0.0;
    double angle;
    double travel;
    int i;
    double asin(),sqrt();
    double distance();

    points_to_line(s,t,&l);

    for (i=1; i<=nobst; i++) {
    closes_point(c[i].c,,l,close);
    d = distance(c[i].c,close);
    if ((d>=0) &&  (d<c[i].r) && point_in_box(close,s,t){
        xray += 2*sqrt(c[i].r*c[i].r) - d*d;
        angle = acos(d/c[i].r);
        around += ((2*angle)/(2*PI)) * (2*PI*c[i].r);
        }
    }

    dist = distance(s,t) - xray + around;
    printf("f\n",dist);
    }

Can you correct it for me? it has many errors but i'm tired trying to solve this.

sadam 23Apr2011 05:13

Re: a tricky program
 
Quote:

Originally Posted by xpi0t0s (Post 82185)
You've not done much yet. This isn't as difficult as it looks; there are several things you need to do, so break it down into tasks and debug as you go along.



Great, so you've been given the outline. That saves a lot of bother and gives you some assumptions you can work with.



OK, so as a starting point you can write a program that reads the file and displays what it has found, with relevant labels. This way you can be sure you've understood the data format.
So the data you've given as an example might result in the following output:
Driver drives from (0.0, 10.0) to (15.0, 0.0)
There are 4 blocks
Block 1 is at (2.0, 7.5) and has radius 1.75
Block 2 is at (3.0, 3.0) and has radius 1.0
Block 3 is at (7.0, 5.0) and has radius 2.0
Block 4 is at (12.0, 1.7) and has radius 1.5



Great, so we can use "easy" maths like y=mx+c, which is prone to infinities when lines are vertical. It's easier than the kind of maths that doesn't have that problem.
Always worth validating the data before proceeding though, just in case the test data has some wrong data.



That will also make the program easier; again it's worth checking, if you want. (You might get extra marks)



Again, this makes the program easier and could be checked for possible extra credit.



So what you'll need is an algorithm to determine the zero, one or two points where a line L intersects a circle. This should be easy enough to find; just Google it (try "line intersects circle").
If zero then you can ignore that circle.
If 1 then you can also ignore the circle because L is tangential to it and no deviation is necessary.

If 2 then you'll need to work out which is the shorter arc. Do you have any idea how to do that? (Hint: try drawing it out on paper and see if you can see anything that might help you centre on a solution).



i have done this so far, i think it's done but it says that it has 3 errors, can you correct them so the program should work?

Code :
Code:

#define MAXN 20

typedef struct {
        double cx,cy;;  /* center of circle */
        double r;        /* radius of circle */
        } circle;

struct point {
    double x, y;
        };

typedef struct {
    double a;            /* x-coefficient */
    double b;            /* y-coefficient */
    double c;            /* constant term */
        } line;

points_to_line(point.p1, point p2, line *l)
    {
        if (p1[X] == p2[X]) {
        l->a = 1;
        l->b = 0;
        l->c = -p1[X];
        } else {
        l->b = 1;
        l->a = -(p1[Y]-p2[Y])/(p1[X]-p2[X]);
        l->c = -(l->a * p1[X]) - (l->b * p1[Y]);
    }
}

point_and_slope_to_line(point p, double m, line *l)
{
        l->a = -m;
        l->b = 1;
        l->c = -((l->a*p[x]) + (l->b*p[y]));
}

closest_point(point *p_in, line l, point p_c)
{
line perp; /* perpendicular to l through (x,y) */
if (fabs(l.b) <= EPSILON) { /* vertical line */
p_c[X] = -(l.c);
p_c[Y] = p_in[Y];
return;
}
if (fabs(l.a) <= EPSILON) { /* horizontal line */
p_c[X] = p_in[X];
p_c[Y] = -(l.c);
return;
}


double distance(sturct point *p, struct point *q);
{
    double d=0.0;

    d = (point.x - point.y) * (point.x - point.y);
    return( sqrt(d) );
}

void ReadFile( const char *filename, point *x, point *y, int *nobst )
{
    FILE *file;
    int i;
    if (( file = fopen( filename, "r" )) == NULL )
    {
        printf ( "Error opening file!\n" );
        exit(1);
        }
    fscanf( file, "%lf %lf", &s.x, &s.y );
    fscanf( file, "%lf %lf", &t.x, &t.y );
        for( i = 0; i <*nobst; i++)
    {
        fscanf( file, "%lf %lf %1f", &circle.cx,&circle.cy,&circle.r);
    }
    fclose( file );
}



point s;            /* Superman’s initial position */
point t;            /* target position */
int nobst;      /* number of circles */
circle c[MAXN];    /* circles data structure */


int main()
{
ReadFile( "route.dat", &s, &t, &nobst );
line l;                /* line from start to target position */
point close;            /* closest point */
double d;              /* distance from circle-center */
double xray = 0.0;      /* length of intersection with circles */
double around = 0.0;    /* length around circular arcs */
double angle;          /* angle subtended by arc */
double dist;          /* total travel distance */
int i;
double asin(), sqrt();
double distance();

points_to_line(s,t,&l);

for (i=1; i<=ncircles; i++) {
closest_point(c[i].c,l,close);
d = distance(c[i].c,close);
if ((d>=0) && (d < c[i].r) && point_in_box(close,s,t)) {
xray += 2*sqrt(c[i].r*c[i].r - d*d);
angle = acos(d/c[i].r);
around += ((2*angle)/(2*PI)) * (2*PI*c[i].r);
}
}
dist = distance(s,t) - xray + around;
printf("f\n",dist);
}


xpi0t0s 25Apr2011 21:33

Re: a tricky program
 
Try reformatting the code (I use Notepad++ and TextFX). If you do, you'll see you're trying to write embedded functions: closest_point() seems to "contain" distance, ReadFile and so on.

> double distance(sturct

What's a "sturct"? Seems you've written loads of code and not tested any of it: don't do that, the scope for errors is massive and it's no wonder you haven't got a clue what's happened. Write a few lines of code at a time - no more than 5-10 at your level (and at my level it's really not that much more) before compiling and testing that you get what you think you should get.

Start with what I suggested - read the file and check the output is what you would expect. Then add functionality a bit at a time and you should storm through this exercise, once you've found the algorithms for line intersects circle, nearest point to line etc.

sadam 26Apr2011 01:24

Re: a tricky program
 
Quote:

Originally Posted by xpi0t0s (Post 82318)
Try reformatting the code (I use Notepad++ and TextFX). If you do, you'll see you're trying to write embedded functions: closest_point() seems to "contain" distance, ReadFile and so on.

> double distance(sturct

What's a "sturct"? Seems you've written loads of code and not tested any of it: don't do that, the scope for errors is massive and it's no wonder you haven't got a clue what's happened. Write a few lines of code at a time - no more than 5-10 at your level (and at my level it's really not that much more) before compiling and testing that you get what you think you should get.

Start with what I suggested - read the file and check the output is what you would expect. Then add functionality a bit at a time and you should storm through this exercise, once you've found the algorithms for line intersects circle, nearest point to line etc.

Thanks for your help but that what i have in my mind, although it doesn't work..can you tell me exactly where my wrong is so i would finish this a day?
thank you once again.

xpi0t0s 26Apr2011 06:18

Re: a tricky program
 
What are the first five compiler errors?
Have you tried taking the "plain English" meaning of those errors? For example, if the error is "missing brace", have you tried looking around the given line for such a problem?

sadam 27Apr2011 00:54

Re: a tricky program
 
it writes the same wrong message 3 times, that means that it has 3 errors only or the whole program is wrong??
can you make it run correctly?


All times are GMT +5.5. The time now is 14:12.