Как я могу эффективно генерировать случайное значение X и Y ВНУТРИ многоугольника в С++?

Итак, я создаю программное обеспечение для виртуального картографирования, которое, по сути, разбивает координаты на области. Область состоит из определенного списка граничных координат (координат, которые образуют внешний край области, которые соединяются друг с другом).

С помощью этого программного обеспечения мне нужно случайным образом выбирать точки в КАЖДОЙ области, которые находятся ВНУТРИ координат границы областей. Каждая область отличается от другой и может иметь намного больше или даже меньше сторон, но минимум с 3 сторонами и без максимума сторон.

В настоящее время у меня есть решение, в котором я просто генерирую случайные числа, пока числа не окажутся в пределах области. Однако из-за количества Областей (имеющих совершенно разные координаты Границ в диапазоне от малых до ОГРОМНЫХ значений) и количества точек (может быть от 1 до 100+) эта тактика оказывается крайне неэффективной (требуется много времени, чтобы завершить работу). . Я хотел бы услышать идеи людей или даже опыт/работу над тем, как оптимизировать это, чтобы оно не было таким вялым.

Я создал небольшое демонстрационное приложение, чтобы лучше объяснить ситуацию...

#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;
}

Пример вывода будет выводить набор координат внутри области... В этом конкретном примере мой первый запуск выводит:

Random Coordinate: (-1, 1)

Я читал, что разделение области на треугольники, затем выбор случайного треугольника и создание случайной координаты внутри этого треугольника - лучшее решение... Но я понятия не имею, как генерировать треугольники из набора координат области, и если бы я мог это сделать... Почему бы мне просто не использовать эту технику, чтобы выбрать случайную координату...?

--------Редактировать--------

Благодаря Мэтту Тиммермансу я смог решить эту проблему путем дальнейшего изучения предмета и применения большей части того, что Мэтт объяснил ниже.

Если у кого-то еще есть трудности с этой темой, вот что я придумал (в основном то, что упомянул Мэтт, с некоторыми изменениями)

1) Триангулировать многоугольник на несколько треугольников, в моем случае мне нужно было простое и легкое решение на C++ с нулевым графическим интерфейсом. Мне удалось найти в Интернете рабочий класс под названием Triangulate здесь http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml.

2) Случайным образом выбрать треугольник, используя взвешенную вероятность. Если треугольник занимает 80% исходного многоугольника, его следует выбирать примерно в 80% случаев.

На этом этапе процесса я смог провести небольшое исследование и найти несколько вариантов, самый простой из которых — тот, который я выбрал (как показано ниже).

3) После того, как вы выбрали треугольник, сгенерируйте равномерно случайную точку внутри этого треугольника. Этого можно добиться, используя следующую формулу:

P = (1 - sqrt(r1)) * A + (sqrt(r1) * (1 - r2)) * B + (sqrt(r1) * r2) * C

Где r1 и r2 — случайные числа от 0 до 1, как описано в разделе 4.2 этой статьи... http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Вы закончили, это все, что нужно!

В качестве альтернативы вы можете продолжить то, что предложил Мэтт, оба метода в любом случае работают отлично. Что...

3) Скопируйте треугольник и создайте параллелограмм с ним и исходным треугольником. Используя следующие формулы:

M=(A+C)/2
P4=M-(B-M)

Where...
M is a midpoint in the original triangle where the copied triangle will connect.
A,B,C are the 3 vertices in the original triangle
P4 is the new point the forms the parallelogram with the other 3 points of the original triangle.

4) Сгенерируйте случайное число внутри параллелограмма, генерируя случайное значение x и y между минимальным и максимальным значениями x и y параллелограмма, пока вы не окажетесь внутри параллелограмма. 5) Если случайная координата находится ВНУТРИ КОПИИРОВАННОГО треугольника, сопоставьте ее с соответствующей точкой в ​​исходном треугольнике, если это не так.