HSPで幾何モジュール - 点と線と円

目的

以下の命令を実装するよ．

• 直線と直線の交点を求める
• 直線と円の交点を求める
• 円と円の交点を求める
• 直線と点の距離を求める
• 点に最も近い直線上の点を求める

高校数学の最初の方の知識だけで解くことは出来ますが，面倒．

モジュール

モジュール上での直線・円の表現方法について

円は 半径r，中心座標x,y の3つのパラメータで表現します．

直線は 媒介変数を用いた表現です．4つのパラメータvx vy px pyで表現されて，tを媒介変数とした時 x=vx*t+px，y=vy*t+pyを満たす点の集まり(x,y)です． 例えば，座標(a,b)と(c,d)を通る直線は，px=a,py=b,vx=c-a,vy=d-bとなります．

モジュール

#module

    // 
    // 内積
    #defcfunc d2dot double x1, double y1, double x2, double y2
    return x1*x2+y1*y2

    // 
    // 外積
    #defcfunc d2cross double x1, double y1, double x2, double y2
    return x1*y2-x2*y1

    // 
    // 直線と直線の交点を求める
    // 交点が存在する場合，stat=1，そうでなければ，stat=0．
    // vx1,vy1,px1,py1 : 媒介変数表示された直線 x=px1+vx1*t, y=py1+vy1*t
    // vx2,vy2,px2,py2 : 媒介変数表示された直線 x=px2+vx2*t, y=py2+vy2*t
    // x9,y9           : 交点を格納する変数
    #deffunc d2intersectionLine2Line double vx1, double vy1, double px1, double py1, double vx2, double vy2, double px2, double py2, var x9, var y9
    t = d2cross(vx1,vy1,vx2,vy2)
    if (t == 0) : return 0
    t = -d2cross(vx1, vy1, px2-px1, py2-py1)/t
    x9 = px2 + t*vx2
    y9 = py2 + t*vy2
    return 1

    //
    // 線と円の交点を求める
    // 交点が存在する場合，stat=1，そうでなければ，stat=0．
    // 交点が1つのみ存在する場合，2つの交点を格納する変数には同じ座標が格納される．
    // vx1,vy1,px1,py1 : 媒介変数表示された直線 x=px1+vx1*t, y=py1+vy1*t
    // r2,x2,y2     : x2,y2を中心とする半径r2の円
    // x8,y8, x9,y9 : 2つの交点を格納する変数
    #deffunc d2intersectionLine2Circle double vx1, double vy1, double px1, double py1, double r2, double x2, double y2, var x8, var y8, var x9, var y9
    t = vx1*(y2-py1)-vy1*(x2-px1)
    den = vx1*vx1+vy1*vy1
    det = den*r2*r2-t*t
    if (det < 0) : return 0
    num = vx1*(x2-px1)+vy1*(y2-py1)
    det = sqrt(det)

    x8 = px1 + vx1*(num+det)/den
    y8 = py1 + vy1*(num+det)/den
    x9 = px1 + vx1*(num-det)/den
    y9 = py1 + vy1*(num-det)/den
    return 1
    
    //
    // 円と円の交点を求める
    // 交点が存在する場合，stat=1，そうでなければ，stat=0．
    // 交点が1つのみ存在する場合，2つの交点を格納する変数には同じ座標が格納される．
    // r1,x1,y1     : x1,y1を中心とする半径r1の円
    // r2,x2,y2     : x2,y2を中心とする半径r2の円
    // x8,y8, x9,y9 : 2つの交点を格納する変数
    #deffunc d2intersectionCircle2Circle double r1, double x1, double y1, double r2, double x2, double y2, var x8, var y8, var x9, var y9
    if (x1 == x2 && y1 == y2) : return 0
    t = ((x1*x1+y1*y1)-(x2*x2+y2*y2)-r1*r1+r2*r2)/2
    if absf(x1-x2) < absf(y1-y2) {
        d2intersectionLine2Circle y1-y2,x2-x1,0,t/(y1-y2),r1,x1,y1,x8,y8,x9,y9
    }else{
        d2intersectionLine2Circle y1-y2,x2-x1,t/(x1-x2),0,r1,x1,y1,x8,y8,x9,y9
    }
    return stat

    // 
    // 直線と点の距離と，直線上で点に最寄りの座標を求める．
    // vx1,vy1,px1,py1 : 媒介変数表示された直線 x=px1+vx1*t, y=py1+vy1*t
    // x2,y2           : 点座標
    // dist         : 距離を格納する変数
    // x9,y9           : 直線上で点に最寄りの座標
    #deffunc d2distanceOfPoint2Line double vx1, double vy1, double px1, double py1, double x2, double y2, var dist, var x9, var y9
    dist = absf(d2cross(vx1,vy1,x2-px1,y2-py1))/sqrt(vx1*vx1+vy1*vy1)
    a = d2dot(vx1,vy1,x2-px1,y2-py1)/(vx1*vx1+vy1*vy1)
    x9 = px1 + vx1*a
    y9 = py1 + vy1*a
    return
    
#global

実行テスト

円や線を適当に置いて，交点や距離を可視化させています．

 randomize

    celload dir_exe+"/hsptv/efx.bmp",1
    celdiv 1,32,32,16,16
    gmode 5,,,255

    repeat
        redraw 0
        color 0,0,0 : boxf
        color 255,255,255

        // circle1
        r1 = rnd(150)+50
        x1 = rnd(400)+100
        y1 = rnd(300)+100
        // line2
        px2 = rnd(400)+100
        py2 = rnd(300)+100
        vx2 = rnd(400)+100
        vy2 = rnd(300)+100
        // circle3
        r3 = rnd(150)+50
        x3 = rnd(400)+100
        y3 = rnd(300)+100
        // line4
        px4 = rnd(400)+100
        py4 = rnd(300)+100
        vx4 = rnd(400)+100
        vy4 = rnd(300)+100

        circle x1-r1,y1-r1, x1+r1,y1+r1, 0
        line px2-vx2*999,py2-vy2*999, px2+vx2*999,py2+vy2*999
        circle x3-r3,y3-r3, x3+r3,y3+r3, 0
        line px4-vx4*999,py4-vy4*999, px4+vx4*999,py4+vy4*999

        ox1 = 0 : oy1 = 0 : ox2 = 0 : oy2 = 0
        dist = 0

        // circle1 - line2
        d2distanceOfPoint2Line vx2,vy2,px2,py2,x1,y1,dist,ox1,oy1
        color 64,0,0 : circle x1-dist,y1-dist,x1+dist,y1+dist,0
        color 255,0,0 : line ox1,oy1,x1,y1
        
        // circle3 - line4
        d2distanceOfPoint2Line vx4,vy4,px4,py4,x3,y3,dist,ox1,oy1
        color 64,0,0 : circle x3-dist,y3-dist,x3+dist,y3+dist,0
        color 255,0,0 : line ox1,oy1,x3,y3
        
        
        // circle1 vs line2
        d2intersectionLine2Circle vx2,vy2,px2,py2,r1,x1,y1,ox1,oy1,ox2,oy2
        if (stat) {
            pos ox1,oy1 : celput 1
            pos ox2,oy2 : celput 1
        }
        
        // circle1 vs circle3
        d2intersectionCircle2Circle r1,x1,y1,r3,x3,y3,ox1,oy1,ox2,oy2
        if (stat) {
            pos ox1,oy1 : celput 1
            pos ox2,oy2 : celput 1
        }
        
        // circle1 vs line4
        d2intersectionLine2Circle vx4,vy4,px4,py4,r1,x1,y1,ox1,oy1,ox2,oy2
        if (stat) {
            pos ox1,oy1 : celput 1
            pos ox2,oy2 : celput 1
        }
        
        // line2 vs circle3
        d2intersectionLine2Circle vx2,vy2,px2,py2,r3,x3,y3,ox1,oy1,ox2,oy2
        if (stat) {
            pos ox1,oy1 : celput 1
            pos ox2,oy2 : celput 1
        }
        
        // line2 vs line4
        d2intersectionLine2Line vx2,vy2,px2,py2,vx4,vy4,px4,py4,ox1,oy1
        if (stat) {
            pos ox1,oy1 : celput 1
        }
        
        // circle3 vs line4
        d2intersectionLine2Circle vx4,vy4,px4,py4,r3,x3,y3,ox1,oy1,ox2,oy2
        if (stat) {
            pos ox1,oy1 : celput 1
            pos ox2,oy2 : celput 1
        }
        

        redraw 1
        
        wait 150
    loop