443,626 Members | 2,202 Online
Need help? Post your question and get tips & solutions from a community of 443,626 IT Pros & Developers. It's quick & easy.

# generate random points on a line

 P: n/a Hi all, I wonder what is the most efficient way to generate random point on a line defined by 2 double points (x0,y0) and (x1,y1). Here is the pseudocode of my method : for each point { dx=x1-x0 dy=y1-y1 if dx != 0 { m=dy/dx b = y0-m*x0 x = (rand()%(int)dx)+x0 y = m* x + b printf("(%f, %f) is a random point on the line", x, y); } else { x = x0 y = (rand() %(int)dy)+y0 } } There is probably a problem with the rounding of dy and dx ... There is probably a better way to do this, but I can't figure which ? Thank you Nov 14 '05 #1
4 Replies

 P: n/a In article , Marc Dansereau wrote:I wonder what is the most efficient way to generate random point on a linedefined by 2 double points (x0,y0) and (x1,y1). Generate a random number t in the interval [0,1]. Then let: x = (1-t)*x0 + t*x1; y = (1-t)*y0 + t*y1; -- Rouben Rostamian Nov 14 '05 #2

 P: n/a Marc Dansereau wrote: Hi all, I wonder what is the most efficient way to generate random point on a line defined by 2 double points (x0,y0) and (x1,y1). Here is the pseudocode of my method : for each point { dx=x1-x0 dy=y1-y1 if dx != 0 { m=dy/dx b = y0-m*x0 x = (rand()%(int)dx)+x0 y = m* x + b printf("(%f, %f) is a random point on the line", x, y); } else { x = x0 y = (rand() %(int)dy)+y0 } } There is probably a problem with the rounding of dy and dx ... There is probably a better way to do this, but I can't figure which ? #include #include #include typedef struct { double x, y; } pt; pt randompt(pt a, pt b) { pt c; c.x = a.x + (b.x - a.x) * rand() / (1. + RAND_MAX); c.y = a.y + (c.x - a.x) * (a.y - b.y) / (a.x - b.x); return c; } int main(void) { pt p1 = { 1, 1 }, p2 = { 2, 3 }, p3; int i; const int npts = 10; srand((unsigned) time(0)); printf("Here are %d randomly chosen points on the line\n" "from (%g,%g) to (%g,%g)\n", npts, p1.x, p1.y, p2.x, p2.y); for (i = 0; i < npts; i++) { p3 = randompt(p1, p2); printf("%2d: (%g,%g)\n", i + 1, p3.x, p3.y); } return 0; } Here are 10 randomly chosen points on the line from (1,1) to (2,3) 1: (1.38438,1.76876) 2: (1.46981,1.93962) 3: (1.96502,2.93003) 4: (1.68285,2.3657) 5: (1.91771,2.83543) 6: (1.77233,2.54467) 7: (1.88148,2.76296) 8: (1.26106,1.52211) 9: (1.77445,2.5489) 10: (1.43061,1.86122) Nov 14 '05 #3

 P: n/a Rouben Rostamian wrote: Marc Dansereau wrote: I wonder what is the most efficient way to generate random point on a line defined by 2 double points (x0,y0) and (x1,y1). Generate a random number t in the interval [0,1]. Then let: x = (1-t)*x0 + t*x1; y = (1-t)*y0 + t*y1; Which, off hand, I think is the same as converting to polar based on (x0,y0) and adjusting the magnitude of the polar coordinates of (x1,y1). At any rate this is off-topic for c.l.c and is better suited for comp.programming. Cross-posted and f'ups set. -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson Nov 14 '05 #4

 P: n/a On Fri, 29 Apr 2005 02:17:47 +0000 (UTC), Rouben Rostamian wrote: In article , Marc Dansereau wrote:I wonder what is the most efficient way to generate random point on a linedefined by 2 double points (x0,y0) and (x1,y1). Generate a random number t in the interval [0,1]. Then let: x = (1-t)*x0 + t*x1; y = (1-t)*y0 + t*y1; I would write it as: x = x0 + t * (x1 - x0); y = y0 + t * (y1 - y0); which only does one multiply per expression. It also reflects the way I think about lines (translate the start of the line to be the origin, scale and then translate back). Incidentally, using the interval [0,1] assumes that the endpoints of the line are inclusive. This may be a problem, since a lot of random number generators are in the (usually more useful) range [0,1) which would exclude the end of the line (I've fallen into that trap before). I've had to resort to using two generator functions: double randf(void) { return rand() / (double)(RAND_MAX + 1); } double randfinc(void) { return rand() / (double)RAND_MAX; } Similarly for (0,1) and (0,1] if needed (I've needed the former but not the latter). (Actually I use a more consistent but non-Standard RNG instead of rand(), see other threads about RNGs...) Chris C Nov 14 '05 #5

### This discussion thread is closed

Replies have been disabled for this discussion.