2 Doğrunun Kesişim Noktası (Line-Line Intersection)

Sanırım basit gibi görünen fakat ilk defa karşılaşanlar için basit olmayan hesaplamalardan biridir bu. İki doğrunun kesişim noktasını farklı yollardan hesaplayabiliriz. Bunu doğru denklemi yöntemiyle yapanlar var, mümkün ve mantıklı bir yaklaşım. Trigonometrik işlemlerle yapanlar var ki eskiden bunlardan biri bendim; optimizasyona önem veriyorsanız ve pratik bir çözüm arıyorsanız tavsiye etmiyorum. Biz bunu vektör hesaplamalarıyla gayet temiz ve optimize bir şekilde yapacağız.

Şimdi öncelikle d1 ve d2 adında 2 tane vektörümüz olsun. Kesişim noktamız da P olsun.

Şimdi burada amacımız P noktasını bulabilmek. Öncelikle bu doğrularımızın noktalarını tanımlayalım.

Şimdi bu noktalarla ihtiyacımız olan V1 ve V2 vektörlerini tanımlayalım.

var v1=new vec2(P2.x-P1.x,P2.y-P1.y);
var v2=new vec2(P4.x-P3.x,P4.y-P3.y);

Şimdi öncelikle P1 noktasından P3 noktası yönünde bir vektör tanımlayacağız.

var v3=new vec2(P3.x-P1.x,P3.y-P1.y);

Gözünüzde şu şekilde canlandırabilirsiniz.

Şimdi yapacağımız şey şu, V3 'den V2’ye dikey nokta çarpımı (Per Dot Product) yapacağız.

var pdot_v3_to_v2=(V3.x*V2.y)-(V3.y*V2.x);

Yapmaya çalıştığımız şeyi görselleştireyim;

Şimdi V3 vektörünü V2 vektörünün normaline yansıttık. Şimdi V1’den V2’ye dikey nokta çarpımı yapacağız;

var pdot_v1_to_v2=(V1.x*V2.y)-(V1.y*V2.x);

Şimdi şuana kadar yaptıklarımızı görsel olarak anlatmaya çalışırsak şöyle bir sonuç elde ediyoruz;

Hedeflediğimiz şeyi anlatmam gerekirse;

Not: Aslında sözkonusu büyüklükleri tam anlamıyla bulmuyoruz, oranları buluyoruz. İzdüşümlerin büyüklüklerini tam öğrenmek istiyorsanız dikey nokta çarpım ile bulduğumuz değerle izdüşüm yaptığımız vektörün büyüklüğüne bölmeniz gerekiyor. Bunu daha iyi anlamak istiyorsanız Dikey nokta çarpım konusundaki yazımı tekrardan gözden geçirin.

Evet geriye kalan tek şey bu yaptığımız izdüşümlerin oranı ile vektörlerin kesişim noktasını bulabilmek. Biz bu orana t ismini verelim.

var t=pdot_v3_to_v2/pdot_v1_to_v2;

Şimdi kesişim noktasını buluyoruz;

var P=new vec2(0,0);
P.x=P1.x+v2.x*t;
P.y=P1.y+v2.y*t;

Burada yaptığımız şey, P1 noktasını referans alarak, V1 vektörünün kordinatlarıyla bulduğumuz oranı çarpıyoruz. Şöyle hayal edin, P1 noktasından V1 vektörünün t oranı kadar V1 vektörü yönü boyunca ilerliyoruz ve orada duruyoruz, bu nokta bizim kesişim noktamızı veriyor.

Yaptığım örnek uygulama;

Bu kadar uzun uzun anlattım, biraz da mantığı kavrayabilmeniz için fakat uygulamada yazdığım kodlar bundan ibaret;

//Vec2 yada türevi bir nesnenizin olduğunu farzediyorum
var v1=p2.subtract(p1);
var v2=p4.subtract(p3);

//p1'den p3'e vektor
var v3=p3.subtract(p1);
//p3'den p1'e vektor
var v4=p1.subtract(p3);

//perp ile hedef 2 vektörde dik projeksiyon yapılır, oranlar alinir
var t=perp(v3,v2)/perp(v1,v2);
var u=perp(v4,v1)/perp(v2,v1);


if((t<0 || t>1) || (u<0 || u>1) || t==0)return; //kesisim arasında degil, kesisme yok

//kesisme noktasi bulunur
var ip=new vec2(p1.x+v1.x*t,p1.y+v1.y*t);
var g1=new guide_point(ip,c_red);

Dikkat ederseniz yazdığım kodlarda size anlattıklarımdan fazlası bile var. bu kodla sadece kesişim noktasını bulmuyoruz, kesişim olup olmadığını da kontrol ediyoruz. Yaptığımız bu izdüşüm hesaplamasının ve t oranlamasını benzerini 2. vektörden 1. vektöre yapıyoruz. Buna da u ismini veriyoruz.

Bunun için t ve u oranının 0 dan küçük, 1 den büyük olamayacağı koşulunu ortaya koyuyoruz. Bu koşulun ne demek istediği çok açık, t ve u oranları aslında hedef vektör parçamızın kesişim yaptığı yerle vektörün tamamı arasında olan bir orandır. Bu oran vektörün tamamından büyük, yada vektörün 0 noktasından küçük olamaz diyoruz.

Sonuç

Çarpışma simülasyonlarından, mermi fiziklerine ve daha birçok konuda ihtiyacınız olacak doğru-doğru çarpışmaları için bu metod umarım size yardımcı olacaktır. Yorumlarınızı da ihmal etmeyin, bu tarz şeylerle ilgili düşünceleri okumaktan keyif alırım.