几何相关计算

一、判断两个矩形是否相交

二、判断两条线段是否相交

三、判断点是否在多边形内

四、垂足计算

五、贝塞尔曲线

六、坐标系

一、判断两个矩形是否相交

当矩形1的最大值比矩形2的最小值都小，那矩形1和矩形2一定不相交，其他同理。

struct Point {
	double x;
	double y;
};
struct Rec {
	Point min;
	Point max;
};
bool is_rec_overlap(const Rec& r1, const Rec& r2) {
	if(r1.max.x < r2.min.x
		|| r1.max.y < r2.min.y
		|| r2.max.x < r1.min.x
		|| r2.max.y < r1.min.y) {
		return false;
	} else {
		return true;
	}	
}

二、判断两条线段是否相交

排斥实验+跨立实验

#include<iostream>
#include<vector>

struct Point {
	double x;
	double y;
	Point(double _x, double _y) : x(_x),y(_y) {}
};

struct Edge {
    Point s;
    Point e;
    Edge(const Point& _s, const Point& _e) : s(_s),e(_e) {}
};

// 判断点在直线的左右侧：计算叉积(p_e_p_s) × (p-p_s)
// 若返回结果>0，则点p在线段ps_p_e的左侧；
// 若返回结果<0，则点p在线段ps_p_e的右侧；
// 若返回结果=0，则点p与ps、p_e共线；
double is_left(const Point& p, const Point& p_s, const Point& p_e) {
    return (p_e.x - p_s.x)*(p.y - p_s.y) - (p_e.y - p_s.y)*(p.x - p_s.x);
}

bool edges_intersect(const Edge& edge1, const Edge& edge2) {
    // 排斥实验：最小外包框不想交，edges不可能相交
    if(std::min(edge1.s.x, edge1.e.x) > std::max(edge2.s.x, edge2.e.x)
        || std::min(edge1.s.y, edge1.e.y) > std::max(edge2.s.y, edge2.e.y)
        || std::min(edge2.s.x, edge2.e.x) > std::max(edge1.s.x, edge1.e.x)
        || std::min(edge2.s.y, edge2.e.y) > std::max(edge1.s.y, edge1.e.y)) {
        return false;
    }

    // 跨立实验：edge1的两个端点在edge2的两侧，且edge2的两个端点在edge1的两侧，则edges相交。
    if(is_left(edge1.s, edge2.s, edge2.e) * is_left(edge1.e, edge2.s, edge2.e) <= 0
        && is_left(edge2.s, edge1.s, edge1.e) * is_left(edge2.e, edge1.s, edge1.e) <= 0) {
        return true;
    }

    return false;
}

参考：https://www.cnblogs.com/TangMoon/p/7611115.html

三、判断点是否在多边形内

简单版

// 判断点在多边形内部还是外部（射线法）：
// 从待判断的点出发，向某一方向（这里假设水平向右）发射一条射线;
// 遍历多边形的每一条边，检查射线是否相交
// 统计交点数量，若为偶数，则点在外部，否则，点在内部。
// 这里交点的判断简化为：edge的两个端点y值一个大于pt.y，一个小于pt.y，同时统计pt所在水平直线与edge交点的x值小于pt.x的个数。
bool is_in_polygon(const Point& pt, const std::vector<Point>& polygon) {
	int count = polygon.size();
	if(count < 3) {
		return false;
	}

    int intersecting_count = 0;
	for(int i = 0; i < polygon.size(); i++) {
		Point edge_s = polygon.at(i);
		Point edge_e = polygon.at((i+1)%count);
        if((pt.y <= edge_s.y && pt.y > edge_e.y 
            || pt.y <= edge_e.y && pt.y > edge_s.y)) {
            // 外层的if保证了edge_e.y != edge_s.y
            double pt_on_edge_x = (pt.y - edge_s.y) * (edge_e.x - edge_s.x) / (edge_e.y - edge_s.y) + edge_s.x;
            if(pt_on_edge_x < pt.x) {
                intersecting_count++;
            }
        }
	}
    return intersecting_count % 2 == 1;
}

参考：https://www.cnblogs.com/tgycoder/p/4901600.html

四、垂足计算

double cal_distance_square(const Point& pt1, const Point& pt2) {
    return (pt2.x - pt1.x) * (pt2.x - pt1.x) + (pt2.y - pt1.y) * (pt2.y - pt1.y);
}

// 计算(p_e-p_s)和(p-p_s)的点积
double dot_product(const Point& p, const Point& p_s, const Point& p_e) {
    return (p_e.x - p_s.x)*(p.x - p_s.x) + (p_e.y - p_s.y)*(p.y - p_s.y);
}

// 判断点pt到edge的投影点project_pt与edge的关系
/*  r = AP dot AB / ||AB||^2
    r=0 : project_pt = A
    r=1 : project_pt = B
    r<0 : project_pt is on backward extension of AB
    r>1 : project_pt is on forward extension of AB
   0<r<1: project_pt is on AB
*/
double relation(const Point& pt, const Edge& edge) {
    double len_square = cal_distance_square(edge.s, edge.e);
    // 特殊情况处理
    if(len_square < EP) {
        if(cal_distance_square(pt, edge.s) < EP) {
            return 0;
        } else {
            return -1; // 随便给个<0或>1的值
        }
    }
    return dot_product(pt, edge.s, edge.e) / len_square;
}

// 计算点pt到线段edge投影点.
// 若投影点在线段上，则project_pt赋值投影点，返回true
// 若投影点不在线段上，则project_pt赋值最近点，返回false。
bool calc_project_pt(const Point& pt, const Edge& edge, Point& project_pt) {
    double r = relation(pt, edge);
    if(r < 0) {
        project_pt = edge.s;
        return false;
    } else if (r > 1) {
        project_pt = edge.e;
        return false;
    }
    project_pt.x = edge.s.x + r * (edge.e.x - edge.s.x);
    project_pt.y = edge.s.y + r * (edge.e.y - edge.s.y);
    return true;
}