当前位置：首页 > article >正文

【GIS】算法原理：点、线、矩形的空间关系

article 2025/3/6 3:06:57

点与矩形的空间关系

判断矩形是否包含点

原理

矩形的左右边界由最小和最大横坐标定义，上下边界由最小和最大纵坐标定义。
若点的横坐标和纵坐标分别位于矩形的左右边界和上下边界之间，则该点位于矩形内。

判断规则

条件：

rectMinX ≤ pointX ≤ rectMaxX

rectMinY ≤ pointY ≤ rectMaxY

点与多边形的空间关系

射线法（Ray Casting Algorithm）

原理

从待判断点引一条水平向右的射线，计算射线与多边形边界的交点数量。
若交点数量为奇数，则点在多边形内；若为偶数，则点在多边形外。

特殊情况

射线与多边形顶点相交时，需特殊处理（通常只计一次交点）。

转角法（Winding Number Algorithm）

原理

计算点与多边形各顶点连线的转角之和。
若转角之和为360度（或2π弧度），则点在多边形内；否则在多边形外。

点与圆的空间关系

判断点是否在圆内

原理

计算点到圆心的距离，若距离小于或等于圆的半径，则点在圆内。

公式

距离公式：

distance = sqrt((pointX - centerX)^2 + (pointY - centerY)^2)
判断条件：

distance ≤ radius

C++代码实现

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

// 二维点结构体
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

// 矩形结构体
struct Rectangle {
    double minX, minY, maxX, maxY;
    Rectangle(double minX, double minY, double maxX, double maxY)
        : minX(minX), minY(minY), maxX(maxX), maxY(maxY) {}
};

// 圆结构体
struct Circle {
    Point center;
    double radius;
    Circle(Point center, double radius) : center(center), radius(radius) {}
};

// 判断矩形是否包含点
bool isPointInRectangle(const Point& point, const Rectangle& rect) {
    return (point.x >= rect.minX && point.x <= rect.maxX &&
            point.y >= rect.minY && point.y <= rect.maxY);
}

// 判断点是否在多边形内（射线法）
bool isPointInPolygon(const Point& point, const vector<Point>& polygon) {
    int n = polygon.size();
    bool inside = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        if (((polygon[i].y > point.y) != (polygon[j].y > point.y)) &&
            (point.x < (polygon[j].x - polygon[i].x) * (point.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x))
            inside = !inside;
    }
    return inside;
}

// 判断点是否在圆内
bool isPointInCircle(const Point& point, const Circle& circle) {
    double dx = point.x - circle.center.x;
    double dy = point.y - circle.center.y;
    double distance = sqrt(dx * dx + dy * dy);
    return distance <= circle.radius;
}

int main() {
    // 测试矩形包含点
    Rectangle rect(0, 0, 4, 4);
    Point point(2, 2);
    cout << "点是否在矩形内: " << isPointInRectangle(point, rect) << endl;

    // 测试多边形包含点
    vector<Point> polygon = {{0, 0}, {4, 0}, {4, 4}, {0, 4}};
    cout << "点是否在多边形内: " << isPointInPolygon(point, polygon) << endl;

    // 测试圆包含点
    Circle circle(Point(2, 2), 2);
    cout << "点是否在圆内: " << isPointInCircle(point, circle) << endl;

    return 0;
}