Generating Random Points within a Polygon in Unity
Tags: gamedev, unity3d, math
Published: 2020-01-09 18:26:49

Scenario: you want to define a polygonal area in your scene and pick random locations on it, for example to have a NPC roam within. There's no one-shot solution for this that I'm aware of, but there's at least one method for picking uniform random points within a triangle. Since polygons can be triangulated, we can apply the triangle formula in the context of the polygon.

The code is [here](https://github.com/BogdanAlexandru/UnityTriangleNetExample), but since it's really just about three non-glue scripts with very few functions, I recommend writing your own as you learn the ideas from the article.

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

### The Solution

Given a triangle with vertices `A`, `B` and `C`, you can find a random point `P` within the triangle with the formula:

![P = (1 - sqrt(r_1)) * A + (sqrt(r_1) * (1 - r_2)) * B + (r_2 sqrt(r_1))* C](https://thepracticaldev.s3.amazonaws.com/i/eo1u4kwyf125iqgvcjrp.png)

where `r1` and `r2` are uniformly distributed random numbers in `[0, 1]` i.e. as returned by `UnityEngine.Random.Range(0f, 1f)`.

![Sample illustration of 1000 points in interval 0, 1](https://thepracticaldev.s3.amazonaws.com/i/zmzi60sz6ruy9xglnwpb.png)

<center>*1000 points within `[(0, 0), (0, 1), (1, 0)]`*</center>

We can apply the formula in the context of any polygonal shape if said shape is triangulated. For the triangulation process you can use an existing library that already implements [Delaunay triangulations](https://en.wikipedia.org/wiki/Delaunay_triangulation), such as [Triangle.net](https://archive.codeplex.com/?p=triangle), or write your own (it's not trivial, in case you're not sure you've got the time to spend). 

I gave Triangle.net a shot and it appeared to work just fine for what I threw at it. The official distribution should work fine now that Unity supports .NET 4.6 but to avoid any kind of hassle I used [this fork](https://github.com/BogdanAlexandru/Triangle.NET) which was already confirmed to work with Unity.

Before we start throwing triangles around though, we need a polygon.

## Setting Up the Polygon

An `Area` script can be defined, which will have a `List<Vector3>` of vertices that describe the polygonal shape.

```cs
public class Area : MonoBehaviour
{
    public List<Vector3> Corners;
    //                   or vertices

    // ...
}
```

We want to be able to edit this polygon in the scene view, so a custom editor for the `Area` component needs to be written.

[This tutorial](http://catlikecoding.com/unity/tutorials/curves-and-splines/) that deals with Bezier curves, or at least the first quarter of it, teaches all that you need to get this done, so if you're not sure how to proceed, give it a shot. In short, we're not doing much more than drawing lines between points and using handles to move said points around.

This is the end result for me (note that here the polygon is already being triangulated):

![Animation](https://thepracticaldev.s3.amazonaws.com/i/zaxrwvzn9w2lloxyp3mu.gif)

In the end, you want the `Area` script to expose a `PickRandomLocation` function or similar, allowing calls like:

```cs
class RoamingAI : MonoBehaviour {

    // Map this to the area you need in the inspector
    public Area RoamingArea;

    // later on...
    var location = RoamingArea.PickRandomLocation();

    // ...
```

## Triangulating the Polygon

With a set of vertices that describe the polygon, we can ask Triangle.Net to do some triangulation for us.

This is my function that calls into Triangle.Net:

```cs
public static ICollection<Triangle> Triangulate(IEnumerable<Vector2> points)
{
    var poly = new Polygon();
    poly.Add(new Contour(points.Select(p => p.ToVertex())));
    var mesh = poly.Triangulate();
    return mesh.Triangles;
}
```

The `Vector2`s given as input are the `Vector3` vertices of the `Area`, with the `z` coordinate taking the place of `y`. In other words, `area.Vertices.Select(v => new Vector2(v.x, v.z))`.

`Polygon` is a Triangle.Net type, as are `Contour` and `Vertex`. We turn a `Vector2` into a `Vertex` via an extension method called `ToVertex` that does nothing more than `new Vertex(vec2.x, vec2.y)`. Then, we build a `Contour` out of our vertices and add it to the `Polygon`.

With the `Polygon` set up, all that's left is to call `Triangulate()` on it, which gives us back an `IMesh` object, from which we only need the collection of `Triangle`.

## Picking a Random Triangle

With the collection of triangles calculated, we can pick one to apply the random point formula on. We want the random positions to be picked as uniformly as possible, so simply choosing one of the triangles at random won't do:

![Not ideal distribution](https://thepracticaldev.s3.amazonaws.com/i/s6uuu3gv66i1j9dl44vo.png)

Instead we'll introduce some bias, so larger (by area) triangles become proportionately more likely to be selected.

```cs
// The sum of the areas of the triangles can be cached.
_areaSum = 0f;
_triangles.ForEach(t => _areaSum += t.TriArea());

// ...

private Triangle PickRandomTriangle()
{
    var rng = Random.Range(0f, _areaSum);
    for (int i = 0; i < _triangles.Count; ++i)
    {
        // TriArea() is an extension method
        // that uses the cross product formula
        // to calculate the triangle's area.
        if (rng < _triangles[i].TriArea())
        {
            return _triangles[i];
        }
        rng -= _triangles[i].TriArea();
    }
    // Should normally not get here
    // so this is not 100% correct.
    // You'd need to consider floating
    // point arithmetic imprecision.
    //
    // But this is a good compromise 
    // that nonetheless gives good 
    // results.
    return _triangles.Last();
}
```

![Better distribution](https://thepracticaldev.s3.amazonaws.com/i/ws78uphl27jklmk2ijv1.png)<center>*Much better.*</center>


## Picking a Random Location

With a `Triangle` having been chosen, all that's left is to apply the aforementioned formula:

```cs
private Vector2 RandomWithinTriangle(Triangle t)
{
    var r1 = Mathf.Sqrt(Random.Range(0f, 1f));
    var r2 = Random.Range(0f, 1f);
    var m1 = 1 - r1;
    var m2 = r1 * (1 - r2);
    var m3 = r2 * r1;

    var p1 = t.GetVertex(0).ToVector2();
    var p2 = t.GetVertex(1).ToVector2();
    var p3 = t.GetVertex(2).ToVector2();
    return (m1 * p1) + (m2 * p2) + (m3 * p3);
}
```

The result is our random position within the polygon describing the `Area`.

## Quick Q&A

### How do I use this in a 3D world?
Once you have the random 2D coordinates generated, `(x, z)`, you can perform a raycast from `(x, HighEnoughY, z)` downwards. Once you hit the terrain, get your final position by taking `hitPoint.y` as your random point's `y` coordinate.

Remember to set your terrain on its own layer if it's not on one already, and make your raycast only hit the terrain layer via the layer mask argument. This will improve performance and reduce the chance that your character receives the top of a giant orc's head as destination.

### How do I add holes within the polygon?
Aside from the area vertices, you will need another set of vertices for each hole. Once you have that, instead of adding just the area vertices to the `Polygon` that's to be triangulated, also add a `Contour` for each hole:

```cs
var p = new Polygon();
p.Add(new Contour(verticesOfArea));
holes.ForEach(h => p.Add(new Contour(h.Vertices)));
var mesh = p.Triangulate();
```

![sample screenshot](https://thepracticaldev.s3.amazonaws.com/i/uz3smnatorrhzr9mo7v1.png)

For the editor part, you may want to separate the `Area` component into an `AreaPolygon` and `Area` pair, with the former only keeping track of the vertices that make up the polygon, and the latter taking in those vertices, triangulating the polygon and returning a random position. Add empty GameObjects as children to the `Area` GameObjects, and give them `AreaPolygon` components. The `Area` component will gather all the Hole `AreaPolygon` data from its children and consider each one as a hole inside its own polygon.