By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,626 Members | 2,202 Online
Bytes IT Community
+ Ask a Question
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
Share this Question
Share on Google+
4 Replies


P: n/a
In article <IF*********************@news20.bellglobal.com>,
Marc Dansereau <bo*******@hotmail.com> 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;

--
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 <stdio.h>
#include <stdlib.h>
#include <time.h>

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 <bo*******@hotmail.com> 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
<ro****@pc18.math.umbc.edu> wrote:
In article <IF*********************@news20.bellglobal.com>,
Marc Dansereau <bo*******@hotmail.com> 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;


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.