在实现很多数学相关的功能的时候, 数学模型的选择尤为重要, 一个是在准确性上, 一个是在扩展性上.
比如最近我要计算一个射线跟一个线段的交点, 初中的时候就学过, 直线和直线外一点的交点怎样计算, 这里
直接上已经写完的两段代码.
简图
因为是计算机, 肯定是通过两点来确定直线方程了, 首先是用点斜式的计算方法( 原始方程 y = kx + b, 推导过程略 ):
/// <summary> /// 点斜式推理出的交点方程 /// </summary> /// <param name="ray"></param> /// <param name="p1"></param> /// <param name="p2"></param> /// <param name="point"></param> /// <returns></returns> [System.Obsolete("Incorrect", false)] public static bool IntersectRayAndLineSegment_XOZ_PointSlope(Ray ray, Vector3 p1, Vector3 p2, out Vector3 point) { var p3 = new Vector3(ray.origin.x, 0, ray.origin.z); float k1 = (p2.z - p1.z) / (p2.x - p1.x); float k2 = -1.0f / k1; float b1 = p1.z - (k1 * p1.x); float b2 = p3.z - (k2 * p3.x); float x = (b2 - b1) / (k1 - k2); float z = x * k1 + b1; point = new Vector3(x, 0, z); var rayDir = ray.direction; rayDir.y = 0; bool intersect = Vector3.Dot(point - p3, rayDir) > 0; if(intersect) { intersect = (x >= Mathf.Min(p1.x, p2.x) && x <= Mathf.Max(p1.x, p2.x)) && (z >= Mathf.Min(p1.z, p2.z) && z <= Mathf.Max(p1.z, p2.z)); } return intersect; }
然后是两点式的计算方法( 原始方程 (y-y1)/(x-x1) = (y-y2)/(x-x2), 推导过程略 ):
/// <summary> /// 两点式推出的交点方程 /// </summary> /// <param name="ray"></param> /// <param name="p1"></param> /// <param name="p2"></param> /// <param name="point"></param> /// <returns></returns> public static bool IntersectRayAndLineSegment_XOZ_TwoPoint(Ray ray, Vector3 p1, Vector3 p2, out Vector3 point) { point = Vector3.zero; Vector3 p3 = new Vector3(ray.origin.x, 0, ray.origin.z); Vector3 p4 = ray.GetPoint(1.0f); p4.y = 0; float a1, b1, c1; PointToLineEquation_2D_XOZ(p1, p2, out a1, out b1, out c1); float a2, b2, c2; PointToLineEquation_2D_XOZ(p3, p4, out a2, out b2, out c2); float D = a1 * b2 - a2 * b1; if(D == 0) { return false; } float D1 = -c1 * b2 + c2 * b1; float D2 = -c2 * a1 + a2 * c1; point = new Vector3(D1 / D, 0, D2 / D); var rayDir = ray.direction; rayDir.y = 0; bool intersect = Vector3.Dot(point - p3, rayDir) > 0; if(intersect) { intersect = (point.x >= Mathf.Min(p1.x, p2.x) && point.x <= Mathf.Max(p1.x, p2.x)) && (point.z >= Mathf.Min(p1.z, p2.z) && point.z <= Mathf.Max(p1.z, p2.z)); } return intersect; } public static void PointToLineEquation_2D_XOZ(Vector3 p1, Vector3 p2, out float a, out float b, out float c) { float x1 = p1.x; float y1 = p1.z; float x2 = p2.x; float y2 = p2.z; a = y2 - y1; b = x1 - x2; c = (y1 * x2) - (y2 * x1); }
在大部分情况下它们的结果是正确的, 可是在线段是平行于坐标轴的情况下, 点斜式的结果就不对了, 往回看计算过程:
var p3 = new Vector3(ray.origin.x, 0, ray.origin.z); float k1 = (p2.z - p1.z) / (p2.x - p1.x); float k2 = -1.0f / k1; float b1 = p1.z - (k1 * p1.x); float b2 = p3.z - (k2 * p3.x); float x = (b2 - b1) / (k1 - k2); float z = x * k1 + b1;
点斜式在刚开始就计算了斜率k, 然后k被作为了分母参与计算, 这样在平行于x轴的时候斜率就是0, 被除之后得到无穷大(或无穷小), 在平行y轴的时候( 两点的x相等 ), k直接就是无穷大(或无穷小).
所以点斜式在计算平行于坐标轴的情况就不行了. 点斜式的问题就在于过早进行了除法计算, 而且分母还可能为0, 这在使用计算机的系统里面天生就存在重大隐患.
然后是两点式, 它的过程是由两点式推算出一般方程的各个变量( 一般方程 ax + by + c = 0 ), 然后联立两个一般方程来进行求解, 它的稳定性就体现在这里:
a = y2 - y1; b = x1 - x2; c = (y1 * x2) - (y2 * x1);
它的初始计算完全不涉及除法, 第一步天生就是计算上稳定的.
然后是计算联立方程的方法, 这里直接用了二元一次线性方程组的求解:
float D = a1 * b2 - a2 * b1; if(D == 0) { return false; } float D1 = -c1 * b2 + c2 * b1; float D2 = -c2 * a1 + a2 * c1; point = new Vector3(D1 / D, 0, D2 / D);
使用行列式计算的好处是很容易判断出是否有解, D==0 时就是无解, 这也是计算稳定性的保证, 然后这里是只计算x, z平面的, 也就是2D的,
如果要计算3D的或更高阶的, 只需要把行列式和一般方程封装成任意元的多元方法即可, 例如一般方程为( ax + by + cz + d = 0 )甚至更高阶的( ax + by + cz + dw......+n = 0 ),
然后行列式求多元线性方程组的解就更简单了, 这就提供了很强大的扩展性, 不仅2维, 3维, 甚至N维都能提供解.
所以在做功能前仔细想好怎样做, 慎重选择数学模型是非常重要的. 虽然这些活看似初中生也能做, 大学生也能做, 差距还是一目了然的吧.
补充一下上面说过的多元线性方程组的解, 分成行列式和线性方程组:
public class Determinant { public int order { get; private set; } public float[,] matrix { get; private set; } private int m_index = 0; public Determinant(int order) { if(order < 2) { throw new System.Exception("order >= 2 !!"); } this.order = order; CreateMatrix(); } #region Main Funcs public void SetColumn(int column, params float[] values) { if(column >= 0 && column < order && values != null) { for(int i = 0, imax = Mathf.Min(order, values.Length); i < imax; i++) { matrix[i, column] = values[i]; } } } public void SetRow(int row, params float[] values) { if(row >= 0 && row < order && values != null) { for(int i = 0, imax = Mathf.Min(order, values.Length); i < imax; i++) { matrix[row, i] = values[i]; } } } public void SetRow(params float[] values) { SetRow(m_index, values); m_index++; } public Determinant Clone() { Determinant tag = new Determinant(this.order); System.Array.Copy(matrix, tag.matrix, matrix.Length); return tag; } public Determinant GetSubDeterminant(int row, int column) { Determinant tag = new Determinant(this.order - 1); for(int i = 0, tagRow = 0; i < order; i++) { if(i == row) { continue; } for(int j = 0, tagColumn = 0; j < order; j++) { if(j == column) { continue; } tag.matrix[tagRow, tagColumn] = this.matrix[i, j]; tagColumn++; } tagRow++; } return tag; } public float GetValue() { if(order == 2) { float value = matrix[0, 0] * matrix[1, 1] - matrix[0, 1] * matrix[1, 0]; return value; } else { float value = 0.0f; int row = order - 1; for(int column = 0; column < order; column++) { var aij = matrix[row, column] * ((row + column) % 2 > 0 ? -1 : 1); var subMatrix = GetSubDeterminant(row, column); var mij = subMatrix.GetValue(); float tempValue = (aij * mij); value += tempValue; } return value; } } #endregion #region Help Funcs private void CreateMatrix() { matrix = new float[order, order]; } #endregion } public class DeterminantEquation { public Determinant determinant { get; private set; } public int order { get { return determinant != null ? determinant.order : 0; } } public DeterminantEquation(int order) { determinant = new Determinant(order); } #region Main Funcs public float[] CaculateVariables(params float[] values) { var D = determinant.GetValue(); if(D == 0) { Debug.LogWarning("This Determinant has no Result !!"); return null; } float[] variables = new float[order]; for(int i = 0; i < order; i++) { var subDeterminant = determinant.Clone(); subDeterminant.SetColumn(i, values); var Di = subDeterminant.GetValue(); var variable = Di / D; variables[i] = variable; } return variables; } #endregion }
因为多元方程组的一般方程就是 NxN 的等边矩阵, 所以行列数量是一样的, 用二维数组表示. 各个解通过克拉默法则计算得出.
而行列式值的计算就通过按行展开, 降阶通过代数余子式计算. 这样就可以计算任意阶的方程组了.
那么两点式的计算代码改一改, 就能看出扩展性了:
/// <summary> /// 两点式推出的交点方程 /// </summary> /// <param name="ray"></param> /// <param name="p1"></param> /// <param name="p2"></param> /// <param name="point"></param> /// <returns></returns> public static bool IntersectRayAndLineSegment_XOZ_TwoPoint(Ray ray, Vector3 p1, Vector3 p2, out Vector3 point) { point = Vector3.zero; Vector3 p3 = new Vector3(ray.origin.x, 0, ray.origin.z); Vector3 p4 = ray.GetPoint(1.0f); p4.y = 0; float a1, b1, c1; PointToLineEquation_2D_XOZ(p1, p2, out a1, out b1, out c1); float a2, b2, c2; PointToLineEquation_2D_XOZ(p3, p4, out a2, out b2, out c2); //float D = a1 * b2 - a2 * b1; //if(D == 0) //{ // return false; //} //float D1 = -c1 * b2 + c2 * b1; //float D2 = -c2 * a1 + a2 * c1; //point = new Vector3(D1 / D, 0, D2 / D); DeterminantEquation determinantEquation = new DeterminantEquation(2); determinantEquation.determinant.SetRow(a1, b1); determinantEquation.determinant.SetRow(a2, b2); var variables = determinantEquation.CaculateVariables(-c1, -c2); if(variables == null) { return false; } point = new Vector3(variables[0], 0, variables[1]); var rayDir = ray.direction; rayDir.y = 0; bool intersect = Vector3.Dot(point - p3, rayDir) > 0; if(intersect) { intersect = (point.x >= Mathf.Min(p1.x, p2.x) && point.x <= Mathf.Max(p1.x, p2.x)) && (point.z >= Mathf.Min(p1.z, p2.z) && point.z <= Mathf.Max(p1.z, p2.z)); } return intersect; } /// <summary> /// 一般方程变量计算 /// </summary> /// <param name="p1"></param> /// <param name="p2"></param> /// <param name="a"></param> /// <param name="b"></param> /// <param name="c"></param> public static void PointToLineEquation_2D_XOZ(Vector3 p1, Vector3 p2, out float a, out float b, out float c) { float x1 = p1.x; float y1 = p1.z; float x2 = p2.x; float y2 = p2.z; a = y2 - y1; b = x1 - x2; c = (y1 * x2) - (y2 * x1); }
把行列式的类( Determinant ) 改成结构体应该在效率上会高效一些.
PS: 数学模型这里有两个, 第一个是通过各个点获取联立方程, 第二个是怎样解联立方程
点斜式获取的是点斜式方程
y = k1*x + b1
y = k2*x + b2
两点式获取的是标准方程
a1*x + b1*y + c1 = 0
a2*x + b2*y + c2 = 0
这两个方程的计算差别上面已经说了.
解联立方程的方法也用了两种, 点斜式用的是一般推论, 就是普通的求解过程, 两点式使用了线性代数(注意点斜式的联立方程也能用线性方程解的, 只是作为对比),
可以预想到如果联立方程的维数增加到很多的时候一般求解过程的难度会大大增加,
比如
3元方程 -> 6个变量
4元方程 -> 24个变量
5元方程 -> 120个变量... 所以初中生最多就教到3元方程
而 DeterminantEquation 这个类就能很简单的计算出多元方程式的解. 所以在扩展性上胜出.
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
