c++ - 检查鼠标是否在三角形 C++ 内

Question

我正在申请学校，我必须点击其中的一个特定对象。

编辑:这是二维制作的

我有一个矩形，我将这个矩形旋转 X 轴。矩形的旋转使我的矩形 (x,y,width,height) 成为围绕旋转矩形的新矩形。

http://i.stack.imgur.com/MejMA.png(请原谅我糟糕的绘画技巧)

黑线描述了旋转后的矩形，红线是我的新矩形。我需要确定我的鼠标是否在黑色矩形内。无论我做什么旋转，我已经有了一个函数来获取黑色矩形每个角的 (X,Y)。

现在我正在尝试实现这个 Check if point is within triangle (The same side technique) .

所以我可以检查我的鼠标是否在每个三角形内，或者如果有一种方法可以检查我的鼠标是否在旋转的矩形内，那会更好。

我几乎理解三角形文档中写的所有内容，但我根本没有计算叉积和 2 个叉积的点积的数学技能。

这应该是叉积:

a × b = |a| |b| sin(θ) n

|a| is the magnitude (length) of vector a

|b| is the magnitude (length) of vector b

θ is the angle between a and b

n is the unit vector at right angles to both a and b

但是如何计算 a 和 b 的单位 vector 呢？我如何获得 vector 的大小？

编辑:我忘了要求计算 2 个叉积之间的点积。

function SameSide(p1,p2, a,b)
    cp1 = CrossProduct(b-a, p1-a)
    cp2 = CrossProduct(b-a, p2-a)
    if DotProduct(cp1, cp2) >= 0 then return true
    else return false

---

谢谢大家的帮助我想我现在已经掌握了窍门，我希望我能接受多个答案。

Answer 1

如果您必须执行大量检查，我会避免使用平方根函数:它们的计算成本很高。出于比较目的，只需将所有内容乘以自身即可绕过平方根:

vector 的大小= vector 的长度

如果vector定义为float[3]，长度可以计算如下:

double magnitude = sqrt( a[0]*a[0] + a[1]*a[1] + a[2]*a[2] );

但是这在计算上很昂贵，所以我会使用

double magnitudeSquared = a[0]*a[0] + a[1]*a[1] + a[2]*a[2];

然后修改任何比较计算以使用距离或幅度的平方版本，这样性能会更高。

对于叉积，如果这个数学不稳定，请原谅我，我已经有几年没有为此编写函数了(代码重用很好，但对于内存来说很糟糕):

double c[3];

c[0] = ( a[1]*b[2] - a[2]*b[1] );
c[1] = ( a[2]*b[0] - a[0]*b[2] );
c[2] = ( a[0]*b[1] - a[1]*b[0] );

为了简化这一切，我将把一个 vec3d 放在它自己的一个类中，一个非常简单的表示是:

class vec3d
{
    public:
        float x, y, z;
        vec3d crossProduct(vec3d secondVector)
        {
            vec3d retval;
            retval.x = (this.y * secondVector.z)-(secondVector.y * this.z);
            retval.y = -(this.x * secondVector.z)+(secondVector.x * this.z);
            retval.z = (this.x * secondVector.y)-(this.y * secondVector.x);
            return retval;
        }
        // to get the unit vector divide by a vectors length...
        void normalise() // this will make the vector into a 1 unit long variant of itself, or a unit vector
        {
           if(fabs(x) > 0.0001){
              x= x / this.magnitude();
           }
           if(fabs(y) > 0.0001){
              y= y / this.magnitude();
           }
           if(fabs(z) > 0.0001){
              z = / this.magnitude();
           }
        }

        double magnitude() 
        {
            return sqrt((x*x) + (y*y) + (z*z));
        }
        double magnitudeSquared() 
        {
            return ((x*x) + (y*y) + (z*z));
        }
};

vec3d 类的更完整实现可以从我的第 2 年编码练习之一获得:.h file和 .cpp file .

这里是一个极简的 2d 实现(这是我突然想到的，所以请原谅简洁的代码，如果有错误请告诉我):

vec2d.h

#ifndef VEC2D_H
#define VEC2D_H

#include <iostream>
using namespace std;

class Vec2D {
 private:
  double x, y;
 public:

  Vec2D();                   // default, takes no args
  Vec2D(double, double);     // user can specify init values

  void setX(double);
  void setY(double);

  double getX() const;
  double getY() const;

  double getMagnitude() const;
  double getMagnitudeSquared() const;
  double getMagnitude2() const;
  Vec2D normalize() const;
  double crossProduct(Vec2D secondVector);
  Vec2D crossProduct(Vec2D secondVector);

  friend Vec2D operator+(const Vec2D&, const Vec2D&);
  friend ostream &operator<<(ostream&, const Vec2D&);
};

double dotProduct(const Vec2D, const Vec2D);

#endif

vec2d.cpp

#include <iostream>
#include <cmath>
using namespace std;

#include "Vec2D.h"  

// Constructors
Vec2D::Vec2D() { x = y = 0.0; }
Vec2D::Vec2D(double a, double b) { x = a; y = b; }

// Mutators
void Vec2D::setX(double a) { x = a; }
void Vec2D::setY(double a) { y = a; }

// Accessors
double Vec2D::getX() const { return x; }
double Vec2D::getY() const { return y; }
double Vec2D::getMagnitude() const { return sqrt((x*x) + (y*y)); }
double Vec2D::getMagnitudeSquared() const { return ((x*x) + (y*y)); }
double Vec2D::getMagnitude2 const { return getMagnitudeSquared(); }
double Vec2d::crossProduct(Vec2D secondVector) { return ((this.x * secondVector.getY())-(this.y * secondVector.getX()));}
Vec2D crossProduct(Vec2D secondVector) {return new Vec2D(this.y,-(this.x));}

Vec2D Vec2D::normalize() const {   return Vec2D(x/getMagnitude(), y/getMagnitude());}

Vec2D operator+(const Vec2D& a, const Vec2D& b) {  return Vec2D(a.x + b.x, a.y + b.y);}

ostream& operator<<(ostream& output, const Vec2D& a) {  output << "(" << a.x << ", " << a.y << ")" << endl;  return output;}

double dotProduct(const Vec2D a, const Vec2D b) {  return a.getX() * b.getX() + a.getY() * b.getY();}

检查一个点是否在由三个 vector 描述的三角形内:

float calculateSign(Vec2D v1, Vec2D v2, Vec2D v3)
{
  return (v1.getX() - v3.getX()) * (v2.getY() - v3.getY()) - (v2.getX() - v3.getX()) * (v1.getY() - v3.getY());
}

bool isPointInsideTriangle(Vec2D point2d, Vec2D v1, Vec2D v2, Vec2D v3)
{
  bool b1, b2, b3;
  // the < 0.0f is arbitrary, could have just as easily been > (would have flipped the results but would compare the same)
  b1 = calculateSign(point2d, v1, v2) < 0.0f;
  b2 = calculateSign(point2d, v2, v3) < 0.0f;
  b3 = calculateSign(point2d, v3, v1) < 0.0f;

  return ((b1 == b2) && (b2 == b3));
}

在上面的代码中，如果 calculateSign 在三角形中，您将得到返回的 true :)

希望这有帮助，如果您需要更多信息或更完整的 vec3d 或 2d 类，请告诉我，我可以发布:)

附录

我添加了一个小的 2d vector 类，以显示 2d 和 3d 的差异。