Hajsza az idővel – vektormetszéspont számoló algoritmusok

Vektorok metszéspontjait nagyon sokféleképpen lehet számolni, mi a két leglogikusabb változattal foglalkozunk. Az egyik módszer a normálos-vektoriális szorzatos ( per product ), a másik pedig az egyenes metszéspontos lesz. Kíváncsi voltam, hogy melyik hatákonyabb, hiszen olyan programnál, ahol minden pillanatban vektorok százait kell vizsgálni egyáltalán nem mindegy a sebesség. Meg amúgy sem.

A vektoriális-szorzatos módszer a következő: van két vektorunk v1 és v2. Létrehozunk egy harmadik vektort a két vektor kezdőpontjai között, és vesszük a vektorok normáljainak és a második vektor ( amire vizsgáljuk a metszést ) vektoriáis szorzatát. Ekkor két skalárt kapunk, melyek hányadosa az az arányszám, amivel többszörözve az első vektort megkapjuk a metszéspontot. Bonyolultan hangzik, és az is, már csak ezért nem tetszett már az elején sem ez a módszer :)

v1 ( bx1 , by1 );
v2 ( bx2 , by2 );
v3 ( bx3 , by3 );

n1 ( -by1 , bx1 );
n3 ( -by3 , bx3 );

dp1 = n3.v2 = -by3*bx2 + bx3*by2;
dp2 = n1.v2 = -by1*bx2 + bx1*by2;

rat = dp1/dp2;
crossv = v1*rat;

Ezzel megkapjuk a metszéspontot, de még nem tudjuk, hogy a pontot tartalmazza-e mindkét vektor.

A másik megoldás, amikor a két vizsgált vektorból egyenest csinálunk, és az ő metszéspontjaikat keressük meg az egyenletükből.

v1 ( bx1 , by1 );
v2 ( bx2 , by2 );

l1: y1 = m1*x1 + b1;
l2: y2 = m2*x2 + b2;

Ahol metszi egymást a két egyenes:
x1 = x2;
y1 = y2;

tehát

y = m1*x + b1;
y = m2*x + b2;

egyenlővé téve őket

m1*x + b1 = m2*x + b2;
x*( m1 – m2 ) = b2 – b1;

x = ( b2 – b1 ) / ( m1 – m2 );
y = m1 * x + b1;

És meg is kaptuk a metszéspontot. Sajnos itt sem tudjuk még eldönteni, hogy tartalmazza-e mindkét vektor a pontot. Ezt legegyszerűbben úgy tudjuk meg, hogy a vektorok pontjai és a metszéspont között új vektorokat hozunk létre, és ha ezek hosszabbak az eredeti vektoroknál, akkor a pont nincs bennük. De mivel mindkét fenti esetben ugyanez az eljárás, ezért bele sem veszem a sebességvizsgálatomba.

Nézzük akkor a kódot. Kell először is egy vektor osztály.

//begin
//
//
package com.milgra.geometry
{
	//
	//
	//
	public class Vector
	{
		//
		//
		//
		public var bx:Number;
		public var by:Number;
		public var sx:Number;
		public var sy:Number;
		public var r:Number;
		//
		//
		//
		public function Vector ( stx:Number , sty:Number , enx:Number , eny:Number )
		{
			//
			sx = stx;
			sy = sty;
			bx = enx - stx;
			by = eny - sty;
			//
			r = Math.sqrt( bx*bx + by*by );
			//	
		}
		//
		//
		//
	}
	//
	//
	//
}
//
//
//end

Nem pusztán irányvektorokként kezelem a vektorokat, jegyzem a kezdőpontot is, és kiszámolom a hosszt is, mivel igen gyakran szükség van rá.

Szükségünk lesz egy osztályra, ami elvégzi a vizsgálatokat a vektorokon, ő lesz a VectorOperator.

//begin
//
//
package com.milgra.geometry
{
	//
	//
	//
	import flash.utils.*;
	import flash.geom.Point;
	import com.milgra.geometry.Line;
	//
	//
	//
	public class VectorOperator
	{
		//
		//
		//
		public function VectorOperator ( )
		{
			//
			addLog( "new VectorOperation" );
			//
		}
		//
		//
		//
		public function getPerIntersection ( v1:Vector , v2:Vector ):Point
		{
			//
			addLog( "VectorOperator.getPerIntersection" );
			//
			var v3bx:Number = v2.sx - v1.sx;
			var v3by:Number = v2.sy - v1.sy;
			var perP1:Number = v3bx*v2.by - v3by*v2.bx;
			var perP2:Number = v1.bx*v2.by - v1.by*v2.bx;
			var t:Number = perP1/perP2;
			//
			var cx:Number = v1.sx + v1.bx*t;
			var cy:Number = v1.sy + v1.by*t;
			//
			return new Point( cx , cy );
			//
		}

Itt nincsen semmi ördöngösség, a bevezetőben tárgyalt egyenleteket simán lepötyögtem.

		//
		//
		//
		public function getLineIntersection ( v1:Vector , v2:Vector ):Point
		{
			//
			addLog( "VectorOperator.getLineIntersection" );
			//
			var m1:Number = v1.by / v1.bx;
			var b1:Number = v1.sy - m1*v1.sx;
			var m2:Number = v2.by / v2.bx;
			var b2:Number = v2.sy - m2*v2.sx;
			//
			var cx:Number = ( b2 - b1 )/( m1 - m2 );
			var cy:Number = m1*cx + b1;
			//
			return new Point( cx , cy );
			//
		}
		//
		//
		//
		public function addLog( logText:String ):void
		{
			//
			//trace( logText );
			//
		}
		//
		//
		//
	}
	//
	//
	//
}
//
//
//end

Ezzel meg is volnánk, és mostmár csak egy keretprogram kell, ami létrehoz random vektorokat, és rájuk ereszti a két algoritmust. Töltsétek le a forrást, raktam bele még egy vektor-kirajzoló osztályt is, további érdekesség, hogy csináltam hozzá egy skint a Flash 9 preview-val, hogy szebb legyen a dolog.

Ezután futtatnunk kell, és nyomogatni a start gombot. Ha van kedvünk, belőhetjük a vektor és a metszéspont kirajzolást is true-ra állítva, de vigyázzunk, kb 5000 ciklus fölött már lefagyasztja a böngészőt. A következőket következtethetjük :)

– minden féle gépen és platformon tesztelve a vonalas algoritmus 15-20 százalékkal gyorsabb, néhány kivételtől eltekintve.
– érdemes próbálkozni a típusok elhagyásával mindkét függvényben, ez is jelentős sebességeltérést okozhat, érdekességképpen

A teszt megtekinthető itt

Forrás itt.

MilGra