11

I have to be able to set a random location for a waypoint for a flight sim. The maths challenge is straightforward:

"To find a single random location within a quadrangle, where there's an equal chance of the point being at any location."

Visually like this:

alt text

An example ABCD quadrangle is: A:[21417.78 37105.97] B:[38197.32 24009.74] C:[1364.19 2455.54] D:[1227.77 37378.81]

Thanks in advance for any help you can provide. :-)

EDIT Thanks all for your replies. I'll be taking a look at this at the weekend and will award the accepted answer then. BTW I should have mentioned that the quadrangle can be CONVEX OR CONCAVE. Sry 'bout dat.

Community
  • 1
  • 1
MrGreggles
  • 6,113
  • 9
  • 42
  • 48
  • 1
    With three answers posted including my own, all suggesting a brute force "pick then check" approach, I'm wondering if perhaps your question is really how to check if a given point is within a specified quad, which is the part we all punted on. – Paul Richter Jun 17 '10 at 00:54
  • 2
    Is the quadrangle guaranteed to be convex? – Jacob Jun 17 '10 at 00:59
  • Update: That was for another idea. Found an excellent SO solution which can be easily adapted for your problem. – Jacob Jun 17 '10 at 01:05
  • 1
    Also give it a try on MathOverflow http://mathoverflow.net/ – John K Jun 17 '10 at 05:02
  • @jdk: Trivial for MathOverflow – Jacob Jun 17 '10 at 05:07
  • @jdk, no, MathOverflow is for graduate-level (and up) math questions. This is too elementary for MO (which is probably what Jacob meant). – Bart Kiers Jun 17 '10 at 19:33
  • @Bart K: That's only partly true: you stated their primary goal but the FAQs continue past that and say: `Of course, individual questions don't have to be worthy of an article, and they don't have to be about new mathematics. A typical example is, "Can this hypothesis in that theorem be relaxed in this way?"` – John K Jun 17 '10 at 21:50
  • @jdk, you have a point, and I could have expressed my opinion in a more reserved way. Only one way to find out: post the question at MO, but it is my guess it will be closed. – Bart Kiers Jun 18 '10 at 06:42

9 Answers9

10

Split your quadrangle into two triangles and then use this excellent SO answer to quickly find a random point in one of them.

Update:

Borrowing this great link from Akusete on picking a random point in a triangle.

main figure
(from MathWorld - A Wolfram Web Resource: wolfram.com)

Given a triangle with one vertex at the origin and the others at positions v1 and v2, pick x
(from MathWorld - A Wolfram Web Resource: wolfram.com)
where A1 and A2 are uniform variates in the interval [0,1] , which gives points uniformly distributed in a quadrilateral (left figure). The points not in the triangle interior can then either be discarded, or transformed into the corresponding point inside the triangle (right figure).

Community
  • 1
  • 1
Jacob
  • 34,255
  • 14
  • 110
  • 165
  • 1
    But, how will you pick a triangle from the two? They might have different areas, biasing the result. (ok, it isn't that difficult, but your answer is wrong without it) – Kobi Jun 17 '10 at 04:22
  • 2
    @Kobi nice point, but you can choose weighting by triangle area, guaranteeing a fair result – garph0 Jun 17 '10 at 04:29
  • 1
    More generally, you can pick a uniformly distributed random point within *any* polygon by triangulating it, selecting a triangle with probability proportional to its area and then choosing a uniformly random point within the triangle. – Boojum Jun 17 '10 at 04:45
  • I don't understand the downvotes, so I'll toss you an upvote. Your answer is complex, perhaps impractical, but it appears to be both interesting and correct. – Steven Sudit Jun 17 '10 at 16:33
  • Even with concave quads you can still compose it into two triangles and apply this method, so I think this is still the best answer. – Akusete Jun 18 '10 at 00:12
  • 4 downvotes now .. why can't people leave comments? SO should atleast allow anonymous comments for downvotes (let's see what meta has to say). UPDATE: http://meta.stackexchange.com/questions/31302/proposal-require-anonymous-comment-with-downvotes-closed – Jacob Jun 21 '10 at 17:13
5

I believe there are two suitable ways to solve this problem.

The first mentioned by other posters is to find the smallest bounding box that encloses the rectangle, then generate points in that box until you find a point which lies inside the rectangle. 

  Find Bounding box (x,y,width, height)
  Pick Random Point x1,y1 with ranges [x to x+width] and [y to y+height]
  while (x1 or y1 is no inside the quadrangle){
       Select new x1,y1
  }

Assuming your quadrangle area is Q and the bounding box is A, the probability that you would need to generate N pairs of points is 1-(Q/A)^N, which approaches 0 inverse exponentially.

I would reccommend the above approach, espesially in two dimensions. It is very fast to generate the points and test.

If you wanted a gaurentee of termination, then you can create an algorithm to only generate points within the quadrangle (easy) but you must ensure the probablity distribution of the points are even thoughout the quadrangle.

http://mathworld.wolfram.com/TrianglePointPicking.html

Gives a very good explination

Akusete
  • 10,704
  • 7
  • 57
  • 73
4

The "brute force" approach is simply to loop through until you have a valid coordinate. In pseudocode:

left   = min(pa.x, pb.x, pc.x, pd.x)
right  = max(pa.x, pb.x, pc.x, pd.x)
bottom = min(pa.y, pb.y, pc.y, pd.y)
top    = max(pa.y, pb.y, pc.y, pd.y)
do {
    x = left   + fmod(rand, right-left)
    y = bottom + fmod(rand, top-bottom)
} while (!isin(x, y, pa, pb, pc, pd));

You can use a stock function pulled from the net for "isin". I realize that this isn't the fastest-executing thing in the world, but I think it'll work.

Reinderien
  • 11,755
  • 5
  • 49
  • 77
2

So, this time tackling how to figure out if a point is within the quad:

The four edges can be expressed as lines in y = mx + b form. Check if the point is above or below each of the four lines, and taken together you can figure out if it's inside or outside.

Paul Richter
  • 6,154
  • 2
  • 20
  • 22
  • This looks reasonable. If it's *still* too slow, one possible optimization would be to find the rectangle bound *by* the quadrangle and do a quick first-pass test to see if the point is inside it. Four comparisons, very cheap. If it's in, stop. Otherwise, do the test y=mx+b test. This potential optimization may actually be slower, so definitely benchmark it. – Steven Sudit Jun 17 '10 at 17:06
  • Figuring out the rectangle bound by the quadrangle seems like a challenge in itself. – Paul Richter Jun 18 '10 at 15:33
1

Are you allowed to just repeatedly try anywhere within the rectangle which bounds the quadrangle, until you get something within the quad? Might this even be faster than some fancy algorithm to ensure that you pick something within the quad?

Incidentally, in that problem statement, I think the use of the word "find" is confusing. You can't really find a random value that satisfies a condition; the randomizer just gives it to you. What you're trying to do is set parameters on the randomizer to give you values matching certain criteria.

Paul Richter
  • 6,154
  • 2
  • 20
  • 22
1

You may randomly create points in a bound-in-box only stopping after you find one that it's inside your polygon.

So:

  1. Find the box that contains all the points of your polygon.
  2. Create a random point inside the bounds of the previously box found. Use random functions to generate x and y values.
  3. Check if that point is inside the polygon (See how here or here)
  4. If that point is inside the polygon stop, you're done, if not go to step 2
user347594
  • 1,256
  • 7
  • 11
  • Thanks for addressing the part I skipped -- how to detect whether the point is inside -- and for providing a pair of interesting links. – Steven Sudit Jun 17 '10 at 16:40
1

I would divide your quadrangle into multiple figures, where each figure is a regular polygon with one side (or both sides) parallel to one of the axes. For eg, for the figure above, I would first find the maximum rectangle that fits inside the quadrangle, the rectangle has to be parallel to the X/Y axes. Then in the remaining area, I would fit triangles, such triangles will be adjacent to each side of the rectangle.

then it is simple to write a function:

1) get a figure at random. 2) find a random point in the figure.

If the figure chosen in #1 is a rectangle, it should be pretty easy to find a random point in it. The tricky part is to write a routine which can find a random point inside the triangle

feroze
  • 7,380
  • 7
  • 40
  • 57
0

This is an interesting problem and there's probably as really interesting answer, but in case you just want it to work, let me offer you something simple.

Here's the algorithm:

  1. Pick a random point that is within the rectangle that bounds the quadrangle.
  2. If it is not within the quadrangle (or whatever shape), repeat.
  3. Profit!

edit

I updated the first step to mention the bounding box, per Bart K.'s suggestion.

Steven Sudit
  • 19,391
  • 1
  • 51
  • 53
  • Simplicity has its own beauty. Thanks for the reply. – MrGreggles Jun 17 '10 at 05:23
  • 1
    Picking just a random point could take a long time, especially if the points of the quadrangle are very close to each other. You could (statistically) narrow it down by picking a point whose `(x,y)` are at least within the bounding box of the quadrangle. – Bart Kiers Jun 17 '10 at 08:23
  • @Bart: You're right. I should have said that the point should be within a shape that bounds the desired shape but is more regular (in this case, a rectangle). A bit of randomness is good, but there's no point generating numbers that we know in advance will be invalid. I'll edit it now, giving you credit. – Steven Sudit Jun 17 '10 at 16:28
  • 1
    @Steve, note that even when generating a number within the (x- and y-aligned) bounding box, it could still take quite some time before a point is found: take the following quadrangle for example: `(0,1) (0,0) (1,0) (100000000000000000000,100000000000000000000)` or one whose area is far less then that example I posted. Of course, it depends on what type of quadrangles the OP might expect, perhaps your suggestion is perfectly valid and such corner cases I portray here will not occur. – Bart Kiers Jun 17 '10 at 16:56
  • @Bart: You are once again correct. Pathological cases, such as your skinny quadrangle that creates a huge, mostly empty bounding box would definitely lead to poor performance for the sort of algorithm I've endorsed. If OP is dealing with random shapes, then the probability of such an edge case should be small, but if the process that generates them is biased or (even worse) open to outside control, then you would at minimum want to add a limiter to the number of retries. You might also compare the area of the quadrangle to that of the bounding box and, (cont.) – Steven Sudit Jun 17 '10 at 18:08
  • if the ratio is not reasonably close to unity, use another algorithm entirely. I think that triangulation with weighting would be the right way to go. A hybrid algorithm is certainly less elegant, but sometimes performance demands such things. Thanks for your corrective input: I'm here to learn. – Steven Sudit Jun 17 '10 at 18:10
  • @Steven, you're welcome. It's typical for computational geometry problems: you think you have found an elegant, relatively simple solution, which, after closer inspection, appears to have quite some nasty corner cases (at least, that is what happens to me when working on such things). :) – Bart Kiers Jun 17 '10 at 18:47
  • @Bart: I suspect there is a relatively elegant yet efficient alternative that is less than obvious. One thought I had is that, despite this being a geometry problem, it seems that it is defined in terms of a discrete metric. In other words, while the coordinates are presented as what look like FP values, they could instead be viewed as integers in a unit that's 100x more. That would mean that there is a finite number of pixels, correlating to the area of the shape. As such, there must be some way to give each pixel a sequence number... – Steven Sudit Jun 17 '10 at 19:23
0

So, it depends on how you want your distribution.

If you want the points randomly sampled in your 2d view space, then Jacob's answer is great. If you want the points to be sort of like a perspective view (in your example image, more density in top right than bottom left), then you can use bilinear interpolation.

Bilinear interpolation is pretty easy. Generate two random numbers s and t in the range [0..1]. Then if your input points are p0,p1,p2,p3 the bilinear interpolation is:

bilerp(s,t) = t*(s*p3+(1-s)*p2) + (1-t)*(s*p1+(1-s)*p0)

The main difference is whether you want your distribution to be uniform in your 2d space (Jacob's method) or uniform in parameter space.

tfinniga
  • 6,693
  • 3
  • 32
  • 37