判断任意点是否在多边形内

在C++中，可以使用射线法来判断一个点是否在多边形内。下面是一个基于射线法的C++代码示例：

#include <iostream>
#include <vector>

struct Point {
    double x, y;
};

// 判断点是否在线段上
bool onSegment(Point p, Point q, Point r) {
    return q.x <= std::max(p.x, r.x) && q.x >= std::min(p.x, r.x) &&
           q.y <= std::max(p.y, r.y) && q.y >= std::min(p.y, r.y);
}

// 计算方向
int orientation(Point p, Point q, Point r) {
    double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0; // 共线
    return (val > 0) ? 1 : 2; // 顺时针或逆时针
}

// 检查两条线段是否相交
bool doIntersect(Point p1, Point q1, Point p2, Point q2) {
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4) return true;

    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false;
}

// 判断点是否在多边形内
bool isInsidePolygon(const std::vector<Point>& polygon, Point p) {
    int n = polygon.size();
    if (n < 3) return false; // 多边形至少需要3个点

    // 创建射线，起点为测试点，终点为右方远点
    Point extreme = {1e10, p.y};
    int count = 0, i = 0;

    do {
        int next = (i + 1) % n;

        // 检查射线是否和多边形的边相交
        if (doIntersect(polygon[i], polygon[next], p, extreme)) {
            if (orientation(polygon[i], p, polygon[next]) == 0) {
                return onSegment(polygon[i], p, polygon[next]);
            }
            count++;
        }
        i = next;
    } while (i != 0);

    return count % 2 == 1;
}

int main() {
    // 定义多边形的顶点
    std::vector<Point> polygon = {
        {5.39128, -2.01951}, {5.44154, -1.76794}, {5.48533, -1.51549},
        {5.52271, -1.26221}, {5.55373, -1.00814}, {5.57846, -0.753312},
        // 添加所有顶点...
        {-5.44154, -1.76794}, {-5.39128, -2.01951}
    };

    Point p = {1.0, 2.0};  // 替换为要测试的点

    if (isInsidePolygon(polygon, p)) {
        std::cout << "点在多边形内" << std::endl;
    } else {
        std::cout << "点在多边形外" << std::endl;
    }

    return 0;
}

解释

• onSegment：用于判断点 q 是否在点 p 和 r 之间。
• orientation：计算三点的方向，判断是顺时针、逆时针还是共线。
• doIntersect：判断两条线段是否相交。
• isInsidePolygon：使用射线法判断点 p 是否在多边形内，统计从 p 向右发出的射线与多边形边的交点数目，如果交点数为奇数则在内，为偶数则在外。

注意

• 此代码适用于任何多边形（包括凹多边形和自交多边形）。
• 程序中的 1e10 为一个较大的数值，用于模拟“无限远”。
• 多边形的最后一个点需和第一个点不重合，否则需在最后手动添加使之闭合。

这些函数共同实现了射线法，用于判断一个点是否位于多边形内。让我们逐一解释这些函数的功能。

1. onSegment：判断点是否在给定线段上

bool onSegment(Point p, Point q, Point r) {
    return q.x <= std::max(p.x, r.x) && q.x >= std::min(p.x, r.x) &&
           q.y <= std::max(p.y, r.y) && q.y >= std::min(p.y, r.y);
}

• 功能：判断点 q 是否在线段 p 和 r 上。
• 原理：如果 q 在线段 p 和 r 上，那么 q 的坐标值应在 p 和 r 的坐标范围之内。
• 用途：在判断射线和边相交时，如果射线穿过边的端点，则需要确认该点是否属于该线段。

2. orientation：计算三点的方向

int orientation(Point p, Point q, Point r) {
    double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0; // 共线
    return (val > 0) ? 1 : 2; // 顺时针或逆时针
}

• 功能：确定三个点 p、q 和 r 的方向关系。
• 返回值：
  • 0：三点共线。
  • 1：三点顺时针。
  • 2：三点逆时针。
• 原理：计算由三点形成的平行四边形的面积：
  • val = 0：面积为零，三点共线。
  • val > 0：面积正值，点 r 位于 p-q 的右侧，顺时针。
  • val < 0：面积负值，点 r 位于 p-q 的左侧，逆时针。
• 用途：在 doIntersect 函数中，用于判断两条线段的相交情况。

3. doIntersect：检查两条线段是否相交

bool doIntersect(Point p1, Point q1, Point p2, Point q2) {
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4) return true;

    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false;
}

• 功能：判断两条线段 p1q1 和 p2q2 是否相交。
• 原理：
  • 使用四个方向值 o1、o2、o3、o4 检查两条线段的相对位置。
  • 一般情况：若 p1q1 和 p2q2 的方向不同，则它们相交。
  • 特殊情况：若两线段共线，检查它们是否在对方线段上相交。
• 用途：在 isInsidePolygon 中，用于检测射线是否与多边形的边相交。

4. isInsidePolygon：判断点是否在多边形内

bool isInsidePolygon(const std::vector<Point>& polygon, Point p) {
    int n = polygon.size();
    if (n < 3) return false;

    Point extreme = {1e10, p.y};
    int count = 0, i = 0;

    do {
        int next = (i + 1) % n;
        if (doIntersect(polygon[i], polygon[next], p, extreme)) {
            if (orientation(polygon[i], p, polygon[next]) == 0) {
                return onSegment(polygon[i], p, polygon[next]);
            }
            count++;
        }
        i = next;
    } while (i != 0);

    return count % 2 == 1;
}

• 功能：判断给定的点 p 是否位于多边形 polygon 内部。
• 原理：
  1. 从点 p 向右创建一条射线 p -> extreme。
  2. 遍历多边形的所有边，并使用 doIntersect 检查射线是否与多边形的边相交。
  3. 如果射线和某条边相交，则增加交点计数 count。若射线穿过某边的端点，还要使用 onSegment 检查点是否在边上。
  4. 最终，根据交点数 count 的奇偶性确定点的位置：奇数表示在内部，偶数表示在外部。