How to get a random point on the interior of an irregular polygon? [closed]

by

I would do this in three steps:

  1. Create a list of triangles that cover the same area as the polygon you are given. If your polygon is convex it is easier, since you can have all triangles share a common vertex. If your polygons are not guaranteed to be convex, then you’ll have to find a better polygon triangulation technique. Here’s the relevant Wikipedia article.

  2. Randomly choose which triangle to use, weighted by its area. So if triangle A is 75% of the area and triangle B is 25% of the area, triangle A should be picked 75% of the time and B 25%. This means find the fraction of the total area that each triangle takes up, and store that in a list. Then generate a random double number from 0 – 1 (Math.random() does this), and subtract each value in the list until the next subtraction would make it negative. That will pick a triangle at random with the area weights considered.

  3. Randomly pick a point within the chosen triangle. You can use this formula : sample random point in triangle.

Alternatively, you can pick a rectangle that covers the entire polygon (such as its bounding box) and randomly pick a point within that rectangle. Then check if the point is inside the polygon, and if it isn’t then generate a new random point and try again, repeating as necessary. Theoretically this could take forever, but in practice it should take four or five tries at most.

You still need to have an algorithm to determine if the point is inside the polygon though. If you already have it broken up into triangles this is easier, just check if it’s in any of those.

More Related Contents:

  1. Random shuffling of an array
  2. Creating random numbers with no duplicates
  3. Java random numbers using a seed
  4. Java random always returns the same number when I set the seed?
  5. Java generating non-repeating random numbers
  6. How to generate a random alpha-numeric string
  7. Getting random numbers in Java [duplicate]
  8. Picking a random element from a set
  9. How to generate a random BigInteger value in Java?
  10. How can I generate random number in specific range in Android? [duplicate]
  11. How can I make image appear randomly every x seconds in java using timer?
  12. Generate random date of birth
  13. How to pick an item by its probability?
  14. Java – generate Random range of specific numbers without duplication of those numbers – how to?
  15. Weighted randomness in Java [duplicate]
  16. Why does this code using random strings print “hello world”?
  17. How can I generate a random number within a range but exclude some?
  18. How to generate a random permutation in Java?
  19. Algorithm to generate Poisson and binomial random numbers?
  20. Random number with Probabilities
  21. Port of Random generator from C to Java?
  22. Pick a random value from an enum?
  23. How to generate random positive and negative numbers in Java [duplicate]
  24. Generate Random Numbers in Array [duplicate]
  25. How do I create an int array with randomly shuffled numbers in a given range [duplicate]
  26. Java random number with given length [duplicate]
  27. Why are initial random numbers similar when using similar seeds?
  28. Random element from string array [closed]
  29. SecureRandom with NativePRNG vs SHA1PRNG
  30. Random over ThreadLocalRandom

Leave a Comment