Generating a random coordinate (x, y) inside of a given polygon/area

Question

I'm creating a virtual mapping software that essentially breaks coordinates into Areas. An Area is comprised of a defined list of boundary coordinates (coordinates that make the outer rim of the area, which connect to one another).

With this software, I need to randomly select points in EACH area that reside INSIDE of the area's boundary coordinates. Each area is different from the other and can have many more or even less sides, but with a minimum of 3 sides and no maximum sides.

I currently have a solution in which I simply generate random numbers until the numbers are within the area. However, due to the quantity of Areas (have vastly different boundary coordinates ranging in small to HUGE values) and the quantity of points (could be 1-100+) this tactic proves to be highly inefficient (takes a long time to finish running). I would like to hear peoples ideas or even experiences/work on how to optimize this so it isn't so sluggish.

I've created a small demo application to explain the situation better:

#include "stdafx.h"
#include <vector>
#include <random>

const int GenerateRandomNumberBetween(
   const int start,
   const int end)
{
   const int stable_end = ((end < start) ? start : end);
   std::random_device rd;
   std::mt19937 generator(rd());
   std::uniform_int_distribution<int> distribution(start, stable_end);

   return distribution(generator); // generates number in the range the distribution value 
}

class Area
{
public:
   Area()
   {
      // Define a primitive area for this example, but please note that this is a very basic area, and most areas are acctually much larger and have many more sides...
      // This sample area creates a triangle.

      //(-2, 2);
      boundaries_x_coordinates.push_back(-2);
      boundaries_y_coordinates.push_back(2);

      //(2, 2);
      boundaries_x_coordinates.push_back(2);
      boundaries_y_coordinates.push_back(2);

      //(-2, 2);
      boundaries_x_coordinates.push_back(-2);
      boundaries_y_coordinates.push_back(-2);
   }

   const bool InArea(
      const int x,
      const int y)
   {
      // This function works just fine, and can be ignored... I just included it to show that we check if the new coordinates are indeed within the given Area.
      int minX = 0;
      int maxX = 0;
      int minY = 0;
      int maxY = 0;
      for (int i = 0; i < boundaries_x_coordinates.size(); i++)
      {
         if (boundaries_x_coordinates[0] < minX)
         {
            minX = boundaries_x_coordinates[0];
         }

         if (boundaries_x_coordinates[0] > maxX)
         {
            maxX = boundaries_x_coordinates[0];
         }

         if (boundaries_y_coordinates[1] < minY)
         {
            minY = boundaries_y_coordinates[1];
         }

         if (boundaries_y_coordinates[1] > maxY)
         {
            maxY = boundaries_y_coordinates[1];
         }
      }

      if (boundaries_x_coordinates.size() < 3)
      {
         return false;
      }
      else if (x < minX || x > maxX || y < minY || y > maxY)
      {
         return false;
      }
      else
      {
         size_t i, j, c = 0;
         for (i = 0, j = boundaries_x_coordinates.size() - 1; i < boundaries_x_coordinates.size(); j = i++)
         {
            if (((boundaries_y_coordinates[i] > y) != (boundaries_y_coordinates[j] > y)) &&
               (x < (boundaries_x_coordinates[j] - boundaries_x_coordinates[i]) * (y - boundaries_y_coordinates[i]) /
               (boundaries_y_coordinates[j] - boundaries_y_coordinates[i]) + boundaries_x_coordinates[i]))
            {
               c = !c;
            }
         }
         return (c == 0) ? false : true;
      }
   }

   std::vector<int> GenerateRandomPointInsideArea()
   {
      int minX = 0, maxX = 0, minY = 0, maxY = 0;

      for (int i = 0; i < boundaries_x_coordinates.size(); i++)
      {
         if (boundaries_x_coordinates[i] < minX)
         {
            minX = boundaries_x_coordinates[i];
         }

         if (boundaries_x_coordinates[i] > maxX)
         {
            maxX = boundaries_x_coordinates[i];
         }

         if (boundaries_y_coordinates[i] < minY)
         {
            minY = boundaries_y_coordinates[i];
         }

         if (boundaries_y_coordinates[i] > maxY)
         {
            maxY = boundaries_y_coordinates[i];
         }
      }

      // The problem is here, this do while statement takes a tremendous of time to execute in realistic Areas simply because it takes a 
      // long time to generate all the random coordinates inside the area (sometimes could be as little as 1 coordinate set, sometimes could be 100).
      int random_x = 0;
      int random_y = 0;
      do
      {
         random_x = GenerateRandomNumberBetween(minX, maxX);
         random_y = GenerateRandomNumberBetween(minY, maxY);
      } while (!InArea(random_x, random_y));

      std::vector<int> random_coordinates;
      random_coordinates.push_back(random_x);
      random_coordinates.push_back(random_y);

      return random_coordinates;
   }

private:
   std::vector<int> boundaries_x_coordinates;
   std::vector<int> boundaries_y_coordinates;
};

int main()
{
   Area* sample_area = new Area();

   std::vector<int> random_coordinates = sample_area->GenerateRandomPointInsideArea();

   printf("Random Coordinate: (%i, %i)\n", random_coordinates[0], random_coordinates[1]);

   // Pause to see results.
   system("pause");
   return 0;
}

The sample output would output a coordinate set inside the Area. In this specific example, my first run outputs:

Random Coordinate: (-1, 1)

I've read that dividing the Area into triangles,then picking a random triangle, and generating a random coordinate within that triangle is the best solution. But I've no idea how to generate triangles out of an Area's coordinate set, and if I could do that. Why wouldn't I just use that technique to choose a random coordinate?

Answer 1

First of all: If I were you, i would create a Point struct instead of having two parallel vectors for x and y coordinates:

struct Point
{
  int X;
  int Y;
}

and then create a vector with Points as items. It's much easier to read and maintain.

Secondly: your function InArea(x, y) calculates the bounding box xmax, ymax, xmin, ymin for every point you check - that is inefficient. Instead I would create a field/proterty (maybe you need to create a struct called Rectangle?) in your Area-class holding that information as it is stable as long as the vertices don't change.

Thirdly: A way to determine if a point lies inside a boundary is the ray-method. To test a point you select another point far away from the boundary and then find the intersections between the line between the two points and each side in the boundary. If there are no or an even number of intersections, the point is outside the boundary and if there are and odd number of intersections, the point is inside the boundary. (see the image below for enlightenment). I won't argue that it is the most efficient method, but it is fairly simple.