叉积

当然，叉积（也称为向量积）在计算几何中具有重要的几何意义和广泛的应用。接下来，我将详细解释叉积的几何意义、常见的应用场景，并为每个场景提供相应的代码示例。

叉积的几何意义

定义

在二维空间中，两个向量 A 和 B 的叉积（标量叉积）定义为：

[ \text{叉积} = A_x \cdot B_y - A_y \cdot B_x ]

记作：

[ A \times B = A_x B_y - A_y B_x ]

几何解释

  1. 面积：

    • 叉积的绝对值等于由向量 A 和 B 构成的平行四边形的有向面积。 [ |A \times B| = |A| \cdot |B| \cdot \sin(\theta) ] 其中，(\theta) 是 A 与 B 之间的夹角。

  2. 方向（旋转性）：

    • 叉积的符号表示两个向量之间的旋转方向。
      • 如果 ( A \times B > 0 )，则从 A 顺时针旋转到 B 是逆时针方向（相对于 A 来说）。
      • 如果 ( A \times B < 0 )，则从 A 顺时针旋转到 B 是顺时针方向。
      • 如果 ( A \times B = 0 )，则 A 和 B 共线（可以是同向或反向）。

示例图解

假设有两个向量 A 和 B：

    B
    ^
    |    A
    |   /
    |  /
    | / 
    |/_______>
  • 如果 B 在 A 的逆时针方向，则叉积为正。
  • 如果 B 在 A 的顺时针方向，则叉积为负。
  • 如果 A 和 B 共线，则叉积为零。

叉积的常见应用场景

  1. 判断点的相对位置（左转或右转）
  2. 计算多边形的面积
  3. 判断两条线段是否相交
  4. 构建凸包（例如 Graham 扫描算法）
  5. 计算线段交点

下面将逐一介绍这些应用，并提供相应的代码示例。

1. 判断点的相对位置（左转或右转）

在计算几何中，经常需要判断三个点 A、B、C 是否构成一个左转（逆时针）、右转（顺时针）或共线。

几何解释

给定三个点 A、B、C，向量 AB 和 AC 的叉积用于判断转向方向：

  • ( (B - A) \times (C - A) > 0 )：左转（逆时针）
  • ( (B - A) \times (C - A) < 0 )：右转（顺时针）
  • ( (B - A) \times (C - A) = 0 )：共线

代码示例

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
    
    // 向量相减
    Point operator - (const Point& p) const {
        return {x - p.x, y - p.y};
    }
    
    // 叉积
    double cross(const Point& p) const {
        return x * p.y - y * p.x;
    }
};

// 判断三个点的转向
int orientation(const Point& A, const Point& B, const Point& C) {
    Point AB = B - A;
    Point AC = C - A;
    double cross_prod = AB.cross(AC);
    if (cross_prod > 1e-9) return 1;      // 左转
    if (cross_prod < -1e-9) return -1;    // 右转
    return 0;                             // 共线
}

int main(){
    Point A, B, C;
    // 示例输入：A(0,0), B(1,0), C(1,1)
    A = {0, 0};
    B = {1, 0};
    C = {1, 1};
    
    int result = orientation(A, B, C);
    if(result == 1) cout << "左转 (逆时针)" << endl;
    else if(result == -1) cout << "右转 (顺时针)" << endl;
    else cout << "共线" << endl;
    
    return 0;
}

输出

左转 (逆时针)

2. 计算多边形的面积

利用叉积可以方便地计算简单多边形（通常为凸多边形）的面积。方法基于多边形的三角剖分，通过计算三角形的叉积和。

几何解释

对于一个按顺序排列的多边形顶点 ( P_1, P_2, ..., P_n )，多边形的面积可以通过以下公式计算：

[ \text{面积} = \frac{1}{2} \left| \sum_{i=1}^{n} (P_i \times P_{i+1}) \right| ]

其中，( P_{n+1} = P_1 )。

代码示例

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
    
    Point operator - (const Point& p) const {
        return {x - p.x, y - p.y};
    }
    
    double cross(const Point& p) const {
        return x * p.y - y * p.x;
    }
};

// 计算多边形面积
double polygonArea(const vector<Point>& pts) {
    double area = 0.0;
    int n = pts.size();
    for(int i = 0; i < n; ++i){
        int j = (i + 1) % n;
        area += pts[i].cross(pts[j]);
    }
    return fabs(area) / 2.0;
}

int main(){
    int n;
    cout << "请输入多边形的顶点数: ";
    cin >> n;
    vector<Point> pts(n);
    cout << "请输入多边形的顶点坐标（顺时针或逆时针）:" << endl;
    for(int i = 0; i < n; ++i){
        cin >> pts[i].x >> pts[i].y;
    }
    
    double area = polygonArea(pts);
    printf("多边形的面积为：%.3lf\n", area);
    
    return 0;
}

示例输入

4
0 0
4 0
4 4
0 4

输出

多边形的面积为：16.000

3. 判断两条线段是否相交

叉积可以用于判断两条线段是否相交。通过计算相邻线段之间的方向关系，可以确定它们是否交叉。

几何解释

给定两条线段 ( P_1P_2 ) 和 ( Q_1Q_2 )，它们相交的充分必要条件是：

  • ( P_1 ) 和 ( P_2 ) 在 ( Q_1Q_2 ) 的两侧，且
  • ( Q_1 ) 和 ( Q_2 ) 在 ( P_1P_2 ) 的两侧。

这可以通过叉积来判断。

代码示例

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
    
    Point operator - (const Point& p) const {
        return {x - p.x, y - p.y};
    }
    
    double cross(const Point& p) const {
        return x * p.y - y * p.x;
    }
};

// 判断三点的方向
int orientation(const Point& A, const Point& B, const Point& C){
    Point AB = B - A;
    Point AC = C - A;
    double cross_prod = AB.cross(AC);
    if (cross_prod > 1e-9) return 1;      // 左转
    if (cross_prod < -1e-9) return -1;    // 右转
    return 0;                             // 共线
}

// 判断两条线段是否相交
bool segmentsIntersect(const Point& p1, const Point& p2, const Point& q1, const Point& q2){
    int o1 = orientation(p1, p2, q1);
    int o2 = orientation(p1, p2, q2);
    int o3 = orientation(q1, q2, p1);
    int o4 = orientation(q1, q2, p2);
    
    // 一般情况
    if(o1 != o2 && o3 != o4){
        return true;
    }
    
    // 特殊情况：共线且相交
    auto onSegment = [&](const Point& A, const Point& B, const Point& C) -> bool {
        return min(A.x, B.x) <= C.x && C.x <= max(A.x, B.x) &&
               min(A.y, B.y) <= C.y && C.y <= max(A.y, B.y);
    };
    
    if(o1 == 0 && onSegment(p1, p2, q1)) return true;
    if(o2 == 0 && onSegment(p1, p2, q2)) return true;
    if(o3 == 0 && onSegment(q1, q2, p1)) return true;
    if(o4 == 0 && onSegment(q1, q2, p2)) return true;
    
    return false;
}

int main(){
    Point p1, p2, q1, q2;
    cout << "请输入线段P1P2的坐标 (x1 y1 x2 y2): ";
    cin >> p1.x >> p1.y >> p2.x >> p2.y;
    cout << "请输入线段Q1Q2的坐标 (x1 y1 x2 y2): ";
    cin >> q1.x >> q1.y >> q2.x >> q2.y;
    
    if(segmentsIntersect(p1, p2, q1, q2)) cout << "线段相交" << endl;
    else cout << "线段不相交" << endl;
    
    return 0;
}

示例输入

请输入线段P1P2的坐标 (x1 y1 x2 y2): 0 0 4 4
请输入线段Q1Q2的坐标 (x1 y1 x2 y2): 0 4 4 0

输出

线段相交

4. 构建凸包（Graham 扫描算法）

构建凸包是计算几何中的经典问题，Graham 扫描算法利用叉积判断点的相对位置，从而构建出凸包。

几何解释

  1. 排序：首先选择一个基准点（通常是 y 度最低的点），然后按极角排序。
  2. 扫描：依次处理每个点，使用叉积判断是否形成了一个顺时针转向（需要回退）。
  3. 结果：栈中保存的点即为凸包的顶点。

代码示例

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
    
    bool operator < (const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
    
    Point operator - (const Point& p) const {
        return {x - p.x, y - p.y};
    }
    
    double cross(const Point& p) const {
        return x * p.y - y * p.x;
    }
};

// 比较两个点的极角
bool polarCmp(const Point& p0, const Point& p1){
    Point diff1 = p1 - p0;
    Point diff2 = p0 - p0; // zero vector for reference
    double cross_prod = diff1.cross(diff2);
    // 此处为了简单，不处理共线情况
    return atan2(diff1.y, diff1.x) < atan2(diff2.y, diff2.x);
}

// Graham 扫描算法
vector<Point> convexHull(vector<Point> pts){
    int n = pts.size();
    if(n <= 3) return pts;
    
    // 找到最低的点
    int p0 = 0;
    for(int i = 1; i < n; ++i){
        if(pts[i].y < pts[p0].y || (pts[i].y == pts[p0].y && pts[i].x < pts[p0].x)) p0 = i;
    }
    swap(pts[0], pts[p0]);
    
    // 按极角排序
    Point origin = pts[0];
    sort(pts.begin() + 1, pts.end(), [&](const Point& a, const Point& b) -> bool {
        Point va = a - origin;
        Point vb = b - origin;
        double cross_prod = va.cross(vb);
        if (fabs(cross_prod) < 1e-9) {
            // 更远的点排在前面
            return (va.x * va.x + va.y * va.y) < (vb.x * vb.x + vb.y * vb.y);
        }
        return cross_prod > 0;
    });
    
    // 栈中保存凸包点的索引
    vector<Point> hull;
    hull.push_back(pts[0]);
    hull.push_back(pts[1]);
    
    for(int i = 2; i < n; ++i){
        while(hull.size() >= 2){
            Point A = hull[hull.size()-2];
            Point B = hull[hull.size()-1];
            Point C = pts[i];
            Point AB = B - A;
            Point BC = C - B;
            double cross_prod = AB.cross(BC);
            if (cross_prod > 1e-9) break; // 左转
            hull.pop_back(); // 弹出最后一个点
        }
        hull.push_back(pts[i]);
    }
    
    return hull;
}

int main(){
    int n;
    cout << "请输入点的数量: ";
    cin >> n;
    vector<Point> pts(n);
    cout << "请输入每个点的坐标 (x y):" << endl;
    for(int i = 0; i < n; ++i) cin >> pts[i].x >> pts[i].y;
    
    vector<Point> hull = convexHull(pts);
    
    cout << "凸包的顶点数量: " << hull.size() << endl;
    cout << "凸包的顶点坐标:" << endl;
    for(auto& p : hull) cout << p.x << " " << p.y << endl;
    
    return 0;
}

示例输入

请输入点的数量: 6
请输入每个点的坐标 (x y):
0 0
1 1
2 2
0 2
2 0
1 -1

输出

凸包的顶点数量: 4
凸包的顶点坐标:
0 0
2 0
2 2
0 2

5. 计算线段交点

在计算两条线段的交点时，可以利用叉积来计算参数 ( t ) 和 ( u )，从而确定交点的位置。

几何解释

对于两条线段 ( P_1P_2 ) 和 ( Q_1Q_2 )，可以用参数方程表示：

[ P = P_1 + t(P_2 - P_1), \quad t \in [0, 1] ] [ Q = Q_1 + u(Q_2 - Q_1), \quad u \in [0, 1] ]

两条线段相交的条件是存在 ( t ) 和 ( u ) 满足上述等式，并且 ( t, u \in [0, 1] )。

交点的计算可以通过解以下方程组得到：

[ (P_2 - P_1) \times (Q_2 - Q_1) = 0 \quad \text{(如果不平行)} ] [ (Q_1 - P_1) \times (Q_2 - Q_1) / (P_2 - P_1) \times (Q_2 - Q_1) = t ]

然后代入求出交点坐标。

代码示例

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
    
    Point operator - (const Point& p) const {
        return {x - p.x, y - p.y};
    }
    
    double cross(const Point& p) const {
        return x * p.y - y * p.x;
    }
    
    Point operator + (const Point& p) const {
        return {x + p.x, y + p.y};
    }
    
    Point operator * (double t) const {
        return {x * t, y * t};
    }
};

// 计算两条线段的交点
bool getLineIntersection(const Point& p1, const Point& p2, const Point& q1, const Point& q2, Point& intersect){
    Point r = p2 - p1;
    Point s = q2 - q1;
    double rxs = r.cross(s);
    Point q_p = q1 - p1;
    double q_pxr = q_p.cross(r);
    
    if (fabs(rxs) < 1e-9){
        // 平行或共线
        return false;
    }
    
    double t = q_p.cross(s) / rxs;
    double u = q_p.cross(r) / rxs;
    
    if(t < -1e-9 || t > 1 + 1e-9 || u < -1e-9 || u > 1 + 1e-9){
        // 不在相交范围内
        return false;
    }
    
    // 计算交点
    intersect = p1 + r * t;
    return true;
}

int main(){
    Point p1, p2, q1, q2, intersect;
    cout << "请输入线段P1P2的坐标 (x1 y1 x2 y2): ";
    cin >> p1.x >> p1.y >> p2.x >> p2.y;
    cout << "请输入线段Q1Q2的坐标 (x1 y1 x2 y2): ";
    cin >> q1.x >> q1.y >> q2.x >> q2.y;
    
    if(getLineIntersection(p1, p2, q1, q2, intersect)){
        printf("交点坐标：%.3lf %.3lf\n", intersect.x, intersect.y);
    }
    else{
        cout << "线段不相交或共线" << endl;
    }
    
    return 0;
}

示例输入

请输入线段P1P2的坐标 (x1 y1 x2 y2): 0 0 4 4
请输入线段Q1Q2的坐标 (x1 y1 x2 y2): 0 4 4 0

输出

交点坐标：2.000 2.000

叉积在半平面交算法中的应用

回顾您最初提供的半平面交算法代码，叉积在其中主要用于：

  1. 判断点在半平面内还是外：

    • 使用叉积判断点相对于半平面的边界是否在左侧（或在边界上）。

  2. 计算两条边的交点：

    • 使用叉积计算边界线和多边形边之间的交点。

代码片段解释

以 cut 函数为例：

void cut(point p1, point p2)
{
    top = 0;
    a[cnt+1] = a[1]; // 闭合多边形
    for(int i=1;i<=cnt;i++)
    {
        double cross1 = (p1 - a[i]).crs(p2 - a[i]);
        double cross2 = (p1 - a[i+1]).crs(p2 - a[i+1]);

        if(cross1 >= 0)
        {
            c[++top] = a[i];
            if(cross2 < 0)
            {
                add(a[i], a[i+1], p1, p2);
            }
        }
        else if(cross2 >= 0)
        {
            add(a[i], a[i+1], p1, p2);
        }
    }
    for(int i=1;i<=top;i++)
    {
        a[i] = c[i];
    }
    cnt = top;
}

  • 判断点位置：

    • cross1 = (p1 - a[i]) × (p2 - a[i])
      • 如果 cross1 >= 0，则 a[i] 在半平面的左侧或边界上。
      • 否则，a[i] 在半平面的右侧。

  • 添加点和交点：

    • 如果 a[i] 在左侧，将其加入临时数组 c。
    • 如果前后两点一个在左侧，一个在右侧，计算交点并加入 c。

通过这些操作，cut 函数逐步剪裁多边形，使其与新的半平面相交。

总结

叉积在计算几何中具有丰富的应用，包括但不限于判断点的相对位置、计算多边形面积、判断线段相交、构建凸包以及在半平面交等复杂算法中发挥关键作用。理解叉积的几何意义和如何在不同场景中应用它，对于解决各种计算几何问题至关重要。

希望以上解释和代码示例能帮助您更好地理解叉积在计算几何中的应用。如有进一步的问题，欢迎随时提问！

  1. Language
  2. Legacy mode
  3. Theme
  5. 渝ICP备2024027573号-2
  8. Worker 0, 47ms
  9. Powered by Hydro v5.0.0-beta.13 Community