Line segment intersection

Line segment intersection test.

Log in to post a comment.

// You can find the Turtle API reference here: https://turtletoy.net/syntax
Canvas.setpenopacity(1);

// Global code will be evaluated once.
const turtle = new Turtle();

const Segment0_A_X = 50; // min=-100, max=100, step=1
const Segment0_A_Y = 50; // min=-100, max=100, step=1
const Segment0_B_X = -50; // min=-100, max=100, step=1
const Segment0_B_Y = -50; // min=-100, max=100, step=1

const Segment1_A_X = -50; // min=-100, max=100, step=1
const Segment1_A_Y = -50; // min=-100, max=100, step=1
const Segment1_B_X = 90; // min=-100, max=100, step=1
const Segment1_B_Y = 90; // min=-100, max=100, step=1

const ENDPOINT_RADIUS = 0.5;
const TEXT_SIZE = 0.15;

////////////////////////////////////////////////////////////////
// Text utility code. Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/1713ddbe99
////////////////////////////////////////////////////////////////

function Text() {
    class Text {
        print (t, str, scale = 1, italic = 0, kerning = 1) {
            t.radians();
            let pos = [t.x(), t.y()], h = t.h(), o = pos;
            str.split('').map(c => {
                const i = c.charCodeAt(0) - 32;
                if (i < 0 ) {
                    pos = o = this.rotAdd([0, 48*scale], o, h);
                } else if (i > 96 ) {
                    pos = this.rotAdd([16*scale, 0], o, h);
                } else {
                    const d = dat[i], lt = d[0]*scale, rt = d[1]*scale, paths = d[2];
                    paths.map( p => {
                        t.up();
                    	p.map( s=> {
                        	t.goto(this.rotAdd([(s[0]-s[1]*italic)*scale - lt, s[1]*scale], pos, h));
                        	t.down();
                        });
                    });
                    pos = this.rotAdd([(rt - lt)*kerning, 0], pos, h);
                }
            });
        }
        rotAdd (a, b, h) {
            return [Math.cos(h)*a[0] - Math.sin(h)*a[1] + b[0], 
                    Math.cos(h)*a[1] + Math.sin(h)*a[0] + b[1]];
        }
    }
    
const dat = ('br>eoj^jl<jqirjskrjq>brf^fe<n^ne>`ukZdz<qZjz<dgrg<cmqm>`thZhw<lZlw<qao_l^h^e_caccdeefg'+
'gmiojpkqmqporlshsercp>^vs^as<f^h`hbgdeeceacaab_d^f^h_k`n`q_s^<olmmlolqnspsrrspsnqlol>]wtgtfsereqfph'+
'nmlpjrhsdsbraq`o`makbjifjekckaj_h^f_eaecffhimporqssstrtq>eoj`i_j^k_kajcid>cqnZl\\j_hcghglhqjulxnz>c'+
'qfZh\\j_lcmhmllqjuhxfz>brjdjp<egom<ogem>]wjajs<ajsj>fnkojpiojnkokqis>]wajsj>fnjniojpkojn>_usZaz>`ti'+
'^f_dbcgcjdofrisksnrpoqjqgpbn_k^i^>`tfbhak^ks>`tdcdbe`f_h^l^n_o`pbpdofmicsqs>`te^p^jfmfogphqkqmppnrk'+
'shserdqco>`tm^clrl<m^ms>`to^e^dgefhekenfphqkqmppnrkshserdqco>`tpao_l^j^g_ebdgdlepgrjsksnrppqmqlping'+
'kfjfggeidl>`tq^gs<c^q^>`th^e_dadceegfkgnhpjqlqopqorlshserdqcocldjfhigmfoepcpao_l^h^>`tpeohmjjkikfjd'+
'hcecddaf_i^j^m_oapepjoomrjshserdp>fnjgihjikhjg<jniojpkojn>fnjgihjikhjg<kojpiojnkokqis>^vrabjrs>]wag'+
'sg<amsm>^vbarjbs>asdcdbe`f_h^l^n_o`pbpdofngjijl<jqirjskrjq>]xofndlcicgdfeehekfmhnknmmnk<icgefhfkgmh'+
'n<ocnknmpnrntluiugtdsbq`o_l^i^f_d`bbad`g`jambodqfrislsorqqrp<pcokompn>asj^bs<j^rs<elol>_tc^cs<c^l^o'+
'_p`qbqdpfoglh<chlhoipjqlqopqorlscs>`urcqao_m^i^g_eadccfckdnepgrismsorqprn>_tc^cs<c^j^m_oapcqfqkpnop'+
'mrjscs>`sd^ds<d^q^<dhlh<dsqs>`rd^ds<d^q^<dhlh>`urcqao_m^i^g_eadccfckdnepgrismsorqprnrk<mkrk>_uc^cs<'+
'q^qs<chqh>fnj^js>brn^nnmqlrjshsfreqdndl>_tc^cs<q^cl<hgqs>`qd^ds<dsps>^vb^bs<b^js<r^js<r^rs>_uc^cs<c'+
'^qs<q^qs>_uh^f_daccbfbkcndpfrhslsnrppqnrkrfqcpan_l^h^>_tc^cs<c^l^o_p`qbqepgohlici>_uh^f_daccbfbkcnd'+
'pfrhslsnrppqnrkrfqcpan_l^h^<koqu>_tc^cs<c^l^o_p`qbqdpfoglhch<jhqs>`tqao_l^h^e_caccdeefggmiojpkqmqpo'+
'rlshsercp>brj^js<c^q^>_uc^cmdpfrisksnrppqmq^>asb^js<r^js>^v`^es<j^es<j^os<t^os>`tc^qs<q^cs>asb^jhjs'+
'<r^jh>`tq^cs<c^q^<csqs>cqgZgz<hZhz<gZnZ<gznz>cqc^qv>cqlZlz<mZmz<fZmZ<fzmz>brj\\bj<j\\rj>asazsz>fnkc'+
'ieigjhkgjfig>atpeps<phnfleiegfehdkdmepgrislsnrpp>`sd^ds<dhffhekemfohpkpmopmrkshsfrdp>asphnfleiegfeh'+
'dkdmepgrislsnrpp>atp^ps<phnfleiegfehdkdmepgrislsnrpp>asdkpkpiognfleiegfehdkdmepgrislsnrpp>eqo^m^k_j'+
'bjs<gene>atpepuoxnylzizgy<phnfleiegfehdkdmepgrislsnrpp>ate^es<eihfjemeofpips>fni^j_k^j]i^<jejs>eoj^'+
'k_l^k]j^<kekvjyhzfz>are^es<oeeo<ikps>fnj^js>[y_e_s<_ibfdegeifjijs<jimfoeretfuius>ateees<eihfjemeofp'+
'ips>atiegfehdkdmepgrislsnrppqmqkphnfleie>`sdedz<dhffhekemfohpkpmopmrkshsfrdp>atpepz<phnfleiegfehdkd'+
'mepgrislsnrpp>cpgegs<gkhhjfleoe>bsphofleieffehfjhkmlompopporlsisfrep>eqj^jokrmsos<gene>ateeeofrhsks'+
'mrpo<peps>brdejs<pejs>_ubefs<jefs<jens<rens>bseeps<pees>brdejs<pejshwfydzcz>bspees<eepe<esps>cqlZj['+
'i\\h^h`ibjckekgii<j[i]i_jakbldlfkhgjkllnlpkrjsiuiwjy<ikkmkojqirhthvixjylz>fnjZjz>cqhZj[k\\l^l`kbjci'+
'eigki<j[k]k_jaibhdhfihmjilhnhpirjskukwjy<kkimiojqkrltlvkxjyhz>^vamakbhdgfghhlknlplrksi<akbidhfhhill'+
'nmpmrlsisg>brb^bscsc^d^dsese^f^fsgsg^h^hsisi^j^jsksk^l^lsmsm^n^nsoso^p^psqsq^r^rs').split('>').map(
    r=> { return [r.charCodeAt(0)-106,r.charCodeAt(1)-106, r.substr(2).split('<').map(a => {const ret 
    = []; for (let i=0; i<a.length; i+=2) {ret.push(a.substr(i, 2).split('').map(b => b.charCodeAt(0)
    -106));} return ret; })]; });

    return new Text();
}
const txt = new Text();

// drawing utilities
function circle(x,y,radius,extent=undefined){turtle.penup();turtle.goto(x,y-radius);turtle.pendown();turtle.circle(radius,extent);}
function line(x1,y1,x2,y2){turtle.penup();turtle.goto(x1,y1);turtle.pendown();turtle.goto(x2,y2);}
function rect(l,t,b,r){line(l,t,l,b);line(l,t,r,t);line(r,t,r,b);line(l,b,r,b);}
function text(x,y,content,size){turtle.penup();turtle.goto(x,y-size);turtle.pendown();txt.print(turtle, content, size);}

function square(x,y,size){let hs = size*0.5;rect(x-hs,y-hs,y+hs,x+hs);}

//v2 operations
function sub2(a,b){return [a[0]-b[0],a[1]-b[1]];}
function add2(a,b){return [a[0]+b[0],a[1]+b[1]];}
function cross2(a,b){return a[0]*b[1]-a[1]*b[0];}
function dot2(a,b){return a[0]*b[0]+a[1]*b[1];}
function len2(v){return Math.sqrt(v[0]*v[0]+v[1]*v[1]);}
function equal2(a,b){return (a[0]==b[0])&&(a[1]==b[1]);}

function onsegment(a,b,p)
{
    // px in [ax,bx] and py in [ay,by];
    return (p[0]-a[0])*(p[0]-b[0])<=0 && (p[1]-a[1])*(p[1]-b[1])<=0
}

// use the function under the condition that the two segments have intersection.
function findIntersectPoint(s1,s2)
{
    let p1 = s1.a, p2 = s1.b, p3 = s2.a, p4 = s2.b;
    let x1 = p1[0],y1=p1[1],x2 = p2[0],y2=p2[1];
    let x3 = p3[0],y3=p3[1],x4 = p4[0],y4=p4[1];
    
    let d = (y4-y3)*(x2-x1) - (x4-x3)*(y2-y1);
    
    let u1 = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3))/d;
    //let u2 = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3))/d;
    
    if(!d){
        var dot = dot2(sub2(p2,p1),sub2(p4,p3));
        // check if only share one end point
        if((equal2(p1,p3)&&dot<0)||(equal2(p2,p3)&&dot>0)){return p3;}
        if((equal2(p1,p4)&&dot>0)||(equal2(p2,p4)&&dot<0)){return p4;}
        return undefined;}
    x = x1 + u1*(x2 - x1);
    y = y1 + u1*(y2 - y1);
    return [x,y];
}


class Segment
{
    constructor(a,b)
    {
        this.a = a;
        this.b = b;
    }
    
    static intersect(s1,s2)
    {
        var a = s1.a, b = s1.b, c = s2.a, d = s2.b;
        
        let ab = sub2(b,a),ac = sub2(c,a),ad = sub2(d,a);
        
        let rc = cross2(ab,ac);
        let rd = cross2(ab,ad);
        
        let cd = sub2(d,c), ca = sub2(a,c), cb = sub2(b,c);
        
        let ra = cross2(cd,ca);
        let rb = cross2(cd,cb);
        
        if((rc*rd<0)&&(ra*rb<0))
        {
            return true;
        }
        
        if(rc==0 && onsegment(a,b,c)){return true;}
        if(rd==0 && onsegment(a,b,d)){return true;}
        if(ra==0 && onsegment(c,d,a)){return true;}
        if(rb==0 && onsegment(c,d,b)){return true;}
        
        return false;
    }
    
    draw()
    {
        circle(this.a[0],this.a[1],ENDPOINT_RADIUS);
        line(this.a[0],this.a[1],this.b[0],this.b[1]);
        circle(this.b[0],this.b[1],ENDPOINT_RADIUS);
    }
}


var seg0 = new Segment([Segment0_A_X,Segment0_A_Y],[Segment0_B_X,Segment0_B_Y]);
var seg1 = new Segment([Segment1_A_X,Segment1_A_Y],[Segment1_B_X,Segment1_B_Y]);
seg0.draw();
seg1.draw();
var result = Segment.intersect(seg0,seg1);

if(result)
{
    let point = findIntersectPoint(seg0,seg1);
    
    if(point==undefined){
        
         text(-90,90,"A common segment of non-zero length.",0.1);
    }
    else
    {
        text(-90,90,"Intersection Detected!",TEXT_SIZE);
        square(point[0],point[1],3);
        text(point[0],point[1]+5,"x = "+point[0],TEXT_SIZE);
        text(point[0],point[1]+10,"y = "+point[1],TEXT_SIZE);
    }
    
    
}
else
{
    text(-90,90,"No common points.",TEXT_SIZE);
}

// The walk function will be called until it returns false.
function walk(i) {
    return i < 4;
}