问一个关于求直线和圆交点算法~~~

如题~~在纸上是可以算出来的~~~
但是用C++语言来描述那个求解过程的话`~~~就头疼了
~~~大虾们~~帮忙咯~~~

10 个解决方案

#1

建两个链表：一个存圆的点的位置，一个存直线的点的位置，判断两个链表中是否是想同的值

#2

看你的图形在计算机中是怎样描述的
如果是用矢量描述的,就按照数学中的公式计算,只是个坐标的换算问题
如果是用标题描述的,可以顺着直线搜索下去,如果某个点周围的点个数大于2,就是交点,当然这只针对于一像素单位的直线

#3

现实问题中怎么描述就怎么去做呀~

需求分析

#4

#include <stdio.h>

#define abs(x) ((x) >= 0 ? (x) : -(x))

/*
用牛顿迭代法求方程的根：
解非线性方程f(x)=0的牛顿法是把非线性方程线性化的一种近似方法。把f(x)在x0点附近展开成泰勒级数
f(x) = f(x0) + (x - x0)f'(x0) + (x - x0)^2 + …
取其线性部分，作为非线性方程f(x)=0的近似方程，则有
f(x0) + f'(x0)(x - x0) = 0
设f'(x0)!=0则其解为
x1 = x0 - f(x0) / f'(x0)
再把f(x)在x1附近展开成泰勒级数，也取其线性部分作f(x)=0的近似方程。若f(x1)!=0，则得
x2 = x1 - f(x1) / f'(x1)
这样，得到牛顿法的一个迭代序列
xn+1 = xn - f(xn) / f'(xn)
*/

/*
y = k * x + c, (x - a)^2 + (y - b)^2 = r^2 =>
(1 + k^2) * x^2 + 2 * (k * c - a - b) * x + (c - b)^2 + a^2 - r^2 = 0 =>
f(x) = (1 + k^2) * x^2 + 2 * (k * c - a - b) * x + (c - b)^2 + a^2 - r^2 =>
f'(x) = 2 * (1 + k^2) * x + 2 * (k * c - a - b) (为f(x)的导数)
*/

// precision 为根的精度
void point(double k, double c, double a, double b, double r, double precision)
{
for(int i = 0; i < 2; i++)
{
double s = i == 0 ? -r : r;
double x = a + s;
double x1 = a + s;
double delta = 0;
int first = 1;
do
{
x = x1;

double fx = (1 + k * k) * x * x +
2 * (k * c - a - b) * x +
(c - b) * (c - b) + a * a - r * r;
double dfx = 2 * (1 + k * k) * x + 2 * (k * c - a - b);

x1 = x - fx / dfx;

if(!first && delta < abs(x1 - x))
{
break; // 没有根
}

first = 0;
delta = abs(x1 - x);

} while(delta > precision);

if(delta < precision)
{
double xx = x;
double yy = k * x + c;

printf("x = %f, y = %f\n", xx, yy);
}
}
}

int main(int argc, char* argv[])
{
point(1, 0, 0, 0, 1, 0.000001);

return 0;
}

#5

看圆心到直线之间的距离，再求三角形找圆心的偏移量（x,y),也太简单拉

#6

看圆心到直线之间的距离，再求三角形找圆心的偏移量（x,y),也太简单拉

我做过类似的算法
但是发现效果不好

#7

参看《计算机图形学几何工具算法详解》P176.
to tufaqing() 你为什么要把简单的问题复杂化。

#8

VB写在圆的类中的代码。
'''
'''返回与一直线的交点
'''二次方程求解法
'''
Public Function IntersAline(ByVal Aline As xLine) As xPoint()
    Dim A As Double, B As Double
    Dim Aa As Double, Ab As Double, Ac As Double
    Dim i As Long, i1 As Long
    Dim Outps() As xPoint, Np As xPoint
    On Error Resume Next
    If Aline.Sp.X = Aline.Ep.X Then
        If Aline.Sp.X > Cp.X - r And Aline.Sp.X < Cp.X + r Then
            Set Np = New xPoint
            Np.X = Aline.Sp.X
            Np.Y = Cp.Y + Sqr(r ^ 2 - (Np.X - Cp.X) ^ 2)
            If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                ReDim Outps(0)
                Set Outps(0) = Np.GetMe
            End If
            Np.Y = Cp.Y - Sqr(r ^ 2 - (Np.X - Cp.X) ^ 2)
            If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                Err.Clear
                i1 = UBound(Outps)
                If i1 < 0 Then
                    i1 = 0
                    Err.Clear
                Else
                    i1 = i1 + 1
                End If
                ReDim Preserve Outps(i1)
                Set Outps(i1) = Np.GetMe
            End If
        ElseIf Aline.Sp.X = Cp.X - r Or Aline.Sp.X = Cp.X + r Then
            Set Np = New xPoint
            Np.X = Aline.Sp.X
            Np.Y = Cp.Y
            If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                ReDim Outps(0)
                Set Outps(0) = Np.GetMe
            End If
        End If
    ElseIf Aline.Sp.Y = Aline.Ep.Y Then
        If Aline.Sp.Y > Cp.Y - r And Aline.Sp.Y < Cp.Y + r Then
            Set Np = New xPoint
            Np.Y = Aline.Sp.Y
            Np.X = Cp.X + Sqr(r ^ 2 - (Np.Y - Cp.Y) ^ 2)
            If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                ReDim Outps(0)
                Set Outps(0) = Np.GetMe
            End If
            Set Np = New xPoint
            Np.Y = Aline.Sp.Y
            Np.X = Cp.X - Sqr(r ^ 2 - (Np.Y - Cp.Y) ^ 2)
            If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                Err.Clear
                i1 = UBound(Outps)
                If i1 < 0 Then
                    i1 = 0
                    Err.Clear
                Else
                    i1 = i1 + 1
                End If
                ReDim Preserve Outps(i1)
                Set Outps(i1) = Np.GetMe
            End If
        ElseIf Aline.Sp.Y = Cp.Y - r Or Aline.Sp.Y = Cp.Y + r Then
            Set Np = New xPoint
            Np.X = Cp.X
            Np.Y = Aline.Sp.Y
            If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                ReDim Outps(0)
                Set Outps(0) = Np.GetMe
            End If
        End If
    Else
        Call Aline.GetAB(A, B)
        Aa = A ^ 2 + 1
        Ab = 2 * A * (Aline.Sp.Y - A * Aline.Sp.X) - 2 * Cp.X - 2 * A * Cp.Y
        Ac = Cp.X ^ 2 + (Aline.Sp.Y - A * Aline.Sp.X) ^ 2 - 2 * Cp.Y * (Aline.Sp.Y - A * Aline.Sp.X) + Cp.Y ^ 2 - r ^ 2
        If Ab ^ 2 - 4 * Aa * Ac > 0 Then
            If Aa = 0 Then
                Set Np = New xPoint
                Np.X = (Ac * -1) / Ab
                Np.Y = A * (Np.X - Aline.Sp.X) + Aline.Sp.Y
                If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                    ReDim Outps(0)
                    Set Outps(0) = Np.GetMe
                End If
            Else
                Set Np = New xPoint
                Np.X = (Ab * -1 + Sqr(Ab ^ 2 - 4 * Aa * Ac)) / (2 * Aa)
                Np.Y = A * (Np.X - Aline.Sp.X) + Aline.Sp.Y
                If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                    ReDim Outps(0)
                    Set Outps(0) = Np.GetMe
                End If
                Set Np = New xPoint
                Np.X = (Ab * -1 - Sqr(Ab ^ 2 - 4 * Aa * Ac)) / (2 * Aa)
                Np.Y = A * (Np.X - Aline.Sp.X) + Aline.Sp.Y
                If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                    Err.Clear
                    i1 = UBound(Outps)
                    If i1 < 0 Then
                        i1 = 0
                        Err.Clear
                    Else
                        i1 = i1 + 1
                    End If
                    ReDim Preserve Outps(i1)
                    Set Outps(i1) = Np.GetMe
                End If
            End If
        ElseIf Ab ^ 2 - 4 * Aa * Ac = 0 Then
            If A <> 0 Then
                Set Np = New xPoint
                Np.X = (Ab * -1) / (2 * Aa)
                Np.Y = A * (Np.X - Aline.Sp.X) + Aline.Sp.Y
                If Np.Distance(Aline.Sp) <= Aline.Length And Np.Distance(Aline.Ep) <= Aline.Length Then
                    ReDim Outps(0)
                    Set Outps(0) = Np.GetMe
                End If
            End If
        End If
    End If
    IntersAline = Outps
End Function
返回所有交点。

#9

上面函数中的A＝(aline.ep.y-aline.sp.y)/(aline.ep.x-aline.sp.x)

#10

引用 4 楼 tufaqing 的回复:

#include    <stdio.h>

#define   abs(x)   ((x)   > =   0   ?   (x)   :   -(x))

/*
用牛顿迭代法求方程的根：
解非线性方程f(x)=0的牛顿法是把非线性方程线性化的一种近似方法。把f(x)在x0点附近展开成泰勒级数
f(x)   =   f(x0)   +   (x   -   x0)f '(x0) ……

大侠，void point(double k, double c, double a, double b, double r, double precision)

参数的意义各是什么啊？

#1