计算机图形学实验报告

实验1：平面三角形点定位算法

1.实验内容

ps：报告图片为对应程序用OpenCV绘制。

（1）方法1：射线求交法（交点个数判断）

基本原理：
从P点分别向AB、BC和CA方向做射线，分别去求往BC、CA和AB的交点。当P点在三角形ABC内时，如下图，三个测试得到3个交点；

image-20240314230147918

而当P点在三角形外时，如下图，将得到少于3个交点

image-20240314230302250

另外，当P在三角形边上是，按在三角形内来算：

image-20240314230348531

计算方法

通过给定的A，B，C和P点坐标，先编写一函数判断射线和线段是否相交并求交点：

根据
$$
P+t\vec{d}=A+u\vec{AB}
$$
其中向量d为射线方向，A,B为线段两端得到
$$
\begin{bmatrix}
\vec{d} & \vec{BA}
\end{bmatrix}
\begin{pmatrix}
t \u
\end{pmatrix}=\vec{PA}
$$
再根据克莱姆法则解出t、u

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isCross(Vector2f P,Vector2f d,Vector2f A,Vector2f B,double &t) //判断射线与线段是否相交
{
    Vector2f PA = A - P;   
    Vector2f BA = A - B;
    if(d[0]*BA[1]-d[1]*BA[0]!=0){
        t=(PA[0]*BA[1]-PA[1]*BA[0])/(d[0]*BA[1]-d[1]*BA[0]);
        double u=(d[0]*PA[1]-d[1]*PA[0])/(d[0]*BA[1]-d[1]*BA[0]);
        if(t>=0&&u>=0&&u<=1){
            return true;
        }
        else{
            return false;
        }  
    }
    return true;
}

运行测试：通过标准输入选取点的坐标，输出保存在output.png文件

image-20240314231353264

（2）方法2：面积法

基本原理：分别计算三角形ABC、PAB、PBC、PCA的面积，若后三者面积相加等于S_ABC,则P在三角形内；

image-20240314231103537

否则（大于S_ABC）则在三角形外。

image-20240314231534999

计算方法：对于三角形ABC，其面积可用任两边向量叉乘取模再除2得到

关键代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
double S_ABC = 0.5 * AB.cross(AC).norm();
double S_PAB = 0.5 * PA.cross(PB).norm();
double S_PBC = 0.5 * PB.cross(PC).norm();
double S_PCA = 0.5 * PC.cross(PA).norm();
if(!(abs(S_PAB) < 1e-6 || abs(S_PBC) < 1e-6 || abs(S_PCA) < 1e-6)){
    if(abs(S_PAB + S_PBC + S_PCA - S_ABC) < 1e-6){ // 浮点数比较,防止机器误差
        text = "P is in the triangle";
    }
    else{
        text = "P is NOT in the triangle";
    }
    putText(img, text, Point(0, 200), FONT_HERSHEY_SIMPLEX, 1, Scalar(0, 255, 255, 255), 2);
}

运行测试：同方法1.

（3）方法3：同侧法

基本原理：若P在ABC内，则AP、BP、CP必定分别在AB、BC、CA同侧；

image-20240314233052073

否则在ABC外。

output (1)

计算方法：判断向量AP在AB哪一侧可以用$\vec{AB} \times \vec{AP}$的符号判断，若为正，根据右手定则，AP在AB左侧，否则在右侧。

1
2
3
4
5
6
if (AB.cross(AP).dot(BC.cross(AP))> 0 && BC.cross(BP).dot(CA.cross(BP)) > 0 && CA.cross(CP).dot(AB.cross(CP)) > 0){
    text = "P is in the triangle";
}
else{
    text = "P is NOT in the triangle";
}

绘图方法：此方法绘图在于绘制一个角度弧来展示同侧方向，利用OpenCV库函数ellipse：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 画夹角,小于180度
void draw_angle(Mat img, Point2d p0, Point2d p1, Point2d p2, double radius)
{
    // 计算直线的角度
    double angle1 = atan2(-(p1.y - p0.y), (p1.x - p0.x)) * 180 / CV_PI;
    double angle2 = atan2(-(p2.y - p0.y), (p2.x - p0.x)) * 180 / CV_PI;
    // 计算主轴的角度
    double angle = angle1 <= 0 ? -angle1 : 360 - angle1;
    // 计算圆弧夹角角度
    double end_angle = (angle2 < angle1) ? (angle1 - angle2) : (360 - (angle2 - angle1));
    // 画圆弧
    if(end_angle > 180) // 大于180度的圆弧需要特殊处理
        ellipse(img, p0, Size(radius, radius),angle, 0, end_angle-360, Scalar(0,255,0,255), 2);
    else
        ellipse(img, p0, Size(radius, radius), angle, 0, end_angle, Scalar(0,255,0,255), 2);
}

运行测试：同方法1.