#c #geometry
#c #геометрия
Вопрос:
Итак, я прочитал, что эта формула генерирует однородную случайную точку внутри треугольника из этой статьи … http://www.cs.princeton.edu /~фанк/tog02.pdf
P = (1 - sqrt(R1)) * A (sqrt(R1) * (1 - R2)) * B (sqrt(R1) * R2) * C
Где…
R1 и R2 являются случайными числами с плавающей запятой между 0 и 1.
A, B и C — это точки, которые создают наш треугольник.
Я реализовал эту формулу в своем коде со МНОГИМИ условиями тестирования, ожидая, что каждое условие будет иметь точку, сгенерированную в треугольнике… Тем не менее, всегда кажется, что за пределами треугольника есть несколько случаев.
Вот мой код (на C )…
#include "stdafx.h"
#include <random>
#include <time.h>
class Location
{
public:
Location(
int x,
int y)
{
m_x = x;
m_y = y;
}
int m_x;
int m_y;
private:
};
double RandomValueBetweenZeroAndOne()
{
return ((double)rand() / (RAND_MAX));
}
float GetArea(
float x1, float y1,
float x2, float y2,
float x3, float y3)
{
return abs((x1*(y2 - y3) x2*(y3 - y1) x3*(y1 - y2)) / 2.0f);
}
bool InsideTriangle(
float Ax, float Ay,
float Bx, float By,
float Cx, float Cy,
float Px, float Py)
{
/* Calculate area of triangle ABC */
float A = GetArea(Ax, Ay, Bx, By, Cx, Cy);
/* Calculate area of triangle PBC */
float A1 = GetArea(Px, Py, Bx, By, Cx, Cy);
/* Calculate area of triangle PAC */
float A2 = GetArea(Ax, Ay, Px, Py, Cx, Cy);
/* Calculate area of triangle PAB */
float A3 = GetArea(Ax, Ay, Bx, By, Px, Py);
/* Check if sum of A1, A2 and A3 is same as A */
if ((A == (A1 A2 A3)))
{
return true;
}
return false;
};
int main()
{
srand(time(0));
Location* A = new Location(-54900, 933200);
Location* B = new Location(-62800, 934300);
Location* C = new Location(-70000, 932100);
bool in_triangle = true;
int i = 0;
do
{
float R1 = static_cast<float>(RandomValueBetweenZeroAndOne());
float R2 = static_cast<float>(RandomValueBetweenZeroAndOne());
float random_x = (1.0f - sqrt(R1)) * static_cast<float>(A->m_x) (sqrt(R1) * (1.0f - R2)) * static_cast<float>(B->m_x) (sqrt(R1) * R2) * static_cast<float>(C->m_x);
float random_y = (1.0f - sqrt(R1)) * static_cast<float>(A->m_y) (sqrt(R1) * (1.0f - R2)) * static_cast<float>(B->m_y) (sqrt(R1) * R2) * static_cast<float>(C->m_y);
in_triangle = InsideTriangle(
static_cast<float>(A->m_x), static_cast<float>(A->m_y),
static_cast<float>(B->m_x), static_cast<float>(B->m_y),
static_cast<float>(C->m_x), static_cast<float>(C->m_y),
random_x, random_y);
if (!in_triangle)
{
printf("Point located outside of Triangle on %i iteration", i);
}
i ;
} while (in_triangle);
system("pause");
}
В одном примере… Уравнение присвоило случайные координаты следующим образом:
random_x = -66886;
random_y = 932326;
Я даже создал программу на C #, чтобы проверить, действительно ли точка находится за пределами треугольника (визуально). Вот результаты: все, что находится над видимой линией, находится ВНУТРИ треугольника… Все, что находится ниже видимой линии, находится ЗА пределами треугольника…
https://puu.sh/rJtSJ/7a7a88c346.png
Для справки, я знаю, что я могу просто обернуть число, генерируемое в цикле do while, до тех пор, пока не будет сгенерировано значение внутри треугольника… Я просто хотел знать, почему он генерируется снаружи, когда этого не должно быть, и где ошибка…
Комментарии:
1. Для справки, я знаю, что я могу просто обернуть число, генерируемое в цикле do while, до тех пор, пока не будет сгенерировано значение внутри треугольника… Я просто хотел знать, почему он генерируется снаружи, когда этого не должно быть, и где ошибка…
2. О коде в целом:
Location* A = new Location(-54900, 933200);Такие вещи совершенно не нужны и являются дополнительной возможностью для ошибок. Не «пишите C # на C «.3. Я не уверен, что ты имеешь в виду @deviantfan…. Вы имеете в виду тот факт, что я сделал его указателем? Это небольшой фрагмент большого набора работ, причина, по которой он является указателем, заключается в том, что он затем распределяется между несколькими объектами. Поэтому вместо того, чтобы копировать местоположение 5-6 раз, мы создаем указатель на него.
4. Проблемой может быть усечение «интерполяции» до целых чисел.
5. @MartinR Я тоже об этом думал, поэтому я округлил значения random_x и random_y до приведения с использованием ceil, а также полученную область, используя ceil снова перед приведением (чтобы избежать усечения)… Результат был все тот же. Иногда генерируется случайный набор координат, который находится за пределами треугольника, чего, насколько я понимаю, не должно быть.
Ответ №1:
Арифметика с плавающей запятой не идеальна.Это означает, что когда вы выполняете художественную операцию с плавающими точками, она может не дать точного ожидаемого результата.В этом случае, как правило, вам следует корректировать свой код, разумно используя небольшое число. В этом случае часть, которая должна быть исправлена, должна быть
float random_x = (1.0f - sqrt(R1)) * static_cast<float>(A->m_x) (sqrt(R1) * (1.0f - R2)) * static_cast<float>(B->m_x) (sqrt(R1) * R2) * static_cast<float>(C->m_x);
float random_y = (1.0f - sqrt(R1)) * static_cast<float>(A->m_y) (sqrt(R1) * (1.0f - R2)) * static_cast<float>(B->m_y) (sqrt(R1) * R2) * static_cast<float>(C->m_y);
Поскольку я не понял формулу, я не могу ее исправить.Но если бы вы использовали эту формулу:
if(R1 R2>1)
{
R1=1-R1;
R2=1-R2;
}
float random_x = A->m_x (B->m_x-A->m_x)*R1 (C->m_x-A->m_x)*R2;
float random_y = A->m_y (B->m_y-A->m_y)*R1 (C->m_y-A->m_y)*R2;
Вы могли бы исправить это как:
if(R1 R2>1)
{
R1=1-R1;
R2=1-R2;
}
float error=0.01;
float D=1-error;
float random_x = D*A->m_x D*(B->m_x-A->m_x)*R1 D*(C->m_x-A->m_x)*R2 error*(A->m_x B->m_x C->m_x)/3;
float random_y = D*A->m_y D*(B->m_y-A->m_y)*R1 D*(C->m_y-A->m_y)*R2 error*(A->m_x B->m_x C->m_x)/3;
Это гарантирует, что точки будут внутри треугольника.
Ответ №2:
У вас проблема с округлением, это нужно округлить до меньшей точности. Также использование double вместо float даст лучший результат.
Вместо сравнения двух значений double (или float), чтобы увидеть, совпадают ли они, возьмите их разницу и посмотрите, находится ли она в пределах погрешности. Приведенная ниже функция имеет произвольный запас 0.00001
bool InsideTriangle(double Ax, double Ay, double Bx, double By,
double Cx, double Cy, double Px, double Py)
{
double A = GetArea(Ax, Ay, Bx, By, Cx, Cy);
double A1 = GetArea(Px, Py, Bx, By, Cx, Cy);
double A2 = GetArea(Ax, Ay, Px, Py, Cx, Cy);
double A3 = GetArea(Ax, Ay, Bx, By, Px, Py);
double diff = A1 A2 A3 - A;
if (abs(diff) < 0.00001) return true;
std::cout << diff << "n";
return false;
};
Чтобы напрямую сравнить значения, используйте приведенный ниже пример:
double getround(double f)
{
return floor(f * 1000.0f 0.5f) / 1000.0f;
}
bool InsideTriangle(double Ax, double Ay, double Bx, double By,
double Cx, double Cy, double Px, double Py)
{
double A = GetArea(Ax, Ay, Bx, By, Cx, Cy);
double A1 = GetArea(Px, Py, Bx, By, Cx, Cy);
double A2 = GetArea(Ax, Ay, Px, Py, Cx, Cy);
double A3 = GetArea(Ax, Ay, Bx, By, Px, Py);
if ((A == (A1 A2 A3)))
{
return true;
}
double t1 = getround(A1 A2 A3);
double t2 = getround(A);
if (t1 == t2)
return true;
std::cout << t1 << ", " << t2 << "n";
return false;
};
Обратите внимание, что вы не должны использовать приведение, если компилятор не жалуется. Например, следующее приведение не требуется
float foo(){return 0.1f;}
...
float R1 = static_cast<float>(foo());
Потому foo что уже float есть . Если вы автоматически помещаете приведение везде, это может скрыть потенциальные проблемы.
Избегайте использования выделения памяти, когда это не нужно. Например, используйте Location A(-54900, 933200); вместо new оператора. Если вы используете new then, обязательно освободите память, delete когда она больше не понадобится.
Комментарии:
1. Превосходно! Спасибо!
2. Добро пожаловать. См. Обновление для альтернативного сравнения.