3

I've got a problem I'm not too sure how to solve. I have a 2d space with several points in it. I also have a current point, which is one of the points in the space. I want to randomly select one of the other point, with a higher probability for selection being given to points closer to my current point. I'm working in Java. Any tips would be much appreciated.

Graham
  • 1,044
  • 1
  • 8
  • 11
  • What sort of probabilistic bias are you looking for? Does the actual distance matter, or do you only care about ordering by distance? – Dilum Ranatunga May 26 '11 at 20:38
  • Actual distance would matter. I want the random selection to favour points that are closer in an euclidian distance sort of way. – Graham May 26 '11 at 20:40

3 Answers3

4

  1. Assign a "weight" to each point by for instance computing 1 / distanceFromCurrent.

  2. Select a point based on these weights.

Solution for the latter part can for instance be found in some of the following answers:

Another option would be to use java.util.Random.nextGaussian. Adjust the resulting double so that it represents a reasonable radius, and select the neighboring point closest to this radius.

Community
  • 1
  • 1
aioobe
  • 413,195
  • 112
  • 811
  • 826
  • Thanks for the reply. I suppose the actual task of choosing a point from the set of weights could be a whole different issue on its own. – Graham May 26 '11 at 22:03
1

you alraedy have all the elements ^^

what you want is that the further away from the current point the less probability it has therefore you want to use a formula where the distance decreases the probability like:

1/d

d being the distance between your current point and another.

so what you do with that is calculate for each point their probability 1/d and sum up all these probabilities to get you your total or world.

so something like:

total = 0;
for(MyPoint p : list){
   p.probability = 1/(distance(currentpoint,p);
   total += p.probability;
}

and then you need only to do 

Math.random*total;

and compare it to your list of points ^^;

Jason

Jason Rogers
  • 19,194
  • 27
  • 79
  • 112
  • Thanks, this was also really useful. I think this is an instance of the type of solution aioobe talked about, but it helped me understand how I am going to actually implement the solution. – Graham May 26 '11 at 22:04
  • yep aioobe gave you the shorter version but its the same logic ^^ – Jason Rogers May 27 '11 at 17:46
0

You need some probability distribution that is a function of distance, more specifically, you need the CDF or the inverse-CDF of the probability distribution as a java function

/**
 * @param distance
 * @return probability of choosing a point closer than distance
**/
double someCDF( double distance );

One possible choice is the exponential distribution, and the corresponding CDF would be 1-Math.exp( distance * r ) where r is some constant for scaling. Again, there are lots of different functions you could use, but this one is really easy to code up.

Then sort the points by distance, and

double rnum = Math.random();
for( Point point : sortedPoints )
    if( someCDF( distance(thisPoint,point) ) >= rnum )
        return point;

would give you the point you want (technically the first point whose probability to be picked is less than or equal to 1-the uniform random number, which you can prove gives you back the probability distribution of the inverse CDF in the long run.)

trutheality
  • 23,114
  • 6
  • 54
  • 68