这是一些好算法
一、向量叉乘求三维空间中两直线(或线段)的交点
2D空间的直线相交
在二维空间中，利用两个直线方程y = kx + b我们可以直接计算出交点，但是这种方法麻烦了些，并且套用到三维空间用公式就更麻烦了，接下来介绍的是如何利用向量叉乘求出直线交点。并且由于利用叉乘最后可以的到一个比例值，这个值的大小还可以判断四个点所得到的两个线段是延长线相交还是线段相交。
向量叉乘
三维空间中，两个向量叉乘得到的是一个垂直于两向量组成的平面的向量，方向可利用右手螺旋法则获取，这一点百度谷歌一搜一大把，不细说了大小可由下面的公式得到，注意和点乘的区别。
向量叉乘的几何意义是得到一个三角形的有向面积，如下图所示，向量OA和OB叉乘的到的向量大小的二分之一就等于三角形OAB的面积
有了以上基础，我们就可以开始计算三维空间中的直线交点了
三维空间中的两直线交点
下图CE和AB是平行线且长度相等。
首先确定两条直线是否平行，利用向量点乘结果是否等于0来判断，等于0垂直，等于1则平行。
接着我们需要确定两条直线在一个平面内，否则无论如何也无法相交，这个用向量叉乘来判断，即判断向量CA和向量AB叉乘得到的向量是否垂直于向量CD。
然后明确一个目标，在四个点ABCD已知的情况下，求交点O我们只需要知道CO/CD就可以了。通过观察发现，三角形ACD的面积比三角形CDE的面积等于线段CO和CD的比值，我们来证明一下，步骤很简单。
证明 ：S三角形ACD/S三角形CDE = AO比AB
三角形AFO和三角形EGC相似
AF / EG = AO/CE；
CE = AB 所以等式成立
问题转化成要计算两个三角形的面积，那么我们只需要 向量AB，CD和CA就可以了，开始写代码
代码实现
利用叉乘求交点少了很多if else的判断，并且可以做到二维和三维的通用，传递参数的时候只要将所有点和向量y轴的值设为0就可以当作二维来使用了。
利用代码中得到的比例值num2的大小还可以判断是延长线相交还是线段相交
注意下述方法所传入的参数是两个点和两个方向，可以改写成传入四个点。
FVector UBFL_Utility::TransformLine(const FVector& A, const FVector& B, float MoveLength, FVector& A_Copy)
{
FVector AB = B-A;
FVector ScaleAB = UKismetMathLibrary::GetRightVector(UKismetMathLibrary::MakeRotFromX(AB));
FVector A_Alias = A + ScaleAB * MoveLength;
FVector B_Alias = B + ScaleAB * MoveLength;
A_Copy = A_Alias;
return B_Alias - A_Alias;
}
//计算每两条相邻的收缩后的边的交点，合并为组，就是收缩后的多边形，无法处理临界情况，例如ScaleLength过长导致顶点减少或者被分割为两个区域
TArray<FVector> UBFL_Utility::ShrinkPolygon(const TArray<FVector>& OldPointsLocation, float ScaleLength)
{
int PointsNum = OldPointsLocation.Num();
TArray<FVector> NewPoints;
for(int i = 0;i<PointsNum;++i)
{
//三维空间中的两直线交点
//AB
FVector A_Alias;
FVector AB_Alias = TransformLine(OldPointsLocation[i], OldPointsLocation[(i+1)%PointsNum], ScaleLength, A_Alias);
//CD
FVector C_Alias;
FVector CD_Alias = TransformLine(OldPointsLocation[(i+1)%PointsNum], OldPointsLocation[(i+2)%PointsNum], ScaleLength, C_Alias);
//CA
FVector CA = A_Alias-C_Alias;
FVector E = C_Alias+AB_Alias;
FVector CE = E - C_Alias;
//S三角形ACD/S三角形CDE = AO比AB, Ratio>1在AB_Alias延长线上
float Ratio = CD_Alias.Cross(CA).Length()/CE.Cross(CD_Alias).Length();
//交点
FVector O = A_Alias+AB_Alias.GetSafeNormal()*Ratio*AB_Alias.Length();
NewPoints.Add(O);
}
return NewPoints;
}
二、收缩多边形
出来上面缩边求交点外，还有一个算法可以，也无法处理临界情况
TArray<FVector> UBFL_Utility::ScaleArea(const TArray<FVector>& OldPointsLocation, float ScaleLength)
{
int PointsNum = OldPointsLocation.Num();
//直接对点进行偏移，沿该点对角线偏移，同时判断是否为凹点，如果为凹点，则对角线取相反方向
for(i = 0;i<PointsNum;++i)
{
//该点向两个相邻点的方向向量
FVector V1 = OldPointsLocation[(PointsNum+i-1)%PointsNum] - OldPointsLocation[i];
FVector V2 = OldPointsLocation[(i+1)%PointsNum] - OldPointsLocation[i];
V1.Normalize();
V2.Normalize();
//顺时针，而V1是逆时针，这个结果会影响凹点判断
FVector V1_Alias = OldPointsLocation[i] - OldPointsLocation[(PointsNum+i-1)%PointsNum];
//对角线
FVector V3 = V1+V2;
V3.Normalize();
//二维叉乘
float Res_temp = V1_Alias.X*V2.Y - V2.X*V1_Alias.Y;
//凹点取反
if(Res_temp<0)
{
V3 *= -1;
}
//下图
NewPointsLocation[i] = OldPointsLocation[i] + V3 * ScaleLength/UKismetMathLibrary::Sin(UKismetMathLibrary::Acos(V1.Dot(V2))/2.f);;
}
return NewPointsLocation;
}
注：当然也有完美的算法参考：An algorithm for inflating/deflating (offsetting, buffering) polygons
三、判断点在多边形内
算法
判断一个点是否在多边形内，我们可以从该点引出一条水平射线（任意射线都可，但水平便于计算），观察射线与多变形的交点个数，如果交点个数为奇数，则该点在多边形内，如果为 偶数 则在多边形外。
如图 点在多边形内，从该点做一条水平射线，与多边形交点个数为2*n+1 为奇数，同理若点在多变形外为偶数。
如何判断水平射线与多变形的边有交点呢？
显然，如果某条边是水平的，那么肯定没有交点
if (p1.y == p2.y) continue;
如果点p的纵坐标比多边形某边的纵坐标都小或都大，那么他们的交点一定在延长线上，如图所示
if (p.y < min(p1.y, p2.y))
continue;
if (p.y >= max(p1.y, p2.y))
continue;
接下来我们考虑一般情况。要想判断有没有交点，我们只需要将多边形某边所在直线的方程求出，将p点的纵坐标y0带入，即可求得交点横坐标x，将x与x0比较，如果下x0<x,该点在多边形内反之在多边形外。 公式为：
x=(y0−p1.y)∗(p2.x−p1.x)/(p2.y−p1.y)+x0
完整代码
struct Point
{
double x, y;
};
bool IsInPolygon(Point p,Point *ptPolygon,int ncount)
{
int ncross = 0;
for (int i = 0; i < ncount; i++)
{
Point p1 = ptPolygon[i];
Point p2 = ptPolygon[(i + 1) % ncount]; //相邻两点p1,p2
if (p1.y == p2.y)
continue;
//在同一水平线上的点，只会计算位于水平线上方的线段
if (p.y < min(p1.y, p2.y))
continue;
if (p.y >= max(p1.y, p2.y))//下方线段跳过
continue;
double x = (p.y - p1.y)*(p2.x - p1.x) / (p2.y - p1.y) + p1.x;
if (x > p.x)
ncross++; //只统计单边交点
}
return(ncross % 2 == 1);
}