Search code examples
c#geometrycomputational-geometry

How to find a random point in a quadrangle?

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.

Solution

  • 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).