点是否在多边形内问题

wenge · 2024-01-31 23:01:44 · 个人记录

算法

1.光线投射算法

太麻烦，没用。

2.回转数算法

如果一个点在多边形外，把这个点做为顶点，向多边形所有点连射线，然后逆时针统计这个点和多边形上 n 对相邻的点构成的 n 个有向角之和，如果和为0说明在多边形外。

口胡：对于不自交的多边形，在多边形里面的话，这个角度和看起来会是 2\pi。

剩下的情况需要特判，判断两点是否是同一点很简单，判断点是否在线段上只需要判断两向量是否为0或反向就行了。

3.面积法

把这个点和多边形所有点连接线段，计算这个点和多边形上 n 对相邻的点构成的 n 个三角形的（无向）面积之和，看是否和多边形面积相等。如果在多边形外，这个面积之和会大于多边形的面积。

只适用于凸多边形。

题目

这是三角形的情况，P1355

注意对点在边界上情况的特判，atan2不稳定

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const double pi=acos(-1.0);
#define N 400005
ll n,m;
ll _eq(double x,double y){
    return abs(x-y)<1e-9;
}
struct Point{
    double x,y;
    Point operator -(Point rhs){
        return {x-rhs.x,y-rhs.y};
    }
    bool operator ==(Point rhs){
        return _eq(x,rhs.x)&&_eq(y,rhs.y);
    }
};
double _cross(Point A,Point B){
    return A.x*B.y-A.y*B.x;
}
double _dot(Point A,Point B){
    return A.x*B.x+A.y*B.y;
}
double _abs(Point A){
    return sqrt(_dot(A,A));
}
double _angle(Point A,Point O,Point B){
    Point X=A-O,Y=B-O;
    //cout<<X.x<<" "<<X.y<<" "<<Y.x<<" "<<Y.y<<"\n";
    //cout<<_abs(X)<<_abs(Y);
    return atan2(_cross(X,Y),_dot(X,Y));
}
int solve(){
    Point A,B,C,O;
    char c;
    cin>>c>>A.x>>c>>A.y>>c;
    cin>>c>>B.x>>c>>B.y>>c;
    cin>>c>>C.x>>c>>C.y>>c;
    cin>>c>>O.x>>c>>O.y>>c;
    if(O==A||O==B||O==C)return 4;
    if(_eq(abs(_angle(A,O,B)),pi)||_eq(abs(_angle(B,O,C)),pi)||_eq(abs(_angle(C,O,A)),pi))return 3;
    double t=_angle(A,O,B)+_angle(B,O,C)+_angle(C,O,A);
    if(_eq(t,0))return 2;
    return 1;
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    cout<<solve();
    //cout<<_angle({1,1},{1,2},{3,1});
    return 0;
}