8

I have a list of longitudes and latitudes which forms boundary for a geographical area. I would like to generate some random co-ordinates inside this geographical area . Could you suggest some approaches I can take in any language?

Kara
  • 6,115
  • 16
  • 50
  • 57
van
  • 633
  • 14
  • 26
  • Similar, but for plane: http://stackoverflow.com/questions/19481514/how-to-get-a-random-point-on-the-interior-of-an-irregular-polygon – Lior Kogan Jan 18 '14 at 14:43

3 Answers3

8

Like any problem, there are many ways to solve it, the first thing came into my mind is

  1. Let's call this "geographic area" a polygon.
  2. Find the bounding box of the polygon (easy, just find maxX maxY minX minY).
  3. Generate random coordinate inside the bounding box x=rand()%(maxX-minX)+minX (and same for Y)
  4. Test that the coordinate is inside the polygon, there are many solutions to this problem and they are implemented in any given language so you don't have to implement it by yourself. Here is an implementation in C/C++ (it is easy to change it to any other language) : Point in Polygon Algorithm

http://en.wikipedia.org/wiki/Point_in_polygon

Edit : As Jan Dvorak suggested, it might be problematic to use it technique on huge areas, i believe that if your polygon is close to the equator and his size is less the 100km, it will work just fine.

Also you will run into problems if you are near the 180° line because right next to it is the -180°.

Community
  • 1
  • 1
OopsUser
  • 4,642
  • 7
  • 46
  • 71
1

First, We'll model the earth's shape as a sphere. Solving the problem for oblate spheroid is much harder.

Generating a random point on a sphere is relatively easy.

Generating a random point on a spherical triangle is harder, but explained in this linked article.

You'll need to divide your polygon into spherical triangles and weight them according to their area. Then randomly select a spherical triangle based on the weights.

For the general case, triangulating a spherical polygon is not possible, however, for most practical cases triangulation is a simple task. One such algorithm is described here (algorithm 1, page 901) with C++ source code available here (search for "Computational methods for calculating geometric parameters of tectonic plates").

Lior Kogan
  • 19,919
  • 6
  • 53
  • 85
  • The geographical area was not very big. So, I did not follow this approach. But the links were very useful and suitable for bigger geographical area. – van Jan 18 '14 at 22:23
0

You can try this:

  1. Compute all co-ordinates within this geographical area, see save in vector<Point> points.

  2. Generate a random int number within [0, points.size()), see k.

  3. points[k] is what you want.

herohuyongtao
  • 49,413
  • 29
  • 133
  • 174