点

摘要: 本文介绍计算几何中与点相关的基本问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，在文章 向量的实现 中，我们实现了一个二维向量的代码模板，主要是 Vector2 这个类。

本文我们介绍计算几何中关于点的常见问题，主要涉及以下内容：

• 两点位置关系
• 三点位置关系
  • 点与直线位置关系
  • 点与线段位置关系
• 点到直线的距离
• 点到线段的距离

二维向量与二维平面的点一一对应，因此用二维向量的理论解决前面的问题非常方便，几个问题的代码都是基于前面的二维向量的代码模板的，也就是用 Vector2 这个类的对象来表示点。

力扣中有两个相关的题目，1232 和 1401，题解代码也用的 Vector2 这个代码模板。

---

1. 两点位置关系

p1, p2 是 Vector2 的对象，表示两个点。

两个点的位置关系，常见的问题是判断两个点是否重合，如果不重合的话，它们的距离是多少。

判断两个点是否重合

p1 == p2

两个点之间的欧氏距离

(p2 - p1).norm();

---

2. 三点位置关系

三个点的位置关系，也就是问三个点是不是共线。可以转换为问某一个点是否落在另外两个点表示的直线上。

(1) 点与直线位置关系

其中 a, b, c 是 Vector2 类的对象，表示三个点。

点 a 与直线 (b, c) 的关系，可以转化为两个向量 (b - a), (c - a) 的关系。

代码模板

double r = ccw(b - a, c - a);
// r > 0, c - a 在 b - a 的逆时针 180 范围内
// r < 0, c - a 在 b - a 的顺时针 180 范围内
// r = 0: c - a 与 b - a 平行

题目: 1232. 缀点成线

给定一个数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。

提示：

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-1e4 <= coordinates[i][0], coordinates[i][1] <= 1e4
coordinates 中不含重复的点

示例 1：
输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true

示例 2：
输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

代码

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int n = coordinates.size();
        Vector2 a(coordinates[0][0], coordinates[0][1]);
        Vector2 b(coordinates[1][0], coordinates[1][1]);
        for(int i = 2; i < n; ++i)
        {
            Vector2 c(coordinates[i][0], coordinates[i][1]);
            double r = ccw(c - a, c - b);
            if(fabs(r) >= EPS)
                return false;
        }
        return true;
    }
};

(2) 点是否在线段上

其中 x, a, b 是 Vector2 类的对象，表示三个点。

如果点 x 在直线 ab 上，那么我们还可以进一步问 x 是否在线段 ab 上。

此时只需要判断 x 是否在包含点 a, b 且各边平行于 x 轴，y 轴的最小四边形内部即可。

代码模板

// 判断点是否落在线段上
bool inBoundingRectangle(Vector2 x, Vector2 a, Vector2 b)
{
    // x, a, b 同线
    // 判断 x 是否在包含点 a, b 且各边平行于 x 轴，y 轴的最小四边形内部。
    if(b < a) 
        swap(a, b);
    return x == a || x == b || (a < x && x < b);
}

---

3. 点到直线的距离

求点 p 到直线 ab 的距离。先计算出点 p 到直线 (a, b) 的垂足。再计算点与垂足之间的距离即可。

代码模板

// 点和直线的距离
Vector2 perpendicularFoot(Vector2 p, Vector2 a, Vector2 b)
{
    // p 到 (a, b) 的垂足
    return a + (p - a).project(b - a);
}

double pointToTline(Vector2 p, Vector2 a, Vector2 b)
{
    // p 到直线 (a, b) 的距离
    return (p - perpendicularFoot(p, a, b)).norm();
}

---

4. 点到线段的距离

若垂足落在线段上，则 P 到线段的距离就是点到直线的距离。

垂足没有落在线段上，那么两个端点中，距离 P 最近的端点到 P 的距离为点和线段之间的距离。

点到线段的距离可以推广到线段到线段的距离，因为两条线段的最短距离一定从四个端点的其中一个开始。

代码模板

// 判断交点是否落在线段上
bool inBoundingRectangle(Vector2 x, Vector2 a, Vector2 b)
{
    // x, a, b 同线
    // 判断 x 是否在包含 (a, b) 且各边平行于 x 轴，y 轴的最小四边形内部。
    if(b < a) 
        swap(a, b);
    return x == a || x == b || (a < x && x < b);
}

// 点和线段的距离
Vector2 perpendicularFoot(Vector2 p, Vector2 a, Vector2 b)
{
    // p 到 (a, b) 的垂足
    return a + (p - a).project(b - a);
}

double pointToTlineSeg(Vector2 p, Vector2 a, Vector2 b)
{
    // p 到直线 (a, b) 的距离
    Vector2 foot = perpendicularFoot(p, a, b);
    if(inBoundingRectangle(foot, a, b)) // 垂足在线段上
        return (p - foot).norm();
    return min((p - a).norm(), (p - b).norm());
}

题目: 1401. 圆和矩形是否有重叠

给你一个以 (radius, xCenter, yCenter) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2) ，其中 (x1, y1) 是矩形左下角的坐标，而 (x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分，请你返回 true ，否则返回 false 。

换句话说，请你检测是否 存在 点 (xi, yi) ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。

示例 1 ：
输入：radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出：true
解释：圆和矩形存在公共点 (1,0) 。

示例 2 ：
输入：radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出：false

示例 3 ：
输入：radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出：true

提示：

1 <= radius <= 2000
-1e4 <= xCenter, yCenter <= 1e4
-1e4 <= x1 < x2 <= 1e4
-1e4 <= y1 < y2 <= 1e4

代码

首先判断圆心是否在四边形内部, 也就是下面代码中的 isInside 函数，这是判断点在多边形内部还是外部的代码模板，原理参考 多边形 这篇文章。

之后求圆心到四条线段的距离即可。

class Solution {
public:
    bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
        vector<Vector2> p;
        p.emplace_back(x1, y1);
        p.emplace_back(x2, y1);
        p.emplace_back(x2, y2);
        p.emplace_back(x1, y2);
        Vector2 O(x_center, y_center);
        if(isInside(p, O))
            return true;
        for(int i = 0; i < 4; ++i)
        {
            int j = (i + 1) % 4;
            double d = pointToTlineSeg(O, p[i], p[j]);
            if(d < radius || fabs(d - radius) < EPS)
                return true;
        }
        return false;
    }
};

// 点 q 是否包含在多边形 p 内部
// q 在多边形边上没有处理
bool isInside(const vector<Vector2>& p, Vector2 q)
{
    int crosses = 0;
    int n = p.size();
    for(int i = 0; i < n; ++i)
    {
        int j = (i + 1) % n;
        // p[i], p[j] 能否纵向分割射线
        if((p[i].y > q.y) != (p[j].y > q.y))
        {
            // 交点的横坐标
            double X = (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x;
            if(q.x < X)
                ++crosses;
        }
    }
    return crosses % 2 == 1;
}

---