a tricky program

Discussion in 'C++' started by sadam, Apr 21, 2011.

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0
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

Last edited by a moderator: Apr 22, 2011
2. xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
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).

shabbir likes this.

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0
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

4. xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
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.

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0
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.

Last edited by a moderator: Apr 23, 2011

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0

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);
}```

Last edited by a moderator: Apr 23, 2011
7. xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
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.

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0
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.

9. xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
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?

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0
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?

11. xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
What are the supposedly wrong messages? why won't you answer my questions directly?
I'm the expert and you're the beginner, remember, so maybe I have a clue what I'm asking...just a thought...

Fact is you have way more than three problems. Your syntax is all over the place.
You need to follow my first suggestion. Write a SMALL amount of code to start. Then
get that code working BEFORE you try to go onto anything new. I'm not going to reply again until you
show evidence of having done that because I'm bored with repeating myself, and you would solve this
problem a whole lot quicker if you listened to me. I know it feels like a retrograde step to throw all
this wonderful code away and start over, but it's not really.

Anyway while I'm here. I'll see what Visual Studio 2010 will do with the code. Get a syntax-highlighting
editor by the way, it will make your life a LOT easier, and ALWAYS ALWAYS ALWAYS strictly indent code.

points_to_line() has too many braces
closest_point() doesn't have enough

By the way always define a return type. The default is int. Return int if that's what you want, otherwise
return void, then it's clear what your intention is.

points_to_line() first argument is wrong. The correct syntax is TYPE<space>VARIABLE.
You have TYPE<dot>VARIABLE.

In distance(), p and q are defined as struct point *, i.e. pointer to struct point, but you're
trying to use local semantics (p.x instead of p->x).

In point_and_slope_to_line(), p is defined as struct point and you're trying to use array semantics
to access x and y, i.e. p[x] instead of p.x. Also I've no idea what p_c[X] is meant to mean. Do you
mean p_c.x? Don't forget C and C++ are case sensitive.

In closest_point, p_c is defined as point, not point*. Remember the difference between pass by copy and pass
by reference. This is pass by copy, so if your aim here is to modify the caller's p_c, you need to change
the definition to point* (and use pointer semantics to access the attributes, e.g. p_c->x.

In distance(), remember that TYPE FUNCTION_NAME(ARGS)<SEMI-COLON> is a function PROTOTYPE, not a function definition.
So
Code:
```double distance(struct point *p, struct point *q);
{
```
is wrong.

Maybe closest_point is missing a brace because you haven't finished writing it yet. It handles vertical and horizontal lines,

distance() uses automatic semantics not pointer semantics for accessing point's x and y members, i.e. point.x instead of point->y.

Code:
```points_to_line(s,t,&l);
```
Great use of meaningless variable names. Take a leaf out of the IOCCC's book and rename all your variables to combinations of
underscores, letters O and digits 0.
Code:
```points_to_line(_OO,_O0,&_0O);
```
is considerably more unreadable than this feeble attempt.

ncircles is undefined.

c.c is undefined.

point_in_box is undefined.

SO. Abandon this lot, there are so many errors and things wrong with it that rescuing it is going to be harder work than my
approach. For the very last time, as a starting point you should 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

Then consider putting the data into data structures. Use consistent naming, and use proper names not one letter characters. You're not programming
a 1K ZX81 you know, where 1-character variable names were pretty much essential. Then start adding BIT BY BIT, no more than 5-10 lines at a time,
new functionality. Use lots of printfs so the program displays everything it is doing and why, and you'll be able to debug it from the output.
Eventually when it's all written you can start removing the printfs so that it displays the required output only.

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0

Can you do the program for me please? or at least some functions?

13. xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
Sure thing. My consultancy rates are UKP150/hour, minimum one 8-hour day, payable in advance.

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0
Ok, well let's take the whole program from the beggining. So far it's ok?

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 );
}
```
Are there any other functions that i should include in my program or it's fine?

Last edited by a moderator: Apr 30, 2011
15. xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
Well, does it work? You don't need me to look over the code before you can determine that. Compile it, if that works, run it and see what output you get. Is it what you expect? If so then it's probably fine.

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0
well are there any other function i should include in my program or it's fine?'
thank you

17. xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
What output do you get if you run the program?
What output do you expect to get?

Joined:
Apr 21, 2011
Messages:
33
0
Trophy Points:
0
i don't get anything yet, i expect to get the distance. so there should be another function called distance?

19. xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
You seem to be using this forum as a substitute for doing your own thinking. Analyse the following answer:

No, you don't need a function called distance. The computer will be able to guess what you want if you just put
Code:
```cout << distance;
```