Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a static rectangle and dynamic polygon. I need to generate a random 2D point in that rectangle, but not in a polygon. This is what I mean:

enter image description here

Green is where random point can be generated and red is where it can't be generated. I'm not really familiar in this thing, so I ask for an algorithm. It also must be fast and efficient, because it's going to be on mobile platform and might be generated few times a second. I could check if point is in polygon, but how do I move it away from polygon to make it still "feel random"? Thanks.

P.S. polygon will always have 4 vertices.

share|improve this question
add comment

2 Answers

up vote 10 down vote accepted

The simplest solution is to generate a random point within the rectangle and reject it if it lies in the polygon. You would repeat the process until you got a valid point. This same algorithm is used to uniformly distribute points over an area or volume, except points that are considered outliers are rejected. This type of sampling is known as rejection sampling, if you want to research it further.

The way I would do the polygon test is to test the point against the 4 edges individually. Imagine that all the lines extend out to infinity in both directions. Any point on the 2d plane belongs to one of the two partitions created by a single infinite line. For example:

           A

   (0, 2)     (4, 2)
<--.----------.------>

           B

The two points (0, 2) and (4, 2) form the line at y = 2. Point A is considered "above" the line, while point B is considered "below" the line.

Now extend the idea to 4 of these lines. If a point tests in a specific way for all 4 lines, the point has to be in the polygon. This is the same logic used when testing for point containment in an AABB, just simplified where all the lines are parallel to the X or Y axes, making the comparison much simpler.

The way this is calculated on a computer is actually very straightforward, this StackOverflow answer provides a function that takes 3 points - 2 that form a line and one to test.

If you use the same function as on the SO answer, you'll want the left edge of the polygon to return false, the right edge to return true, the top edge to return false, and the bottom edge to return true for the point to be considered contained.

The test requires, in the worst case, 20 subtractions, 8 multiplications, and 4 comparisons. Even on a low-end smartphone, that's nothing. Even having to test several points per frame, it won't make a dent in performance.

The benefit of this kind of sampling over your suggested moving of the point is that any simple algorithm for moving the point will skew your distribution to be more dense around the polygon. Rejection sampling keeps the same distribution, it just cuts out anything that doesn't belong.

share|improve this answer
add comment

I think what you said about checking if its in the polygon then moving it could be fine, the user wont notice anything if say you move the point up or down till its not in the polygon. You could move it by random amounts so it wont always end up on the boundary of your polygon.

You could also try dividing the space around the polygon up and picking one segment randomly, then make your point in that space.

Iv done that before in a simple game but the area I was avoiding was a static square.

share|improve this answer
    
How do I know in what direction should I move that point? Let's say polygon is right in the corner, so there is high chance that I might probably move outside the rectangle –  Gintas_ Jul 6 '13 at 10:49
    
You could check how close it is to each side of the rectangle and move it towards the closest, or you could do what Robert below said and just keep running the code till you get a random point that isn't in the polygon –  richi lonsdale Jul 6 '13 at 10:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.