二次元の三角形の内外判定で誤差を指定する

2022年8月14日公開
2022年8月14日

二次元の、ある点が三角形の内側にあるか外側にあるかを判定するコードを以前紹介したのだが、点が三角形の境界ぎりぎりにある場合問題を起こすことがある。

判定方法はs,tを計算し、それが0～1に収まっていれば内側と判断するので、この範囲を0.1～0.9などに変更すると誤差を指定することができるようになる。

誤差指定版

//https://suzulang.com/2d-triangle-in-out-check/
template<typename real_t>
inline bool isInTheTriangle(
  real_t px, real_t py,
  real_t p0x, real_t p0y,
  real_t p1x, real_t p1y,
  real_t p2x, real_t p2y
) {
  real_t Area = 0.5 * (-p1y * p2x + p0y * (-p1x + p2x) + p0x * (p1y - p2y) + p1x * p2y);

  real_t s = 1.0 / (2.0 * Area) * (p0y * p2x - p0x * p2y + (p2y - p0y) * px + (p0x - p2x) * py);
  real_t t = 1.0 / (2.0 * Area) * (p0x * p1y - p0y * p1x + (p0y - p1y) * px + (p1x - p0x) * py);


  real_t e = 0.05;
  real_t tmin = 0.0 - e;
  real_t tmax = 1.0 + e;

  if (

    (tmin < s) && (s < tmax) &&
    (tmin < t) && (t < tmax) &&
    (tmin < (1 - s - t)) &&
    ((1 - s - t) < tmax)

    ) {
    return true;
  }
  else {
    return false;
  }
}

呼び出し例

  auto p0 = glm::vec3(-0.913841, 0.999223, 0);
  auto p1 = glm::vec3(0.032665, -0.787554, 0);
  auto p2 = glm::vec3(0.853559, 0.974719, 0);

  glBegin(GL_TRIANGLES);
  glVertex2fv(glm::value_ptr(p0));
  glVertex2fv(glm::value_ptr(p1));
  glVertex2fv(glm::value_ptr(p2));
  glEnd();

  glPointSize(5);
  glBegin(GL_POINTS);
  for (float x = -2.f; x < 2.f; x += 0.1f) {
      for (float y = -2.f; y < 2.f; y += 0.1f) {

    bool hit = isInTheTriangle(
        x, y,
        p0.x, p0.y,
        p1.x, p1.y,
        p2.x, p2.y
    );

    if (hit)
        glColor3d(1, 0, 0);
    else
        glColor3d(0.7, 0.7, 0.7);

    glVertex2f(x,y);


      }
  }
  glEnd();