Matte - Finne skjæringspunkt til to linjer

[Jonas]

Hei!

 

Jeg prøver fortiden å lage et simpelt 3D bilspill. Har det meste på plass, men det er noe med map-renderinga jeg ikke helt for til. Banen er nemlig definert som en lang liste med punkter, som danner en lang linje. Jeg får til å tegne parallelle linjer og dermed "utvide" banen fra 1px tykk, men som man ser på dette bildet har jeg et problem.

 

 

Parallell-linjene til midtlinjen treffer ikke hverandre i yttersiden og krysser hverandre på innersiden. Hvordan kan jeg finne krysningspunktet til to linjer, utifra 2 * 2 XY kordinater?

 

Har lagt med et vedlegg, med en funksjon hvor det kun mangler en formel. (Merk - vedlegge er ikke helt i tråd med hva jeg beskriver, men formellen for krysningspunkt er fortsatt den samme)

 

Takk for hjelp!

 

- Jonas

 

(Rename *.txt til *.rar)

 

Edit: Jeg mener å tro at jeg fikk det til! Løsningen var å finne et funksjonsuttrykk for begge linjene og sette opp en likning for å sjekke når begge krysset hverandre. At jeg ikke tenkte på det med en gang.

3.txt

Endret 8. desember 2006 av Jonas

[aadnk]

Du må benytte regresjon til å beregne de to linjenes funksjoner for å kunne finne ut hvor de møtes. Men først, la oss definere informasjonen vi vil beregne til følgende UDT'er:

' Beskriver en linje

Private Type LineSegment

    X1 As Single

    Y1 As Single

    X2 As Single

    Y2 As Single

End Type

 

' Beskriver linjefunksjonen Y = ax + b

Private Type LineFunction

    A As Single

    B As Single

End Type

 

' Maksimumverdien for Single. Brukes når teller er null.

Const MaxValue As Single = 3.4028235E+38

Den fullstendige linje et linjestykke danner kan vi beskrive med følgende funksjon:

 

A kan ennvidere beregnes ved å bruke linjens tangent:

 

Når vi har A, kan vi subtrahere Y med ax og få b:

 

Dette kan vi implementere eksempelvis slik:

' Hjelpefunksjon.

Private Function CreateSegment(X1 As Single, Y1 As Single, X2 As Single, Y2 As Single) As LineSegment

 

    ' Setter variabler

    With CreateSegment

        .X1 = X1

        .Y1 = Y1

        .X2 = X2

        .Y2 = Y2

    End With

 

End Function

 

' Kalkulerer ax + b for en linje.

Private Function LinReg(Line As LineSegment) As LineFunction

 

    ' Kalkuler tangenten. Dette tilsvarer a.

    If Line.X1 - Line.X2 = 0 Then

        ' Telleren kan såklart ikke være null, men utregningen krever vi definerer en funksjon for linjen.

        ' Det nærmeste vi kommer til en rett linje i Y-aksen er ved å sette A til et meget høyt tall.

        LinReg.A = MaxValue / 1000

    Else

        LinReg.A = (Line.Y1 - Line.Y2) / (Line.X1 - Line.X2)

    End If

   

    ' Ved å subtrahere y med ax for det første punktet, får vi b.

    LinReg.B = Line.Y1 - (Line.X1 * LinReg.A)

   

End Function

Posisjonen der disse to linjene møtes, etter vi har beregnet deres funksjon, kan skrives som følger:

 

Dette omformer vi:

 

Og vi får følgende funksjon:

' Returnerer X- og Y-posisjonen der to linjer møtes.

Private Function Intercept(Line1 As LineSegment, Line2 As LineSegment) As LineSegment

 

    Dim f(1) As LineFunction, X As Double

 

    ' Beregn regresjon for begge linjene

    f(0) = LinReg(Line1)

    f(1) = LinReg(Line2)

   

    ' Regn ut X-posisjonen der linjene møter hverandre

    X = (f(1).B - f(0).B) / (f(0).A - f(1).A)

   

    ' Y-posisjonen får vi ved å fylle den inn i den første funksjonen

    With Intercept

        .X1 = X

        .Y1 = (f(0).A * X) + f(0).B

    End With

 

End Function

Jeg har også laget et lite prosjekt som viser disse funksjonene i aksjon. Det burde iallfall være en smal sak å få implementert i ditt spill. Lykke til.

 

Edit: Fikset kodevisning.

Line_regression.zip

Endret 8. desember 2006 av aadnk

[Jonas]

Takk, det ga meg et par ideer!

Dette ble resultatet, om noen skulle være interessert.

 

(Rename *.txt til *.rar)

4.txt