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

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

С этим программным обеспечением мне нужно случайным образом выбирать точки в КАЖДОЙ области, которые находятся ВНУТРИ координатных границ областей. Каждая область отличается от другой и может иметь много больше или даже меньше сторон, но с минимум 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 ++ с 0 графическими интерфейсами. Мне удалось найти здесь рабочий класс под названием 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.cs.princeton.edu/~funk/tog02.pdf

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

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

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 между значениями min и max x и y параллелограмма, пока вы не окажетесь внутри параллелограмма.
5) Если случайная координата находится внутри треугольника COPIED, сопоставьте ее с соответствующей точкой в ​​исходном треугольнике, если это не так.