计算几何之点的内包

在计算几何中，判断点是否内包于多边形之中，就是点的内包问题。

解决的思路就是，对于给定点p，作一条沿x轴正方向的射线，然后计算这条射线与多边形的边相交的次数。

首先判断点p是否在边上，如果在边上的话就直接return

如果相交的次数是奇数，那么它就是内包的。否则，点处于多边形的外部。

具体求相交次数的方法就是

遍历多边形上相邻的两点g_i g_i+1 ,设向量a = g_i – p, b = g_i+1– p

如果a的y坐标大于b的y坐标，那么就交换a、b

这时，如果a、b的外积为正，且a、b的y坐标一负一正，那么射线与线段g_ig_i+1相交。

题目：CGL_3_C

AC代码：

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

const double EPS = (1E-8);

class Point
{
public:
    double x, y;
    Point()
    {
    }
    Point(double x, double y)
    {
        (*this).x = x;
        (*this).y = y;
    }

    double operator^(const Point &p) const //叉乘
    {
        return x * p.y - y * p.x;
    }

    double operator*(const Point &p) const //点乘
    {
        return x * p.x + y * p.y;
    }

    Point operator*(const double &d) const
    {
        return Point(x * d, y * d);
    }

    Point operator/(const double &d) const
    {
        return Point(x / d, y / d);
    }

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

    Point operator+(const Point &p) const
    {
        return Point(x + p.x, y + p.y);
    }

    double sqr()
    {
        return x * x + y * y;
    }
    double abs()
    {
        return sqrt(sqr());
    }

    double distance(const Point &p)
    {
        return fabs((*this - p).abs());
    }

    void print()
    {

        printf("%.10lf %.10lf\n", x, y);
    }

    void read()
    {
        cin >> x >> y;
    }
};

class Line
{
public:
    Point p1, p2;
    Line();
    Line(Point p1, Point p2)
    {
        (*this).p1 = p1;
        (*this).p2 = p2;
    }
};

Point pp[MAXN];
int n;
int contains(Point p) //内包-》2，在边上-》1，在外部-》0
{
    int js=0;
    for (int i = 0; i < n; ++i)
    {
        Point a = pp[i] - p;
        Point b = pp[(i + 1) % n] - p;

        if (fabs((a ^ b)) < EPS && a * b < EPS)
            return 1; //在边上

        if (a.y > b.y)
            swap(a, b);

        if ((a ^ b) > EPS && a.y < EPS && b.y > EPS)
            js++;
    }

    return (js%2?2:0);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        pp[i].read();
    }

    int q;
    cin >> q;

    Point tmp;
    while (q--)
    {
        tmp.read();
        cout<<contains(tmp)<<endl;
    }
}

转载请注明来源：https://www.longjin666.top/?p=815

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~