精华内容
下载资源
问答
  • 平面上N个,没确定一条直线,求出斜率最大那条直线所通过的两(斜率不存在情况不考虑)。 先把N个按x排序。 斜率k最大值为max(斜率(point[i],point[i+1])) 1 <=i < n-1。 ...

    平面上N个点,没两个点都确定一条直线,求出斜率最大的那条直线所通过的两个点(斜率不存在的情况不考虑)。

    先把N个点按x排序。
    斜率k最大值为max(斜率(point[i],point[i+1])) 1 <=i < n-1。
    复杂度Nlog(N)。

    下面的例子是求斜率绝对值最大的直线,正常情况下把代码中的绝对值去掉就好了

    #include <bits/stdc++.h>
    #define ll long long
    #define pb push_back
    #define inf 0x3f3f3f3f
    #define pll pair<ll,ll>
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    #define rep1(i,a,b) for(int i=a;i>=b;i--)
    #define rson rt<<1|1,m+1,r
    #define lson rt<<1,l,m
    using namespace std;
    const int N=1e5+100;
    int arr[N],n,pp;
    double mx;
    struct node
    {
      double x,y;
      friend bool operator <(node a,node b)
      {
          return a.x<b.x||a.x==b.x&&a.y<b.y;
      }
    }points[N];
    int GetMaxSlope()
    {
        double fCurSlope = 0;
        double fMaxSlope = 0;
        for (int k=2;k<=n;k++)
        {
            double a=abs(points[k-1].x - points[k].x);
            fCurSlope = abs(points[k-1].y - points[k].y) / a;
            if (fMaxSlope < fCurSlope)
            {
                fMaxSlope = fCurSlope;
            }
        }
        mx=fMaxSlope;
        return 0;
    }
    int main()
    {
        #ifdef LOCAL_DEFINE
            freopen("D:\\rush.txt","r",stdin);
        #endif
        //ios::sync_with_stdio(false),cin.tie(0);
        int t;
        cin>>t;
        while(t--)
        {
            cin>>n;
            pp=0;
            rep(i,1,n)
            {
                scanf("%lf%lf",&points[i].x,&points[i].y);
            }
            sort(points+1,points+1+n);
            rep(i,1,n-1)
            {
                if(points[i].x==points[i+1].x)
                {
                    //cout<<-1<<endl;
                    pp=1;
                    break;
                }
            }
            if(pp)
                cout<<-1<<endl;
            else
            {
                GetMaxSlope();
                cout<<fixed<<setprecision(8)<<mx<<endl;
            }
        }
    }
    
    展开全文
  • 平面上N个,没确定一条直线,求出斜率最大那条直线所通过的两(斜率不存在情况不考虑)。 先把N个按x排序。 斜率k最大值为max(斜率(point[i],point[i+1])) 1 <=i < n-1。 复杂度Nlog(N...

    平面上N个点,没两个点都确定一条直线,求出斜率最大的那条直线所通过的两个点(斜率不存在的情况不考虑)。

    先把N个点按x排序。
    斜率k最大值为max(斜率(point[i],point[i+1])) 1 <=i < n-1。
    复杂度Nlog(N)。

    下面的例子是求斜率绝对值最大的直线,正常情况下把代码中的绝对值去掉就好了

    #include <bits/stdc++.h>
    #define ll long long
    #define pb push_back
    #define inf 0x3f3f3f3f
    #define pll pair<ll,ll>
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    #define rep1(i,a,b) for(int i=a;i>=b;i--)
    #define rson rt<<1|1,m+1,r
    #define lson rt<<1,l,m
    using namespace std;
    const int N=1e5+100;
    int arr[N],n,pp;
    double mx;
    struct node
    {
      double x,y;
      friend bool operator <(node a,node b)
      {
          return a.x<b.x||a.x==b.x&&a.y<b.y;
      }
    }points[N];
    int GetMaxSlope()
    {
        double fCurSlope = 0;
        double fMaxSlope = 0;
        for (int k=2;k<=n;k++)
        {
            double a=abs(points[k-1].x - points[k].x);
            fCurSlope = abs(points[k-1].y - points[k].y) / a;
            if (fMaxSlope < fCurSlope)
            {
                fMaxSlope = fCurSlope;
            }
        }
        mx=fMaxSlope;
        return 0;
    }
    int main()
    {
        #ifdef LOCAL_DEFINE
            freopen("D:\\rush.txt","r",stdin);
        #endif
        //ios::sync_with_stdio(false),cin.tie(0);
        int t;
        cin>>t;
        while(t--)
        {
            cin>>n;
            pp=0;
            rep(i,1,n)
            {
                scanf("%lf%lf",&points[i].x,&points[i].y);
            }
            sort(points+1,points+1+n);
            rep(i,1,n-1)
            {
                if(points[i].x==points[i+1].x)
                {
                    //cout<<-1<<endl;
                    pp=1;
                    break;
                }
            }
            if(pp)
                cout<<-1<<endl;
            else
            {
                GetMaxSlope();
                cout<<fixed<<setprecision(8)<<mx<<endl;
            }
        }
    }
    

    转载于:https://www.cnblogs.com/ffgcc/p/10546397.html

    展开全文
  • 对于2,直线在Matlab里面是点确定,因此交点如果是一段线(无穷个点)的情况,可能只是显示端点为交点; 对于3,很简单的例子,参数方程 x=cos,y=sin 在数学分析(即连续空间)层面上是个圆,但是如果你在...
  • 时间点:(2019.06.17)  在实现很多数学相关功能时候, 数学模型选择尤为重要, 一个是在准确性上, 一个是在... 因为是计算机, 肯定是通过两点确定直线方程了, 首先是用点斜式计算方法( 原始方程 y = kx +...

    时间点:(2019.06.17)

      在实现很多数学相关的功能的时候, 数学模型的选择尤为重要, 一个是在准确性上, 一个是在扩展性上.

    比如最近我要计算一个射线跟一个线段的交点, 初中的时候就学过, 直线和直线外一点的交点怎样计算, 这里

    直接上已经写完的两段代码.

    简图

     

      因为是计算机, 肯定是通过两点来确定直线方程了, 首先是用点斜式的计算方法( 原始方程 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维都能提供解. 

      所以在做功能前仔细想好怎样做, 慎重选择数学模型是非常重要的. 虽然这些活看似初中生也能做, 大学生也能做, 差距还是一目了然的吧.

     

    PS : 在射线和直线重合的时候, 这个方法也是无解的, 因为首先射线跟直线是平行的, 行列式无解, 还要做一次与判断才行(2019.06.19) 

    PS : 计算精度问题今天碰到了, 下图判断点是否在线段内的时候会出错... 后续会进行修改(2019.06.19) 

    PS :  忘了在射线与线段平行时也有交点的情况, 仍然需要计算交点.... 后续会进行修改(2019.06.20)

     

    时间点:(2019.06.18)

    补充一下上面说过的多元线性方程组的解, 分成行列式和线性方程组:

        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)
            public static bool IntersectRayAndLineSegment_XOZ_TwoPoint(Ray ray, Vector3 p1, Vector3 p2, out Vector3 point, out bool isParallel)
            {
                isParallel = false;
                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);
                
                // 使用行列式计算线性方程组
                DeterminantEquation determinantEquation = new DeterminantEquation(2);
                determinantEquation.determinant.SetRow(a1, b1);
                determinantEquation.determinant.SetRow(a2, b2);
                var variables = determinantEquation.CaculateVariables(-c1, -c2);
                if(variables == null)
                {
                    // 平行线测试添加 (2019.06.19)
                    float ea, eb;
                    ea = a1 * c2 - a2 * c1;
                    eb = b1 * c2 - b2 * c1;
                    if((ea == 0) && (eb == 0))
                    {
                        isParallel = true;
                        Debug.Log("Determinant No Result, it is Parallel Line.");
                        // 平行线未进行交点计算修改 (2019.06.20)
                        if(IsPointInsideLine(ray.origin, p1, p2))
                        {
                            point = ray.origin;
                            return true;
                        }
                        else
                        {
                            var testDir = ((p1 + p2) * 0.5f) - ray.origin;
                            testDir.y = 0.0f;
                            if(Vector3.Dot(rayDir, testDir) > 0)
                            {
                                point = Vector3.SqrMagnitude(p1 - ray.origin) < Vector3.SqrMagnitude(p2 - ray.origin) ? p1 : p2;
                                return true;
                            }
                        }
                        Debug.Log("it is Parallel Line, and has no intersection");
                    }
                    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 = IsPointInsideLine(point, p1, p2);
                }
                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);
            }
            
            /// <summary>
            /// 检查是否相等, 解决计算机计算误差
            /// </summary>
            /// <param name="a"></param>
            /// <param name="b"></param>
            /// <returns></returns>
            public static bool IsTheSameValue(float a, float b)
            {
                const double Epsilon = 1e-5;
                var val = System.Math.Abs(a - b);
                return val <= Epsilon;
            }
            
            /// <summary>
            /// 测试点是否在线段上
            /// </summary>
            /// <param name="point"></param>
            /// <param name="lineStart"></param>
            /// <param name="lineEnd"></param>
            /// <returns></returns>
            public static bool IsPointInsideLine(Vector3 point, Vector3 lineStart, Vector3 lineEnd)
            {
                bool xClamp = IsTheSameValue(point.x, lineStart.x) || IsTheSameValue(point.x, lineEnd.x) || (point.x >= Mathf.Min(lineStart.x, lineEnd.x) && point.x <= Mathf.Max(lineStart.x, lineEnd.x));
                bool zClamp = IsTheSameValue(point.z, lineStart.z) || IsTheSameValue(point.z, lineEnd.z) || (point.z >= Mathf.Min(lineStart.z, lineEnd.z) && point.z <= Mathf.Max(lineStart.z, lineEnd.z));
                return xClamp && zClamp;
            }

     PS: 补充了射线与线段平行时的错误, 修改了精度错误测试.(2019.06.20)

      把行列式的类( 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 这个类就能很简单的计算出多元方程式的解. 所以在扩展性上胜出.

     

    (2019.06.18)

      昨天写的是用行列式解联立方程组得到的扩展性, 今天补充一下获取标准方程组特征值的泛用方法, 改进一下之前的函数, 提高扩展性.

    因为这一步应该很少人去实现, 就把推导过程也加上吧.

      先考虑2D和3D直线的一般方程: ax + by + C = 0 /  ax + by + cz + D = 0

      这里获取直线方程是通过两点获取的, 比如点斜式, 两点式, 都是基于几何的, 并且推导并不具有一般性.

      两点 p1(x1,y1), p2(x2, y2) => (y-y1)/(x-x1) = (y2-y1)/(x2-x1) 这是根据斜率相等得到的,  一步步下来就得到

      y(x1-x2) + x(y2-y1) + y1x2 - y2x1 = 0

      于是

        a = y2 - y1

        b = x1 - x2

        c = y1x2 - y2x1

      这是 PointToLineEquation_2D_XOZ 函数做的计算, 可是如果是多元等式的话要怎样推算呢? 这里直接使用向量的概念, 这个向量可以是任意阶的向量.

    向量 : vec = p2 - p1, 很好理解, 就是p1到p2的向量, 虽然可能是4阶, 5阶, 或者更高阶的. 假设f(p)是多元等式方程(  ax + by + cz + dw .... + N = 0  ),  

    那么向量的值就是 ( v1, v2, v3, v4, ..... ), 向量的意义是什么呢? 向量就代表了增量, 哪个元的向量增量大, 它在哪个方向的增量就大,

    得出的结论就是 : 在p1, p2构成的直线上(应该叫组成的多元等式上), p2点与p1点的差是向量vec, 任意一点p3与p1的差是向量vec的倍数,

    而向量vec本来就是p1到p2的向量, 即 :

      (v1) = (x2-x1) => (v1)/(x2-x1) = 1

      (v2) = (y2-y1) => (v2)/(y2-y1) = 1

      ......

      可得  (v1)/(x2-x1) = (v2)/(y2-y1) = (v3)/(z2-z1) ..... = 1

      而任一点p3( x3, y3, z3, w3 .... )与p1的向量为vec的n倍, 可得 :  (x3-x1)/(x2-x1) = (y3-y1)/(y2-y1) = (z3-z1)/(z2-z1) ..... = 1 * n 注意这里是多个等式

    然后我们把等式变成一般式(  ax + by + cz + dw .... + N = 0  )的形式, 要怎样变换呢? 很简单, 因为它们都相等, 用减法就行了, 比如上面的式子, 有A个元, 

    我们给它第一个等式乘一个(A-1)倍, 然后减去其它的元就行了 : 

      (x3-x1)/(x2-x1) = (y3-y1)/(y2-y1) = (z3-z1)/(z2-z1) ..... = 1 * n

      变换可得 : (A-1)*(x3-x1)/(x2-x1) -  (y3-y1)/(y2-y1) - (z3-z1)/(z2-z1) - ....... = 0

      然后p3点代表任意点, 把它写成一般式的未展开形式 :  (A-1)*(x-x1)/(v1) -  (y-y1)/(v2) - (z-z1)/(v3) - ....... = 0  

      在这里我们按照计算原则, 不进行除法以便消除计算误差, 那么给等式两边乘以 (v1)*(v2)*(v3)......*(vA) 有A个元

      得到没有除法的一般式 :  (A-1)*(x-x1)*(v2)*(v3)......*(vA) -  (y-y1)*(v1)*(v3)......*(vA) - (z-z1)*(v1)*(v2)......*(vA) - ....... = 0

      最后抽出一般式的各个变量:

      a = (A-1)*(v2)*(v3)......*(vA)

      b = (-1)*(v1)*(v3)......*(vA)

      c = (-1)*(v1)*(v2)......*(vA)

      .......

      N = (-x1)*(A-1)*(v2)*(v3)......*(vA) + (y1)*(v1)*(v3)......*(vA) + (z1)*(v1)*(v2)......*(vA) + ......

      这样就可以得到一般式(  ax + by + cz + dw .... + N = 0  )的各个变量了.

      PS : 多元方程的一般式求解不仅限于2D直线3D直线这些, 到更多元的计算比如12维空间这些都能用的上, 并不是没有实际意义的.

     

    下面是实现的代码, 很意外的非常简单:

        public static class GeometryMath
        {
            /// <summary>
            /// 求解多元线性方程的特征值
            /// </summary>
            /// <param name="p1"></param>
            /// <param name="p2"></param>
            /// <param name="variables"> (aX + bY + cZ + dW + ..... + N = 0) => (a, b, c, d, .... N) </param>
            public static void MultivariateLinearEquation(float[] p1, float[] p2, out float[] variables)
            {
                int maxLen = Mathf.Min(p1.Length, p2.Length);
                variables = new float[maxLen + 1];
                float[] vector = new float[maxLen];
                for(int i = 0; i < maxLen; i++)
                {
                    vector[i] = p2[i] - p1[i];
                }
                // caculate variables form vector
                variables[0] = (maxLen - 1) * ArrayValueMultiple(vector, 0);
                for(int i = 1; i < maxLen; i++)
                {
                    variables[i] = (-1) * ArrayValueMultiple(vector, i);
                }
                // caculate last fixed value
                float N = (-1) * p1[0] * ArrayValueMultiple(vector, 0);
                for(int i = 1; i < p1.Length; i++)
                {
                    float value = p1[i] * ArrayValueMultiple(vector, i);
                    N += value;
                }
                variables[variables.Length - 1] = N;
            }
            /// <summary>
            /// float数组中去掉某个index的值的相乘
            /// </summary>
            /// <param name="array"></param>
            /// <param name="except"></param>
            /// <returns></returns>
            private static float ArrayValueMultiple(float[] array, int except)
            {
                float value = 1.0f;
                for(int i = 0; i < array.Length; i++)
                {
                    if(i != except)
                    {
                        value *= array[i];
                    }
                }
                return value;
            }
        }

     

    然后是改动后的两点式代码, 修正了计算误差:

            /// <summary>
            /// 射线与线段相交性判断
            /// </summary>
            /// <param name="ray"></param>
            /// <param name="p1"></param>
            /// <param name="p2"></param>
            /// <param name="point"></param>
            /// <param name="isParallel"></param>
            /// <returns></returns>
            public static bool IntersectRayAndLineSegment_XOZ_TwoPoint(Ray ray, Vector3 p1, Vector3 p2, out Vector3 point, out bool isParallel)
            {
                point = Vector3.zero;
                isParallel = false;
                Vector3 p3 = new Vector3(ray.origin.x, 0, ray.origin.z);
                Vector3 p4 = ray.GetPoint(1.0f);
                p4.y = 0;
                var rayDir = ray.direction;
                rayDir.y = 0;
    
                float a1, b1, c1;
                float[] variables1;
                GeometryMath.MultivariateLinearEquation(new float[2] { p1.x, p1.z }, new float[2] { p2.x, p2.z }, out variables1);
                a1 = variables1[0];
                b1 = variables1[1];
                c1 = variables1[2];
    
                float a2, b2, c2;
                float[] variables2;
                GeometryMath.MultivariateLinearEquation(new float[2] { p3.x, p3.z }, new float[2] { p4.x, p4.z }, out variables2);
                a2 = variables2[0];
                b2 = variables2[1];
                c2 = variables2[2];
    
                DeterminantEquation determinantEquation = new DeterminantEquation(2);
                determinantEquation.determinant.SetRow(a1, b1);
                determinantEquation.determinant.SetRow(a2, b2);
                var variables = determinantEquation.CaculateVariables(-c1, -c2);
                if(variables == null)
                {
                    float ea, eb;
                    ea = a1 * c2 - a2 * c1;
                    eb = b1 * c2 - b2 * c1;
                    if((ea == 0) && (eb == 0))
                    {
                        isParallel = true;
                        Debug.Log("Determinant No Result, it is Parallel Line.");
                        if(IsPointInsideLine(ray.origin, p1, p2))
                        {
                            point = ray.origin;
                            return true;
                        }
                        else
                        {
                            var testDir = ((p1 + p2) * 0.5f) - ray.origin;
                            testDir.y = 0.0f;
                            if(Vector3.Dot(rayDir, testDir) > 0)
                            {
                                point = Vector3.SqrMagnitude(p1 - ray.origin) < Vector3.SqrMagnitude(p2 - ray.origin) ? p1 : p2;
                                return true;
                            }
                        }
                        Debug.Log("it is Parallel Line, and has no intersection");
                    }
                    return false;
                }
                point = new Vector3(variables[0], 0, variables[1]);
    
                bool intersect = Vector3.Dot(point - p3, rayDir) > 0;
                if(intersect)
                {
                    intersect = IsPointInsideLine(point, p1, p2);
                }
                return intersect;
            }
            
                    /// <summary>
            /// 检查是否相等, 解决计算机计算误差
            /// </summary>
            /// <param name="a"></param>
            /// <param name="b"></param>
            /// <returns></returns>
            public static bool IsTheSameValue(float a, float b)
            {
                const double Epsilon = 1e-5;
                var val = System.Math.Abs(a - b);
                return val <= Epsilon;
            }
            
                    /// <summary>
            /// 测试点是否在线段上
            /// </summary>
            /// <param name="point"></param>
            /// <param name="lineStart"></param>
            /// <param name="lineEnd"></param>
            /// <returns></returns>
            public static bool IsPointInsideLine(Vector3 point, Vector3 lineStart, Vector3 lineEnd)
            {
                bool xClamp = IsTheSameValue(point.x, lineStart.x) || IsTheSameValue(point.x, lineEnd.x) || (point.x >= Mathf.Min(lineStart.x, lineEnd.x) && point.x <= Mathf.Max(lineStart.x, lineEnd.x));
                bool zClamp = IsTheSameValue(point.z, lineStart.z) || IsTheSameValue(point.z, lineEnd.z) || (point.z >= Mathf.Min(lineStart.z, lineEnd.z) && point.z <= Mathf.Max(lineStart.z, lineEnd.z));
                return xClamp && zClamp;
            }

      看着真是牛了, 最终在计算上规避了所有除法公式造成的数据错误, 稳定性非常高, 然后在获取一般方程上扩展出了获取任意元的一般方程的方法, 以及计算任意阶线性方程组的方法.

    唯一的遗憾就是判断point是否在线段上的精度误差.

     

    转载于:https://www.cnblogs.com/tiancaiwrk/p/11039595.html

    展开全文
  • 5.2 圆环与摄像机内参数5.2.1 内参数约束方程5.2.2 确定圆环点的图像正方形个圆圆与直线平面相似图形5.2.3 圆环与其正交方向例子 5.2.1 内参数约束方程 共轭 ptCq=0,pq关于C共轭 圆环点的像仍是虚 ...

    5.2.1 内参数的约束方程

    在这里插入图片描述
    共轭 ptCq=0,pq关于C共轭
    圆环点的像仍是虚点

    5.2.2 确定圆环点的图像

    基于圆环点的标定方法的关键问题是如何在图像平面上确定圆环点的图像。由于圆环点是虚点从而无法直接从图像获取,因此需要借助图像中所包含的相关场景结构信息才能得到圆环点图像。

    正方形

    在这里插入图片描述
    Xj为正方形所在平面坐标,通过相应图像坐标得到单应矩阵

    两个圆

    在这里插入图片描述
    二次曲线的摄影变换还是二次曲线
    为什么圆和中心的图像也能确定圆环点图像?见下面圆与直线

    圆与直线

    在这里插入图片描述
    调和共轭
    在这里插入图片描述

    平面相似图形

    在这里插入图片描述
    在这里插入图片描述

    5.2.3 圆环点与其正交方向

    在这里插入图片描述
    在这里插入图片描述
    x为齐次因子
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    例子 从圆柱的图像标定内参数

    在这里插入图片描述

    展开全文
  • 一、极点(extreme point) 继续考虑钉子与橡皮筋的例子。...有向直线可以将平面划分确定的左右部分; 可以在图像上表示为: 可以发现,边缘上“有贡献”的钉子,总可以找到一条穿过它的有向...
  • 在计算机中由像素构成的点很难直接画成直线,一般通过确定离散在直线附近的点来近似的确定直线。Bresenham算法可以通过确定直线附近离散来画线,同样可以运用于画圆。 (1)具体例子解释:在这个例子中,我们以...
  • 坐标又分绝对坐标和相对坐标种了解了坐标含义之后,坐标输入就好办了,下面以几个例子来学习坐标输入输入直线命令L,第一个屏幕随便一下(或以捕捉方式点击已经存在的点),第二个点的输入@100,50,即...
  • 假如你要在一些打破项链,展开成一条直线,然后从一端开始收集同颜色珠子直到你遇到一个不同颜色珠子,在另一端做同样事(颜色可能与在这之前收集不同)。 确定应该在哪里打破项链来收集到最大数目珠子。 ...
  • 凸集

    2018-01-08 10:49:41
    简单来说,就是两点确定一条直线的直线        凸集 有 集合C是凸的 简单来说,就是两点间的线段    锥 C为锥 C为凸锥 简单理解,C为射线集合      ...
  • 从上一课可知,对于给定的线性可分的数据集,离分隔超平面最近的点是支持向量。... 选取一个函数里的两个点,连接两个点成一条直线两点间的函数点都在这条直线下即为凸函数,凸函数的例子有指数函数。
  • 线性回归多重共线性优化

    千次阅读 2017-09-12 18:33:49
    最小二乘回归法,但是对于大多数的实际问题,由于我们要用有限的观测值去估计模型的分布,比如在之前讲线性回归中的例子,给出的样例有100对,而我们建立的模型是一条直线,我们都知道两点确定一条直线,这里有100个...
  • 3.19.1 确定一个点的可见性 194 3.19.2 线段求交 196 3.19.3 算法 197 3.20 Liang-Barsky多边形裁剪 202 3.20.1 进和出点 203 3.20.2 折 203 3.20.3 算法设计 205 3.20.4 水平边和垂直边 207 3.20.5 ...
  • 误差来源于何处?...简单model受不同data影响较小(我理解:两点确定一条直线,曲线需要更多点? 极端例子:f(x)=cf(x)=cf(x)=c ,不论什么data,output都是c Bias 黑线:真实function 蓝线:5000
  • 1.16.17 pku3668_GameofLine_N个最多确定多少互不平行的直线(poj3668) 99 1.16.18 求凸多边形直径 100 2.组合 102 2.1 组合公式 102 2.2 排列组合生成 102 2.3 生成gray码 104 2.4 置换(polya) 104 2.5 字典序...
  • 这个程序里我们实现了类窗口打开方式,一个是自身消失而 后打开另一个窗口,一个是打开另一个窗口而自身不消失。可以看到他们实现 方法是不同。 三、Qt Creator 登录对话框(原创) 实现功能: 在弹出对话框...
  • 特点:两点确定一条直线,存在唯一两点——即第一个元素和最后一个元素,其他数据元素均有唯一“直接后继”和“直接前继” 数组是存储多个相同类型数据集合。 常见线性数据结构典型例子有栈、队列、线性表...
  • 如果是进行分类,将新样本投影到同样这条直线上,根据投影点的位置来确定新样本类别。 将高维模式样本投影到最佳鉴别矢量空间,以达到抽取分类信息和压缩特征空间维数效果,投影后保证模式样本在新子空间...
  • 找公切线

    2013-09-24 17:36:45
    公切线是同时与多边形相切...事实上, 公切线可以通过多边形间一些确定的点对来确立。 因此, 给定个不相交多边形, 就存在个多边形间条公切线, 并且当多边形相交时, 还有可能存在与顶点数一样多公切线
  • GSP5.exe

    2020-04-01 09:16:40
    通过两点作圆;用圆心与半径画圆(这种方法作圆定长不变,除非改变定长时,否则半径不变) 圆弧 画圆弧也有3种方法 按一定顺序选定三点然后作弧(按逆时针方向从起点到终点画弧);选取圆及圆上2点作弧(从第一点...
  • 在对新样本进行分类时,将其投影到同样这条直线上,再根据投影点的位置来确定新样本类别。 2.特征抽取:可以将原始数据集变换到一个维度更低特征子空间,在尽可能多地保持相关信息情况下,对数据进行...
  • 旋转卡壳——找公切线

    千次阅读 2013-05-31 11:48:24
    找公切线 公切线是同时与多边形相切简单直线, 并且个多边形都位于线同一侧。 换句话说, 一条公切线是一条与个多边形都相切线。...事实上, 公切线可以通过多边形间一些确定的点对来
  • 支持向量机 简单记了关键词,具体的数学推理回看视频,查阅资料 ...就能满足所有的例子有yi(w·xi+b) >= 1,边界时=1 求个边缘之间的距离,向量差·与街道中线垂直的单位向量 作者:wizardOfCode
  • 第6页 C#(WINFORM)学习 找到集合中数量最多一个元素 利用方法来查找,可以返回个变量。 object Jmax0(ArrayList v11,ref int jj) { int i; object j0=0; ArrayList y11=new ArrayList(); //各个不同元素...

空空如也

空空如也

1 2 3
收藏数 47
精华内容 18
关键字:

两点确定直线的例子