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

[Futs]

Пересекаются простые фигуры, точки пересечения находятся математически, однако это ведь формулы пересечения векторов и соответственно если отрезки не паралельны, то они все равно пересекаются. Как определяется принадлежность точки к отрезку, замучался совсем?
Простой пример: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})

[CorC]

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

[petrochenko1981]

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

[Kikasso]

немножко больше букв надо для строгого синтаксиса:
function Peresechenie(x11:Number, y11:Number, x12:Number, y12:Number, x21:Number, y21:Number, x22:Number, y22:Number) : Number {...}
И вместо "<>" стоит писать "!="

[Futs]

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

[Kikasso]

вот, нашел:
// уравнение прямой
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;
}
способ проверки, попадает ли точка на отрезок, мягко говоря туповат..

[Kikasso]

вроде так работает: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

[Futs]

вроде так работает: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, т.е. их надо сначала проверять и если надо менять местами.

[Kikasso]

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

[Kikasso]

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

[Futs]

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

[Kikasso]

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

[Futs]

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

[Futs]

Нашел проблему в моем примере ошибка вместо var toch2Ymax = myPoint1.y+par2.point["y"+j2];
надо
var toch2Ymax = myPoint2.y+par2.point["y"+j2]; тогда все работает, буду искать в своем проекте.
P.S. Убил зря два дня