Ta reda på i vilken punkt två linjer skär varandra

Är objektet ifråga en punkt?
Är linjen ifråga en matematiskt riktig linje, eller har den två ändar?

Objektet är en punkt och linjen har två ändar :)

Här kommer en säkert väldigt opedagogisk lösning (men det är allt jag orkar göra nu :(). Jag får väl förklara senare, sorry.

p0 = punktens startposition vid t=0
v = punktens rörelsevektor
t = tiden

x1,y1,x2,y2 = linjens två ändpunkter

P(t) är punktens position
P(t) = p0 + v * t

Linjens ekvation (se bild):
y = kx - kx1 + y1

Parameterform:
y = s
x = (s + kx1 - y1)/k

Slå ihop P(t) med denna ekvation på paramterform och se för vilket t som P(t) ligger på linjen.

Sätt in t i P(t) och se var på linjen punkten korsar.
Ligger denna position inom ändpunkterna så har du position och tid utlösta. I annat fall korsar ej punkten linjen.

EDIT: Blev inte så bra :( :(

Det känns som en väldigt bökig metod att programmera... Satt o tänkte så förut men kom inte på något sätt att göra det...

Hittade denna kod och den verkade fungera.... Men samtidigt visade det sig att det inte riktigt var en så bra lösning för det egentliga problemet... :l

function ClosestSegmentPoint(P: TVector; S: TSegment): TVector;
var
  v, w : TVector;
  c1, c2, b : Double;
begin
  v := VectorSub(S.P1, S.P0);
  w := VectorSub(P, S.P0);

  c1 := Dot(w,v);
  if ( c1 <= 0 ) then
  begin
    Result := S.P0;
    Exit;
  end;

  c2 := Dot(v,v);
  if ( c2 <= c1 ) then
  begin
    Result := S.P1;
    Exit;
  end;

  b := c1 / c2;
  Result := VectorAdd(S.P0, VectorMultiply(v, b));
end;

Om jag får ta och expandera lite på vad Sang-drax sa...

Antag att segment 1 har ändar vid (a, b) och (c, d), och att segment 2 har ändar vid (i, j) och (m, n). Nu skiter vi i att de bara är linjesegment, och tänker oss att de är riktiga linjer.

Segment 1 har då "ekvationen"

y = (b - d)/(a - c)x + c(d - b)/(a - c) + d.

Segment 2 har ekvationen

y = (j - n)/(i - m)x + m(n - j)/(i - m) + n.

(Fy fan ;)). När/om de skär varandra är

(b - d)/(a - c)x + c(d - b)/(a - c) + d = (j - n)/(i - m)x + m(n - j)/(i - m) + n.

Låter vi ett lämpligt datorprogram lösa ut x, får vi

x = (a(d(i - m) - in + jm) - c(b(i - m) - in + jm))/(a(j - n) + b(m - i) + c(n - j) + d(i - m)).

och sätter vi in detta i nån av linjernas ekvationer, får vi att

y = (d - b)(c(j - n) + d(m - i) + in - jm)/(a(j - n) + b(m - i) + c(n - j) + d(i - m)) + d

På så sätt kan man beräkna eventuella skärningspunkter. Man måste dock kolla att det som står under bråkstrecket inte är noll, dvs att

a(j - n) + b(m - i) + c(n - j) + d(i - m) != 0.

Är detta 0 så skär linjerna varandra inte alls, eller så är de parallella och ligger "på varandra".

Så, nu måste man bara kolla om skärningspunkten ligger i rätt intervall (alltså att den ligger på båda segmenten), det görs väl lättast genom en massa ifsatser:

if( (x >= a && x <= c) || (x >= c && x <= a) )
{
	if( (y >= b && y <= d) || (y >= d && y <= b) )
	{
		// gör samma sak för andra segmentet
	}
}

Ganska fult dock :P

Har du rutiner för beräkning av matrisinverser och matrisprodukter så kan man göra detta på ett lite finare sätt...

Muzzafarath skrev:

Segment 1 har då "ekvationen"

y = (b - d)/(a - c)x + c(d - b)/(a - c) + d.

Nästan...
k = (b-d)/(a-c)
Tvåpunktsformeln:
y - d = k(x - a) <=>
y = kx - kc + d

Vadå nästan? Du har ju skrivit exakt samma sak som jag. Sätt in vad k är och förenkla så ser du att uttrycken är likadana. Det som kanske är lite "förvirrande" är att jag har ett plustecken framför min "term med c" (alltså c(d - b)/(a - c)), och därmed är ordningen på termerna i den övre parentesen (den där (d - b)) omvänd.

Ja, det är bara jag som är förvirrad.