jueves, 4 de febrero de 2016

El punto está dentro de un poligono bezier y una pista bezier

Las funciones de hoy pretenden identificar si un punto en el espacio bidimensional se encuentra dentro del área que encierra una figura formada por curvas bezier .
El ejemplo: https://jsfiddle.net/cincibeles/0bcag61a/9/
La siguiente función devuelve true o fase según sea el caso. Los parámetros que requiere son: un punto descrito por un array [x,y] y una sucesión de puntos que describan la figura, combinando curvas con líneas [[x1,y1],[x2,y2,cA2,cB2],[x3,y3]]. Donde se puede ver que una curva bezier se describe a través de tres cordenadas (origen A, controlador A y controlador B) usando como extremo final el siguiente punto en el arreglo.  Nota:requiere de funciones descritas abajo.

    var isDotInPolygonB=function (point, vs) {
        if(vs instanceof Array){      
            var x = point[0], y = point[1];
            var xi, yi, xj, yj, bx,by, cx,cy, r;
            var inside = false;
            for (var i = 0, j = vs.length - 1; i < vs.length; j = i++) {
                xi = vs[i][0]; yi = vs[i][1]; xj = vs[j][0]; yj = vs[j][1];
                if(vs[j][2]!=undefined && vs[j][3]!=undefined && vs[j][4]!=undefined && vs[j][5]!=undefined){
                    bx=vs[j][2]; by=vs[j][3]; cx=vs[j][4]; cy=vs[j][5];
                    r=BizierLineCollide(x,y,0,[xj,yj],[bx,by],[cx,cy],[xi,yi]);
                    r.forEach(function(v){ if(x<v[0]) inside = !inside; });
                }else
                    if ( ((yi > y) != (yj > y)) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi) ) inside = !inside;
            }
            return inside;
        } return false;
    };

Además, presento la misma función aplicada en donas creadas por dos formas bezier una dentro de otra. Por ejemplo un punto dentro de una pista delimitada por curvas bezier. 

En este caso los parametros son el punto [x,y] y dos arreglos de puntos, cada arreglo con la sucesión de puntos necesaria para formar una forma.   Nota:requiere de funciones descritas abajo.

vvar isDotInRoadB=function (point, vsOut, vsIn) {
    if((vsOut instanceof Array) && (vsIn instanceof Array)){
        var x = point[0], y = point[1], colionOut=[], colionIn=[], cntOut=0, cntIn=0;
        var xi, yi, xj, yj, xx, bx,by, cx,cy, r;;
        var inside = false;
        for (var i = 0, j = vsOut.length - 1; i < vsOut.length; j = i++) {
            xi = vsOut[i][0]; yi = vsOut[i][1]; xj = vsOut[j][0]; yj = vsOut[j][1];
            if(vsOut[j][2]!=undefined && vsOut[j][3]!=undefined && vsOut[j][4]!=undefined && vsOut[j][5]!=undefined){
                bx=vsOut[j][2]; by=vsOut[j][3]; cx=vsOut[j][4]; cy=vsOut[j][5];
                r=BizierLineCollide(x,y,0,[xj,yj],[bx,by],[cx,cy],[xi,yi]);
                r.forEach(function(v){
                    if(x<v[0]){ inside = !inside; }
                    else{ colionOut.push([j,i,v[0],v]); }
                    cntOut++;
                });
            }else
            if ( (yi > y) != (yj > y) ){
                xx = (xj - xi) * (y - yi) / (yj - yi) + xi;
                if (x < xx){
                    inside = !inside;
                }else colionOut.push([j,i,xx]);
                cntOut++;
            }
        }
        for (var i = 0, j = vsIn.length - 1; i < vsIn.length; j = i++) {
            xi = vsIn[i][0]; yi = vsIn[i][1]; xj = vsIn[j][0]; yj = vsIn[j][1];
            if(vsIn[j][2]!=undefined && vsIn[j][3]!=undefined && vsIn[j][4]!=undefined && vsIn[j][5]!=undefined){
                bx=vsIn[j][2]; by=vsIn[j][3]; cx=vsIn[j][4]; cy=vsIn[j][5];
                r=BizierLineCollide(x,y,0,[xj,yj],[bx,by],[cx,cy],[xi,yi]);
                r.forEach(function(v){
                    if(x<v[0]){ inside = !inside; }
                    else{ colionIn.push([j,i,v[0],v]); }
                    cntIn++;
                });
            }else
            if ( (yi > y) != (yj > y) ){
                xx = (xj - xi) * (y - yi) / (yj - yi) + xi;
                if (x < xx){
                    inside = !inside;
                }else colionIn.push([j,i,xx]);
                cntIn++;
            }
        }
        if(!inside && colionOut.length>0 && colionIn.length>0 && cntOut-colionOut.length + cntIn-colionIn.length>0){
            var a=colionOut.sort(sortByValue2).pop(), b=colionIn.sort(sortByValue2).pop();
            if(a.length>3){
                var ai=[a[3][0],a[3][1]], aj=[a[3][0]+a[3][3],a[3][1]+a[3][4]];
            }else{
                var ai=[vsOut[a[0]][0],vsOut[a[0]][1]], aj=[vsOut[a[1]][0],vsOut[a[1]][1]];
            }
            if(b.length>3){
                var bi=[b[3][0],b[3][1]], bj=[b[3][0]+b[3][3],b[3][1]+b[3][4]];
            }else{
                var bi=[vsIn[b[0]][0],vsIn[b[0]][1]], bj=[vsIn[b[1]][0],vsIn[b[1]][1]];
            }
            if(triangleNormal(point,ai,aj)*triangleNormal(point,bi,bj)<0) inside=true;
        }
        return inside;
    } return false;
};


Ambas funciones ( isDotInPolygonB y isDotInRoadB ) requieren de funciones de apoyo.

            // encuentra la normal de un triangulo
            var triangleNormal=function(p,a,b){
                var i=a[0]-p[0]; var j=a[1]-p[1]; var k=b[0]-p[0]; var l=b[1]-p[1];
                return i*l-j*k;
            }
            var reverseSortByValue2=function(a,b){ return a[2]>b[2]?1:(a[2]<b[2]?-1:0); }


// devuelve el punto de cruce entre una línea y una curva bizier.
function BizierLineCollide(x,y,m,A,B,C,D){
    var Ax=A[0], Ay=A[1], At, Bx=B[0], By=B[1], Bt, Cx=C[0], Cy=C[1], Ct, Dx=D[0], Dy=D[1], Dt, result=[];
    if(Math.abs(m)<=1){
        At=(Ay-3*By+3*Cy-Dy)-m*(Ax-3*Bx+3*Cx-Dx);
        Bt=3*(By-2*Cy+Dy)-m*3*(Bx-2*Cx+Dx);
        Ct=3*(Cy-Dy)-m*3*(Cx-Dx)
        Dt=Dy-y+m*(x-Dx);
        result= eqCubic(At,Bt,Ct,Dt);
    }else{
        var w=1/m;
        At=(Ax-3*Bx+3*Cx-Dx)-w*(Ay-3*By+3*Cy-Dy);
        Bt=3*(Bx-2*Cx+Dx)-w*3*(By-2*Cy+Dy);
        Ct=3*(Cx-Dx)-w*3*(Cy-Dy);
        Dt=Dx-x+w*(y-Dy);
        result= eqCubic(At,Bt,Ct,Dt);
    }
    var fnB=fnBizier(A,B,C,D), _return=[];
    result.forEach(function(v,k){
        if(!isNaN(v)){
            v=Math.round(v*10000)/10000;
            if(v>=0 && v<1){
                _return.push(fnB(v));
            }
        }
    });
    return _return;
}

// resuelve hasta una ecuación cubica a través de sus factores.
// fue tomada de http://www.gyplan.com/es/eqcubic_es.html
function eqCubic(a,b,c,d){
    var x1=x2=x3=0, f,g,h,m,k,m2,n,n2,r,rc,theta;
       
    if(a=="" && b==""&& c=="" && d=="") return 'es vacia';
    if(a=="" && b==""&& c=="" ) return d;
    if(a=="" && b=="" ){
        a=c; b=d;
        return -b/a; 
    }
    if(a==0 | a=="") {
        a=b; b=c; c=d;
        var b24ac2a=Math.sqrt(b*b-4*a*c);
        return isNaN(b24ac2a)?[]:[(-b+b24ac2a)/(2*a),(-b-b24ac2a)/(2*a)];
    };

    f = (((3*c)/a) - (((b*b)/(a*a))))/3
    g = ((2*((Math.pow(b,3))/(Math.pow(a,3)))-(9*b*c/(a*a)) + ((27*(d/a)))))/27 // Math.pow(b,3)
    h = (((g*g)/4) + ((f*f*f)/27))
    var dis = h;
    if (h > 0){
        m = (-(g/2)+ (Math.sqrt(h)))
        k=1
        if (m < 0) k=-1; else k=1
        m2 = (Math.pow((m*k),(1/3)))
        m2 = m2*k
        k=1
        n = -(g/2)- (Math.sqrt(h))
        if (n < 0) k=-1; else k=1
        n2 = (Math.pow((n*k),(1/3)))
        n2 = n2*k
        k=1
        x1= (m2 + n2) - b/(3*a);
        x2= ((-1*(m2 + n2)/2 - b/(3*a)) + "  + i * " + (m2 - n2)*Math.pow(3,.5)/2 );
        x3= ((-1*(m2 + n2)/2 - b/(3*a)) + "  - i * " + (m2 - n2)*Math.pow(3,.5)/2 );
        return [x1,x2,x3];
    }
    if (h<=0){
        r = ((Math.sqrt((g*g/4)-h)));
        k=1;
        if (r<0) k=-1;
        rc = Math.pow((r*k),(1/3))*k;
        k=1;
        theta =Math.acos((-g/(2*r)));
        x1= (2*(rc*Math.cos(theta/3))-(b/(3*a)));
        x2a=rc*-1;
        x2b= Math.cos(theta/3);
        x2c= Math.sqrt(3)*(Math.sin(theta/3));
        x2d= (b/3*a)*-1;
        x2=(x2a*(x2b + x2c))-(b/(3*a));
        x3=(x2a*(x2b - x2c))-(b/(3*a));
        return [x1,x2,x3];
    }

}

// devuelve una función que describe una curva bizier, esta función regresa cada punto a través del parámetro t
function fnBizier(pA,cA,cB,pB){
    var B=[
        function(x){ return x*x*x; },
        function(x){ return 3*x*x*(1-x); },
        function(x){ var x1=(1-x); return 3*x*x1*x1; },
        function(x){ var x1=(1-x); return x1*x1*x1; }
    ],
    C=[pA,cA,cB,pB],
    Ax=3*(C[0][0] - 3*C[1][0] + 3*C[2][0] - C[3][0]),
    Bx=2*(3*C[1][0] - 6*C[2][0] + 3*C[3][0]),
    Cx=(3*C[2][0] - 3*C[3][0]),
    Ay=3*(C[0][1] - 3*C[1][1] + 3*C[2][1] - C[3][1]),
    By=2*(3*C[1][1] - 6*C[2][1] + 3*C[3][1]),
    Cy=(3*C[2][1] - 3*C[3][1]),
    getPoint=function(t){
        var B0=B[0](t),
            B1=B[1](t),
            B2=B[2](t),
            B3=B[3](t),
            x = pA[0]*B0 + cA[0]*B1 + cB[0]*B2 + pB[0]*B3,
            y = pA[1]*B0 + cA[1]*B1 + cB[1]*B2 + pB[1]*B3,
            t2=t*t,
            mx= t2*Ax + t*Bx + Cx,

            my= t2*Ay + t*By + Cy;
        return [x,y,t,mx,my];
    };
    return getPoint;
}

No hay comentarios.:

Publicar un comentario