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

Futs · 16.01.2007, 17:33

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

Код:

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 · 16.01.2007, 18:21

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

petrochenko1981 · 16.01.2007, 18:38

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

Код:

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 · 16.01.2007, 19:00

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

Код:

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

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

Futs · 16.01.2007, 19:10

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

Kikasso · 16.01.2007, 19:46

вот, нашел:

Код:

// уравнение прямой
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 · 16.01.2007, 20:35

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

Код:

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 · 17.01.2007, 14:43

Цитата:

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

Kikasso · 17.01.2007, 15:28

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

Kikasso · 17.01.2007, 15:38

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