如何在 C++ 中有效地生成多边形内部的随机 X 和 Y 值？

Question

所以我正在创建一个虚拟地图软件，它基本上将坐标分解为区域。一个区域由定义的边界坐标列表组成（构成该区域外缘的坐标，它们相互连接）。

使用此软件，我需要在区域边界坐标内部的每个区域中随机 select 点。每个区域都不同，可以有更多或更少的边，但最少有 3 个边，没有最大边。

我目前有一个解决方案，我只是生成随机数，直到数字在该区域内。然而，由于区域的数量（具有从小到大的值范围内的大不相同的边界坐标）和点的数量（可能是 1-100+），这种策略被证明是非常低效的（需要很长时间才能完成运行宁）。我想听听人们的想法，甚至 experiences/work 如何优化它，让它不那么迟钝。

我创建了一个小型演示应用程序来更好地解释情况...

#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)

我读过将区域划分为三角形，然后随机选择一个三角形，并在该三角形内生成一个随机坐标是最好的解决方案...但我不知道如何从区域坐标集，如果我能做到...为什么我不使用该技术来选择随机坐标...？

--------编辑--------

感谢 Matt Timmermans，我能够通过进一步研究该主题并应用 Matt 在下面解释的大部分内容来解决这个问题。

如果其他人对这个主题有困难，这就是我想出的（主要是马特提到的，有一些变化）

1) 将多边形三角化为多个三角形，在我的例子中，我需要一个具有 0 个图形界面的简单轻量级 C++ 解决方案。我设法在此处 http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml.

找到了一个名为 Triangulate 的在线 class

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.cs.princeton.edu/~funk/tog02.pdf

大功告成，仅此而已！

或者，您可以继续 Matt 的建议，这两种方法似乎在任何情况下都可以完美地工作。这就是...

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) 如果随机坐标在复制的三角形内部，则将其映射到原始三角形中的相应点，否则你就完成了。

Answer 1

将多边形分成三角形
随机选择一个三角形，给每个三角形一个与其面积成正比的概率
复制三角形做平行四边形
在平行四边形中通过随机选择底面和高度方向的坐标来随机选择一个点
如果随机点在三角形的副本中，而不在原始三角形中，则将其映射到原始三角形中的对应点。
完成 -- 您在所选三角形中剩下一个随机点，它是从多边形中均匀选择的随机点。

如何在 C++ 中有效地生成多边形内部的随机 X 和 Y 值？

How can I efficiently generate a random X and Y value INSIDE of a polygon in C++?

c++

optimization

point-in-polygon