Martian148's blog Martian148's blog
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档

Martian148

一只热爱文科的理科生
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档
  • 线上赛板子(实时更新)
  • 数据结构

  • 数学

  • 计算几何

    • 二维计算几何基础(总结)
    • 三维计算几何基础
      • 定义
      • 基本运算
        • 点积
        • 长度
        • 向量夹角
        • 叉积
        • 三角形的有向面积的两倍
      • 点、线、面
        • 点到直线的距离
        • 点在直线上的投影
        • 点到平面的距离
        • 点在平面上的投影点
        • 直线和直线的交点
        • 直线和平面的交点
      • 体
        • 四面体的体积
    • 圆相关计算
    • 凸包
    • 半平面交
  • 动态规划

  • 图论

  • 字符串

  • 杂项

  • 算法笔记
  • 计算几何
martian148
2024-08-29
目录

三维计算几何基础

# 三维计算几何基础

# 定义

struct Point3{
    double x,y,z;
    Point3(double x=0,double y=0,double z=0):x(x),y(y),z(z){}
};
typedef Point3 Vector3;
1
2
3
4
5

# 基本运算

Vector3 operator +(Vector3 A,Vector3 B){return Vector3(A.x+B.x,A.y+B.y,A.z+B.z);}
Vector3 operator -(Point3 A,Point3 B){return Vector3(A.x-B.x,A.y-B.y,A.z-B.z);}
Vector3 operator *(Vector3 A,double p){return Vector3(A.x*p,A.y*p,A.z*p);}
Vector3 operator /(Vector3 A,double p){return Vector3(A.x/p,A.y/p,A.z/p);}
1
2
3
4

直线的表示,可以用参数方程 (点和向量)来表示,射线和线段可以看成”参数由取值范围限制的“的直线

平面的表示,用点法式 (p0,n)(p_0,n)(p0​,n), 其中 p0p_0p0​ 是平面上的一个点,向量 nnn 是平面的法向量。每个平面把空间分成了两个部分,我们用点法式表示其中一个半空间,是法向量所背离的哪一个。nnn 垂直于平面上的所有直线。平面上任意点 ppp 满足 Dot(n,p−p0)=0Dot(n,p-p_0)=0Dot(n,p−p0​)=0 。设 ppp 的坐标为 (x,y,z)(x,y,z)(x,y,z) ,p0p_0p0​ 的坐标为 (x0,y0,z0)(x_0,y_0,z_0)(x0​,y0​,z0​) ,向量 nnn 的坐标表示为 (A,B,C)(A,B,C)(A,B,C) 上述等式等价于

A(x−x0)+B(y−y0)+C(z−z0)=0 A(x-x_0)+B(y-y_0)+C(z-z_0)=0 A(x−x0​)+B(y−y0​)+C(z−z0​)=0

整理得: Ax+By+Cz−(Ax0+By0+Cz0)=0Ax+By+Cz-(Ax_0+By_0+Cz_0)=0Ax+By+Cz−(Ax0​+By0​+Cz0​)=0 如果令 −(Ax0+By0+Cz0)-(Ax_0+By_0+Cz_0)−(Ax0​+By0​+Cz0​),就得到了平面的一般式

Ax+By+Cz+D=0 Ax+By+Cz+D=0 Ax+By+Cz+D=0

当 Ax+By+Cz+D>0Ax+By+Cz+D>0Ax+By+Cz+D>0 上述点积大于 000 ,即点 (x,y,z)(x,y,z)(x,y,z) 在半平面空间 (p0,n)(p_0,n)(p0​,n) 外。换句话说 Ax+By+Cz+D>0Ax+By+Cz+D>0Ax+By+Cz+D>0 表示的是以一个半空间

# 点积

double dot(Vector3 A, Vector3 B) { return A.x * B.x + A.y * B.y + A.z * B.z; }
1

# 长度

double length(Vector3 A) { return sqrt(dot(A, A)); }
1

# 向量夹角

double angle(Vector3 A, Vector3 B) { return acos(dot(A, B) / length(A) / length(B)); }
1

# 叉积

三维叉积的结果是一个向量

v1×v2=[y1z2−y2z1z1x2−z2x1x1y2−x2y1] v_1\times v_2=\begin{bmatrix}y_1z_2-y_2z_1\\z_1x_2-z_2x_1\\x_1y_2-x_2y_1\end{bmatrix} v1​×v2​=⎣⎢⎡​y1​z2​−y2​z1​z1​x2​−z2​x1​x1​y2​−x2​y1​​⎦⎥⎤​

叉积同时垂直于 v1v_1v1​ 和 v2v_2v2​ ,方向遵循右手定则。当且仅当 v1v_1v1​ 和 v2v_2v2​ 平行时,叉积为 000

Vector3 cross(Vector3 A, Vector3 B) {
    return Vector3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}
1
2
3

通过向量叉积,可以进行一些拓展的基础问题。

过不共线的三点的平面,法向量为 Cross⁡(p2−p0,p1−p0)\operatorname{Cross}(p_2-p_0,p_1-p_0)Cross(p2​−p0​,p1​−p0​) ,任取一个点即可得到平面的点法式。

# 三角形的有向面积的两倍

double area2(Point3 A, Point3 B, Point3 C) { return length(cross(B - A, C - A)); }
1

# 点、线、面

# 点到直线的距离

double distance_to_line(Point3 p, Point3 p0, Vector3 v) {
    return length(cross(p - p0, v)) / length(v);
}
1
2
3

# 点在直线上的投影

Point3 line_projection(Point3 p, Point3 p0, Vector3 v) {
    return p0 + v * dot(p - p0, v) / dot(v, v);
}
1
2
3

# 点到平面的距离

image.png

把 p−p0p-p_0p−p0​ 投影到向量 nnn 上可得 :ppp 到平面的有向距离为 Dot(p−p0,n)/Length(n)Dot(p-p_0,n)/Length(n)Dot(p−p0​,n)/Length(n)。

double distance_to_plane(Point3 p, Point3 p0, Vector3 n) {
    return fabs(dot(p - p0, n) / length(n));
}  //点 p 到平面 p0-n 的距离,如果不取绝对值,得到的是有向距离
1
2
3

# 点在平面上的投影点

设 ppp 在平面 (p0,n)(p_0,n)(p0​,n) 上的投影为 p′p'p′ 则 p′−pp'-pp′−p 平行于 nnn ,且 p′−p=dnp'-p=dnp′−p=dn 其中 ddd 为 ppp 到平面的的有向距离

Point3 plane_projection(Point3 p, Point3 p0, Vector3 n) {
    return p - n * dot(p - p0, n) / length(n);
}
1
2
3

# 直线和直线的交点

Point3 line_intersection(Point3 p, Vector3 v, Point3 q, Vector3 w) {
    Vector3 u = p - q;
    double t = length(cross(w, u)) / length(cross(v, w));
    return p + v * t;
}
1
2
3
4
5

# 直线和平面的交点

设平面方程为 Dot⁡(n,p−p0)=0\operatorname{Dot}(n,p-p_0)=0Dot(n,p−p0​)=0,过点 p1p_1p1​ 和 p2p_2p2​ 的直线的参数方程为 p=p1+t(p2−p1)p=p_1+t(p_2-p_1)p=p1​+t(p2​−p1​) ,则与平面方程联立解得

t=Dot⁡(n,p0−p1)/Dot⁡(n,p2−p1) t=\operatorname{Dot}(n,p_0-p_1)/\operatorname{Dot}(n,p_2-p_1) t=Dot(n,p0​−p1​)/Dot(n,p2​−p1​)

如果分母为 000 则直线和平面平行,或者直线在平面上

如果平面用一般式 Ax+By+Cz+D=0Ax+By+Cz+D=0Ax+By+Cz+D=0 ,则联立出来的表达式为

t=Ax1+By1+Cz1+DA(x1−x2)+B(y1−y2)+C(z1−z2) t=\frac{Ax_1+By_1+Cz_1+D}{A(x_1-x_2)+B(y_1-y_2)+C(z_1-z_2)} t=A(x1​−x2​)+B(y1​−y2​)+C(z1​−z2​)Ax1​+By1​+Cz1​+D​
Point3 line_plane_intersection(Point3 p, Vector3 v, Point3 p0, Vector3 n) {
    Vector3 u = p - p0;
    double t = dot(n, u) / dot(n, v);
    return p - v * t;
}
1
2
3
4
5

# 体

# 四面体的体积

已知 444 个顶点为 A,B,C,DA,B,C,DA,B,C,D

V=13S⋅h=16(AB→×AC→)⋅h=16(AB→×AC→)⋅AD→ V=\frac{1}{3}S\cdot h = \frac{1}{6}(\overrightarrow{AB}\times \overrightarrow{AC})\cdot h=\frac{1}{6}(\overrightarrow{AB}\times \overrightarrow{AC})\cdot \overrightarrow{AD} V=31​S⋅h=61​(AB×AC)⋅h=61​(AB×AC)⋅AD
double volume6(Point3 A, Point3 B, Point3 C, Point3 D) {
    return dot(D - A, cross(B - A, C - A));
}
1
2
3
上次更新: 2025/04/08, 18:03:31
二维计算几何基础(总结)
圆相关计算

← 二维计算几何基础(总结) 圆相关计算→

最近更新
01
在 ACM 集训队年会上的讲话
07-01
02
计算机网络笔记
06-13
03
LLM101 NLP学习笔记
06-02
更多文章>
Theme by Vdoing | Copyright © 2024-2025 Martian148 | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式