[作业记录]——GIS算法的几何基础

:)

#include <cstdio>
#include <iostream>
#include <cfloat>
#include <algorithm>

using namespace std;

//定义点结构
typedef struct point
{
    double x;//点x坐标
    double y;//点y坐标
}POINT;

//定义线段结构
typedef struct line
{
    POINT startP;//线段起点
    POINT endP;//线段终点
}LINE;

//定义多边形结构
typedef struct polygon
{
    LINE l[100];
    int length;
}POLYGON;

//向量叉积函数
double cross_product(POINT vector1,POINT vector2)
{
    return vector1.x * vector2.y - vector2.x * vector1.y;
}

//点相等判断函数
bool equal_point(POINT a,POINT b)
{
    return(a.x == b.x && a.y == b.y);
}

//点在线段上判断函数
bool point_on_the_line(POINT a,LINE b)
{
    double maxx = max(b.startP.x,b.endP.x),minx = min(b.startP.x,b.endP.x),maxy = max(b.startP.y,b.endP.y),miny = min(b.startP.y,b.endP.y);
    if(a.x > maxx || a.x < minx || a.y > maxy || a.y < miny)return false;
    //(Q-P1)x(P2-P1)=0
    POINT vector1,vector2;
    vector1.x = a.x - b.startP.x, vector1.y = a.y - b.startP.y;
    vector2.x = b.endP.x - b.startP.x, vector2.y = b.endP.y - b.startP.y;
    if(cross_product(vector1,vector2))return false;
    return true;
}

//判断线段拐向
void turn_of_line(LINE frontL,LINE backL,int &turnL)
{

    //首线段frontL 尾线段backL
    //拐向状态turnL(-2为线段不相接 -1为左拐 0为共线 1为右拐)
    if(!equal_point(frontL.endP,backL.startP))
        turnL = -2;
    else{
        POINT p0 = frontL.startP,p1 = frontL.endP,p2 = backL.endP;
        POINT vector1,vector2;
        vector1.x = p2.x - p0.x,vector1.y = p2.y - p0.y;
        vector2.x = p1.x - p0.x,vector2.y = p1.y - p0.y;
        double dir = cross_product(vector1,vector2);
        if(dir < 0)turnL = -1;
        else if(dir > 0)turnL = 1;
        else turnL = 0;
    }
    return;
}

//线段相交函数
bool intersecting_lines(LINE a,LINE b)
{
    //快速排斥
    if(!(min(a.startP.x,a.endP.x) <= max(b.startP.x,b.endP.x) &&
       min(b.startP.x,b.endP.x) <= max(a.startP.x,a.endP.x) &&
       min(a.startP.y,a.endP.y) <= max(b.startP.y,b.endP.y) &&
       min(b.startP.y,b.endP.y) <= max(a.startP.y,a.endP.y)))return false;
    //(P1-Q1)x(Q2-Q1)*(Q2-Q1)x(P2-Q1)>=0
    POINT vector1,vector2,vector3;
    vector1.x = a.startP.x - b.startP.x,vector1.y = a.startP.y - b.startP.y;
    vector2.x = b.endP.x - b.startP.x,vector2.y = b.endP.y - b.startP.y;
    vector3.x = a.endP.x - b.startP.x,vector3.y = a.endP.y - b.startP.y;
    if(cross_product(vector1,vector2) * cross_product(vector2,vector3) < 0)return false;
    return true;
}

//点在多边形中函数
bool point_in_polygon(POINT p,POLYGON a)
{
    int c = 0;
    POINT p2;
    p2.x = DBL_MAX, p2.y = p.y;
    for(int i = 0; i<a.length ; ++i){
        if(point_on_the_line(p,a.l[i]))return true;
        POINT p0, p1;
        p0.x = a.l[i].startP.x,p0.y = a.l[i].startP.y;
        p1.x = a.l[i].endP.x,p1.y = a.l[i].endP.y;
        if(p0.y == p1.y)continue;
        LINE L;
        L.startP.x = p.x, L.startP.y = p.y, L.endP.x = p2.x, L.endP.y = p2.y;
        if(point_on_the_line(p0,L) || point_on_the_line(p1,L)){
            POINT mp;
            if(p0.y > p1.y)mp.x = p0.x, mp.y = p0.y;else mp.x = p1.x, mp.y = p1.y;
            if(point_on_the_line(mp,L))++c;
        }
        else if(intersecting_lines(L,a.l[i]))++c;
    }
    if(c%2)return true;
    return false;
}

bool cmp(POINT a,POINT b)
{
    if(a.x<b.x)return true;
    else if(a.x>b.x)return false;
    else return (a.y<b.y);
}

//线段在多边形中函数
bool line_in_polygon(LINE l,POLYGON a)
{
    if(!(point_in_polygon(l.startP,a) && point_in_polygon(l.endP,a)))return false;
    POINT pointset[200];
    int c = 0;
    for(int i = 0;i<a.length; ++i){
        if(point_on_the_line(l.startP,a.l[i]))pointset[c++] = l.startP;
        else if(point_on_the_line(l.endP,a.l[i]))pointset[c++] = l.endP;
        else if(point_on_the_line(a.l[i].startP,l))pointset[c++] = a.l[i].startP;
        else if(point_on_the_line(a.l[i].endP,l))pointset[c++] = a.l[i].endP;
        else if(intersecting_lines(l,a.l[i]))return false;
    }
    sort(pointset,pointset+c,cmp);
    for(int i = 0; i<c-1; ++i){
        POINT midpoint;
        midpoint.x = (pointset[i].x + pointset[i+1].x)/2;
        midpoint.y = (pointset[i].y + pointset[i+1].y)/2;
        if(!point_in_polygon(midpoint,a))return false;
    }
    return true;
}

void read_polygon(POLYGON &s)
{
    int n;
    cout<<"请输入多边形边数（100以内）：";
    cin>>n;
    s.length = n;
    cout<<"请输入多边形点坐标（依次）："<<endl;
    double fx,fy,tx,ty,x,y;
    cin>>fx>>fy;
    tx=fx,ty=fy;
    for(int i = 0; i < n-1; ++i){
        cin>>x>>y;
        s.l[i].startP.x = tx,s.l[i].startP.y = ty;
        s.l[i].endP.x = x,s.l[i].endP.y = y;
        tx = x,ty = y;
    }
    s.l[n-1].startP.x = x,s.l[n-1].startP.y = y;
    s.l[n-1].endP.x = fx,s.l[n-1].endP.y = fy;
    return;
}

void read_point(POINT &p)
{
    cout<<"请输入需判断的点坐标：";
    cin>>p.x>>p.y;
    return;
}

void read_line(LINE &l)
{
    cout<<"分别输入线段起始点"<<endl;
    read_point(l.startP);
    read_point(l.endP);
    return;
}

int main()
{
    /*
    POINT p0,p1,p2,p3;
    cout<<"请输入首线段起点:(x y)"<<endl;
    cin>>p0.x>>p0.y;
    cout<<"请输入首线段终点:(x y)"<<endl;
    cin>>p1.x>>p1.y;
    cout<<"请输入尾线段起点:(x y)"<<endl;
    cin>>p2.x>>p2.y;
    cout<<"请输入尾线段终点:(x y)"<<endl;
    cin>>p3.x>>p3.y;
    LINE l1,l2;
    l1.startP = p0,l1.endP = p1;
    l2.startP = p2,l2.endP = p3;
    int turnL = 0;
    turn_of_line(l1,l2,turnL);
    switch(turnL){
        case -2:{cout<<"输入错误！两线段不相接！"<<endl;break;}
        case -1:{cout<<"拐向为左"<<endl;break;}
        case 0:{cout<<"两线段共线！"<<endl;break;}
        case 1:{cout<<"拐向为右"<<endl;break;}
    }
    */
    /*
    POINT p;
    POLYGON s;
    read_polygon(s);
    read_point(p);
    if(point_in_polygon(p,s))cout<<"点在多边形内";
    else cout<<"点不在多边形内";
    */
    /*POINT p;
    POLYGON s;
    read_polygon(s);
    read_point(p);
    if(point_in_polygon(p,s))cout<<"点在多边形内";
    else cout<<"点不在多边形内";
    */
    return 0;
}