c++ 线与多边形关系算法

线与多边形的关系算法主要有以下几种：

1. 射线法：对于一个多边形，从线段的起点开始画一条射线，如果这条射线与多边形的边相交的次数为奇数，则线段与多边形有交点，否则线段与多边形没有交点。

2. 分割法：首先将多边形分割成若干个三角形，然后判断线段与每个三角形的关系，如果与任意一个三角形有交点，则线段与多边形有交点。

3. SAT法：利用分离轴定理，判断线段是否与多边形相交。具体方法是首先求出多边形的所有边的法向量，然后将线段的两个端点分别投影到法向量上，如果两个投影之间的距离大于多边形在该法向量上的投影距离之和，则线段与多边形没有交点。

4. Minkowski差法：将多边形沿着线段的方向缩小一定距离，得到一个新的多边形，然后判断原多边形和新多边形是否相交。如果相交，则线段与多边形有交点。