c++ - 为什么要在 C++ 中的三角形之外生成点？

Question

所以我读过这个公式在三角形内生成一个均匀的随机点，从这篇文章... http://www.cs.princeton.edu/~funk/tog02.pdf

        P = (1 - sqrt(R1)) * A + (sqrt(R1) * (1 - R2)) * B + (sqrt(R1) * R2) * C

哪里...R1 和 R2 是介于 0 和 1 之间的随机 float 。

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 循环中，直到生成一个三角形内的值...我只是想知道为什么它在不应该的时候在外面生成，以及在哪里生成错误是...

Answer 1

浮点运算并不完美。这意味着当您使用 float 进行算术运算时，它可能不会给出准确的预期结果。在这种情况下，通常您应该明智地使用较小的数字来更正您的代码。在那种情况下应该更正的部分应该是

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;

这将确保点位于三角形内。