Форум Flasher.ru - точка пересечения отрезков

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 1.0/2.0 (http://www.flasher.ru/forum/forumdisplay.php?f=93)

- - точка пересечения отрезков (http://www.flasher.ru/forum/showthread.php?t=90686)

точка пересечения отрезков

Пересекаются простые фигуры, точки пересечения находятся математически, однако это ведь формулы пересечения векторов и соответственно если отрезки не паралельны, то они все равно пересекаются. Как определяется принадлежность точки к отрезку, замучался совсем?
Простой пример:

Код:

var arr=[100, 100, 200, 200, 200, 100, 100, 200];

//[300, 100, 200, 200, 200, 100, 100, 200] прямые паралельны

this.lineStyle(2,0x00ff00,100)

this.moveTo(arr[0], arr[1]);

this.lineTo(arr[2], arr[3]);

this.lineStyle(2,0xff0000,100)

this.moveTo(arr[4], arr[5]);

this.lineTo(arr[6], arr[7]);

var A1=-(arr[3]-arr[1])

var B1=(arr[2]-arr[0])

var C1=(arr[3]-arr[1])*arr[0]-(arr[2]-arr[0])*arr[1]

var A2=-(arr[7]-arr[5])

var B2=(arr[6]-arr[4])

var C2=(arr[7]-arr[5])*arr[4]-(arr[6]-arr[4])*arr[5]

var X = -(C1*B2-C2*B1)/(A1*B2-A2*B1)

var Y =(A2*C1-A1*C2)/(A1*B2-A2*B1)

//A1*x+B1*y+C1=0 и A2*x+B2*y+C2=0

//если прямые не паралельны все равно трейсить будет 0

trace(A1*X+B1*Y+C1)

trace(A2*X+B2*Y+C2)

this.attachMovie("tochka","toch_mc",1,{_x:X;_y:Y})

проверь если допустим Х точки пересечения не больше максимума из Х-ов и не менее минимума отрезков и У

//Функция, которая проверяет пересечение двух линий>>>>---------------------------

Код:

function Peresechenie(x11,y11,x12,y12,x21,y21,x22,y22 : Number) : Number {

var s,xx,yy,t1,t2,t : Number = null;

var D,D1,D2 : Number = null;

s=0;

D=(y12-y11)*(x21-x22)-(y21-y22)*(x12-x11);

D1=(y21-y11)*(x21-x22)-(y21-y22)*(x21-x11);

D2=(y12-y11)*(x21-x11)-(y21-y11)*(x12-x11);

if (D<>0){

        t1=D1/D;

        t2=D2/D;

        if ((t1<=1) && (t1>=0) && (t2>=0) && (t2<=1)){

                s=1;

                xx=x11+(x12-x11)*t1;

                yy=y11+(y12-y11)*t1;

        }

}else {        

        if ((D1==0) && (D2==0)){

                if (x11<>x12){

                        t1=(x21-x11)/(x12-x11);

                        t2=(x22-x11)/(x12-x11);

                }else{

                        if (y11<>y12){

                                t1=(y21-y11)/(y12-y11);

                                t2=(y22-y11)/(y12-y11);

                        }

                }

                if (t1>t2){

                        t=t2;

                        xx=x21;

                        yy=y21;

                        t2=t1;

                        x21=x22;

                        y21=y22;

                        t1=t

                        x22=xx;

                        y22=yy;

                }

                if (t1<0){                        

                        if (t2>=1){

                                s=2;

                        }else{

                                if (t2>0){

                                        s=2;

                                        x12=x22;

                                        y12=y22;

                                }else{

                                        if (t2==0){

                                                s=1;

                                                xx=x11;

                                                yy=y11;

                                        }

                                }

                        }

                }else{

                        if (t1<=1){

                                if (t1==1){

                                        s=1;

                                        xx=x12;

                                        yy=y12;

                                }

                                else{

                                        s=2;

                                        x11=x21;

                                        y11=y21;

                                        if (t2>=1){

                                                x12=x22;

                                                y12=y22;

                                        }

                                }

                        }

                }

        }        

}

        return s;

}

x11,y11,x12,y12,x21,y21,x22,y22 - координаты отрезков, если return s != 0, то значит пересекаются или один отрезок продолжает другой. Ну потесть и все понятнро будет, s может только трем значения равняться 0,1,2

немножко больше букв надо для строгого синтаксиса:

Код:

function Peresechenie(x11:Number, y11:Number, x12:Number, y12:Number, x21:Number, y21:Number, x22:Number, y22:Number) : Number {...}

И вместо "<>" стоит писать "!="

Спасибо, буду мудрить

вот, нашел:

Код:

// уравнение прямой

function findABC(x1, y1, x2, y2){

        var dx = x2-x1, dy = y2-y1;

        return {a:dx, b:dy, c: x1*dy - y1*dx };        

}



// проверка на пересечение

function checkIt( x1, y1, x2, y2, x3, y3, x4, y4 ){



var line1 = findABC(  x1, y1, x2,  y2 );

var line2 = findABC(  x3, y3, x4,  y4 );



var det = line1.a*line2.b - line2.a*line1.b;



 // параллельны?

if (det == 0) return null;



// точка пересечения

var y0 = (line1.b*line2.c - line2.b*line1.c)/det;

var x0 = (line1.a*line2.c - line2.a*line1.c)/det;



// а лежит она на отрезках?

var XS  = ( x1 == x2 ) ? true : ( ( x1 > x2 ) ? ( x1 > x0) && (x0 > x2) :  ( x1 < x0) && ( x0 < x2 ) );

var XS2 = ( x3 == x4 ) ? true : ( ( x3 > x4 ) ? ( x3 > x0) && (x0 > x4) :  ( x3 < x0) && ( x0 < x4 ) );

var YS  = ( y1 == y2 ) ? true : ( ( y1 > y2 ) ? ( y1 > y0) && (y0 > y2) :  ( y1 < y0) && ( y0 < y2 ) );

var YS2 = ( y3 == y4 ) ? true : ( ( y3 > y4 ) ? ( y3 > y0) && (y0 > y4) :  ( y3 < y0) && ( y0 < y4 ) );



if(XS && XS2 && YS && YS2) return { x:x0, y:y0 };

else return null;

}

способ проверки, попадает ли точка на отрезок, мягко говоря туповат..

вроде так работает:

Код:

var XS  =  ( x1 >= x0 ) === ( x0 >= x2 );

var XS2 =  ( x3 >= x0 ) === ( x0 >= x4 );

var YS  =  ( y1 >= y0 ) === ( y0 >= y2 );

var YS2 =  ( y3 >= y0 ) === ( y0 >= y4 );

upd: исправил, спасибо Futs

Цитата:

Сообщение от Kikasso

вроде так работает:

Код:

var XS  =  ( x1 >= x0 ) === ( x0 >= x2 );

var XS2 =  ( x3 >= x0 ) === ( x0 >= x4 );

var YS  =  ( y1 >= y0 ) === ( y0 >= y2 );

var YS2 =  ( y3 >= y0 ) === ( y3 >= y4 );

y3 - ошибка?
Сделал для наглядности пример, а то проект у меня очень большой, я проверял почти также и как у тебя, не во всех случаях работает

Код:

var tochka:MovieClip = _root.createEmptyMovieClip("tochka", _root.getNextHighestDepth());

tochka.lineStyle(1, 0x0000ff, 100);

tochka.moveTo(-5,0)

tochka.lineTo(5,0)

tochka.moveTo(0,-5)

tochka.lineTo(0,5)

var par1:MovieClip = _root.createEmptyMovieClip("par1_mc", _root.getNextHighestDepth());

par1._x = 200;

par1._y = 200;

par1.point = {x1:0, y1:0, x2:100, y2:0, x3:75, y3:100, x4:25, y4:100};

par1.lineStyle(2, 0x00ff00, 100);

par1.beginFill(0x00ff00, 30);

par1.moveTo(par1.point.x1, par1.point.y1);

par1.lineTo(par1.point.x2, par1.point.y2);

par1.lineTo(par1.point.x3, par1.point.y3);

par1.lineTo(par1.point.x4, par1.point.y4);

par1.lineTo(par1.point.x1, par1.point.y1);

par1.endFill();

var par2:MovieClip = _root.createEmptyMovieClip("par2_mc", _root.getNextHighestDepth());

par2._x = 150;

par2._y = 150;

par2.point = {x1:0, y1:0, x2:-100, y2:0, x3:-75, y3:-100, x4:25, y4:-100};

par2.lineStyle(2, 0xff0000, 100);

par2.beginFill(0xff0000, 30);

par2.moveTo(par2.point.x1, par2.point.y1);

par2.lineTo(par2.point.x2, par2.point.y2);

par2.lineTo(par2.point.x3, par2.point.y3);

par2.lineTo(par2.point.x4, par2.point.y4);

par2.lineTo(par2.point.x1, par2.point.y1);

par2.endFill();

par1.onPress = function() {

        this.startDrag();

};

par1.onRelease = function() {

        this.stopDrag();

        checkIt(this, par2);

};

function checkIt(par1, par2) {

        var myPoint1:Object = {x:0, y:0};

        par1.localToGlobal(myPoint1);

        var myPoint2:Object = {x:0, y:0};

        par2.localToGlobal(myPoint2);

        for (var i1 = 1; i1<=4; i1++) {

                var i2:Number = i1+1;

                if (i2 == 5) {

                        i2 = 1;

                }

                var dgx:Number = (myPoint1.x+par1.point["x"+i2])-(myPoint1.x+par1.point["x"+i1]);

                var dgy:Number = (myPoint1.y+par1.point["y"+i2])-(myPoint1.y+par1.point["y"+i1]);

                var c1:Number = ((myPoint1.x+par1.point["x"+i1])*dgy)-((myPoint1.y+par1.point["y"+i1])*dgx);

                //

                var toch1Xmin:Number = myPoint1.x+par1.point["x"+i1];

                var toch1Xmax:Number = myPoint1.x+par1.point["x"+i2];

                var toch1Ymin:Number = myPoint1.y+par1.point["y"+i1];

                var toch1Ymax:Number = myPoint1.y+par1.point["y"+i2];

                for (var j1 = 1; j1<=4; j1++) {

                        var j2:Number = j1+1;

                        if (j2 == 5) {

                                j2 = 1;

                        }

                        var dsx:Number = (myPoint2.x+par2.point["x"+j2])-(myPoint2.x+par2.point["x"+j1]);

                        var dsy:Number = (myPoint2.y+par2.point["y"+j2])-(myPoint2.y+par2.point["y"+j1]);

                        var c2:Number = ((myPoint2.x+par2.point["x"+j1])*dsy)-((myPoint2.y+par2.point["y"+j1])*dsx);

                        var det:Number = dsx*dgy-dgx*dsy;

                        //

                        var toch2Xmin = myPoint2.x+par2.point["x"+j1];

                        var toch2Xmax = myPoint2.x+par2.point["x"+j2];

                        var toch2Ymin = myPoint2.y+par2.point["y"+j1];

                        var toch2Ymax = myPoint1.y+par2.point["y"+j2];

                        //

                        if (det != 0) {

                                var X = -(c2*dgx-c1*dsx)/det;

                                var Y = (dsy*c1-dgy*c2)/det;

                                var XS = (toch1Xmin>=X) === (X>=toch1Xmax);

                                var XS2 = (toch2Xmin>=X) === (X>=toch2Xmax);

                                var YS = (toch1Ymin>=Y) === (Y>=toch1Ymax);

                                var YS2 = (toch2Ymin>=Y) === (Y>=toch2Ymax);

                                //

                                if (XS && XS2 && YS && YS2) {

                                        trace("X="+X);

                                        trace("Y="+Y);

                                        var myPoint:Object = {x:X, y:Y};

                                        tochka.duplicateMovieClip("toch_mc"+i1+"_"+j1, _root.getNextHighestDepth(), {_x:myPoint.x, _y:myPoint.y});

                                }

                        }

                }

        }

}

Думаю, что дело в том что toch1Xmin может быть больше toch1Xmax, т.е. их надо сначала проверять и если надо менять местами.

В том-то и дело. в 6-м посте все работает, именно по такому принципу.
В 7-м принцип такой: если точка попала на отрезок, то либо оба true либо оба false, после сравнения получается true.
кстати toch1Xmin может быть и равен toch1Xmax, это учтено.
Тут лучше юзать flash.geom.Point, кстати.
Уравнения прямых я брал из справочника по математике, точка пересечения нашлась вычислением матрицы.

Вот, смотри в аттаче - все работает.

Вот я и удивляюсь, если использовать данный код в первом посте (для двух отрезков) то все работает, а для фигур глючит.

Наверное клип в клипе и поворот до кучи. Волшебное слово localToGlobal ты знаешь. duplicateMovieClip не есть хорошо, attachMovie куда лучше. Попробуй все упростить.

duplicateMovieClip я использовал для наглядности, а повот до кучи у меня в проекте есть, запарился совсем, никак не могу понять. Расчеты ведь правильные, если убрать проверку на принадлежность к отрезку, клипы аттачатся правильно, траблы с проверкой. Кстати если нарисовать в примере квадраты, то вообще фигня...

Нашел проблему в моем примере ошибка вместо

Код:

var toch2Ymax = myPoint1.y+par2.point["y"+j2];

надо 

var toch2Ymax = myPoint2.y+par2.point["y"+j2];

тогда все работает, буду искать в своем проекте.
P.S. Убил зря два дня