TrianglesOverlap - kahden kolmion törmäystunnistus

Oletko tehnyt jotain, mistä muut voisivat hyötyä. Postita vinkit tänne.
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 8:49 pm

TrianglesOverlap - kahden kolmion törmäystunnistus

Post by Alligaattori »

Terve kaikki!

Pitkästä aikaa kaivoin koneeni uumenista CoolBasicin saatuani idean kolmioiden törmäystunnistuksesta. Parin päivän bugijahdin jälkeen sain yksinkertaisen systeemin valmiiksi: funktio testaa täysin matemaattisesti, ovatko kaksi mielivaltaisen kokoista tasasivuista kolmiota päällekkäin. Viritys on vain vähän optimoitu rekursiivinen purkkapallo, mutta toimiva. Tulevaisuudessa yritän saada funktion testaamaan mitä tahansa kolmioita. Tätä saa kuka tahansa vapaasti optimoida (sopii ottaa selvää :P ) ja käyttää peleissään, mutta pelien krediiteissä olisi hyvä CB-foorumin nimeni mainita.

Mihin tätä voi edes käyttää? Kai sille jotain käyttöä löytyy, esimerkiksi jossain Gigabotin tapaisessa pelissä voivat robotit olla ylhäältä katsoen kolmioita.

Funktion käyttöohjeet:
Jos et tiedä mitä teet, kutsu
TrianglesOverlap(x1,y1,r1,a1,x2,y2,r2,a2)
jossa
xN,yN = kolmion N keskipisteen koordinaatit
rN = kolmion N keskipisteen ja kärjen etäisyys
aN = kolmion N pyörityskulma

Muita funktion parametreja, joita käytetään rekursioissa, ei käyttäjän tarvitse tietää. Voin kertoa ne, jos jotakuta kiinnostaa.

Esimerkki:

Code: Select all

// korjauksessa (saattaa tulla takaisin)
  
Itse funktio:

Code: Select all

// korjauksessa (saattaa tulla takaisin)
  
Kommenttia ja parannusehdotuksia saa antaa.

EDIT: olin siivotessani poistanut tärkeän tarkistuksen. Vanha versio jakoi nollalla, jos käänsi kolmion oikeaan asentoon.

EDIT2: Lisää säätöä. Nyt saattaa toimia nopeammin, mutta ei välttämättä aina samalla nopeudella.

EDIT3: Paha aukko löytyi! Korjaan ja optimoin ennen kuin saatte koodit takaisin.
Last edited by Alligaattori on Tue Mar 17, 2009 9:29 pm, edited 4 times in total.
Jani
Devoted Member
Posts: 741
Joined: Fri Oct 31, 2008 4:53 pm

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Post by Jani »

Katsoin tuota koodia ja huomasin erään asian; kun palautat result-muuttujan, käytät ennen sitä kahta Not-komentoa.
Ja 2 Not-komentoa kumoavat toisensa. Muuten vaikutti kätevältä.
Dead men tell no tales. Also, Python rocks!
Codegolf: 99 bottles of beer (oneliner) - Water map partition
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 8:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori »

Asia on niin, että result on kokonaisluku väliltä 0...12 ja kahden not-komennon käytön jälkeen se on joko 0 tai 1. Jos resultissa on nollasta poikkeava luku, palautetaan yksi, muuten nolla.
otto90x
Advanced Member
Posts: 349
Joined: Mon Aug 27, 2007 9:00 pm
Location: Lapinjärvi, Finland
Contact:

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by otto90x »

Ei tämä nyt ihan toimiva ole. Itse tarkastaisin kolmioiden päällekäisyyden tähän funktioon ja etäisyyteen perustuvaan läheisyystarkistukseen nojautuen. EDIT: Ja tämä tosiaan on funktio joka kertoo josko janat leikkaavat toisensa.

Code: Select all

Function Lines_Intersect(Ax#, Ay#, Bx#, By#, Cx#, Cy#, Dx#, Dy#)

   Rn# = (Ay#-Cy#)*(Dx#-Cx#) - (Ax#-Cx#)*(Dy#-Cy#)
   Rd# = (Bx#-Ax#)*(Dy#-Cy#) - (By#-Ay#)*(Dx#-Cx#)

   If Rd# = 0
       Return False    
   Else
       Sn# = (Ay#-Cy#)*(Bx#-Ax#) - (Ax#-Cx#)*(By#-Ay#)
       Intersection_AB# = Rn# / Rd#
       Intersection_CD# = Sn# / Rd#        
       If Intersection_AB#>1 Or Intersection_CD#>1 Or Intersection_AB#<0 Or Intersection_CD#<0 Then Return False
       IntersX = Ax# + Intersection_AB#*(Bx#-Ax#)
       IntersY = Ay# + Intersection_AB#*(By#-Ay#)    
       Return True        
   EndIf

End Function
Otto Martikainen a.k.a. MetalRain, otto90x, kAATOSade.
Runoblogi, vuodatusta ja sekoiluja.
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 8:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori »

Oho, olin poistanut vähän tarkisteluja siivotessani funktiota. Nyt pitäisi toimia taas.
Jonhu
Active Member
Posts: 186
Joined: Mon Aug 04, 2008 5:45 pm

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Post by Jonhu »

Tässä vielä monikulmioiden (mukaanlukien kolmio) päällekkäinolotunnistus..

Code: Select all

ShowMouse OFF

Repeat
    angle+1
    
    // merkataan kuvion pisteet
    // TurnDots(muistipala, keskipisteX, keskipisteY, halkasija, kulma, kulmia)
    mem1 = TurnDots(mem1,100,100,150,angle,5)
    mem2 = TurnDots(mem2,MouseX(),MouseY(),70,-angle,3)
    
    // tarkistetaan ovatko päällekkäin
    If KuviotOverlap(mem1,mem2) = 1 Then Color cbred
    
    //piirretään kuviot
    mem1 = DrawKulmio(mem1)
    mem2 = DrawKulmio(mem2)
    
    Color cbwhite
    Text 10,10,"FPS: "+FPS()
    
    DrawScreen

Forever


// Laskee minimi etäisyydenkuvion keskeltä sen reunaan 
Function MinDist(koko#,kulmia)
    alfa# = ( 360.0 / kulmia ) / 2.0
    Dist# = ( koko# / 2.0 ) / Cos( alfa# )
    Return Dist#
EndFunction

// piirretään kuvio
Function DrawKulmio(mem)
    kulmia = ( MEMBlockSize(mem) - 17 ) / 8
    For a = 0 To kulmia - 1
        If a = kulmia - 1 Then n = 0 Else n = a + 1
        Line PeekInt( mem, n * 4 ), PeekInt( mem, ( n + kulmia ) * 4 ),PeekInt( mem, a * 4 ), PeekInt( mem, ( a + kulmia ) * 4 )
    Next a    
    Return mem
EndFunction


Function TurnDots(mem, kx#, ky#, koko#, ang#=0, kulmia=3)
    If mem=0 Then mem = MakeMEMBlock( 4 * (kulmia*2) + 17 )
    
    For a=0 To (kulmia)-1
        PokeInt mem, a*4, kx# + Cos(a * (360 / kulmia) + ang#) * (koko#/2.0)
        PokeInt mem, (a+kulmia)*4, ky# - Sin(a * (360 / kulmia) + ang#) * (koko#/2.0)
    Next a
    
    // lisätään koko yms tiedot vielä muistiin
    PokeFloat mem, MEMBlockSize(mem)-17, kx#
    PokeFloat mem, MEMBlockSize(mem)-13, ky#
    PokeFloat mem, MEMBlockSize(mem)-9, koko#
    PokeFloat mem, MEMBlockSize(mem)-5, ang#
    
    Return mem
EndFunction

Function KuviotOverlap(mem1,mem2)

    mem_size1 = MEMBlockSize(mem1) 
    mem_size2 = MEMBlockSize(mem2) 
    kulmia1 = ( mem_size1 - 17 ) / 8
    kulmia2 = ( mem_size2 - 17 ) / 8
    koko1# = PeekFloat(mem1,mem_size1-9)
    koko2# = PeekFloat(mem2,mem_size2-9)
    
    // kuvioiden keskipisteiden etäisyys toisitaan
    Distan# = Distance( PeekFloat(mem1,mem_size1-17), PeekFloat(mem1,mem_size1-13), PeekFloat(mem2,mem_size2-17), PeekFloat(mem2,mem_size2-13))
    
    // jos ovat pakosti päällekkäin palautetaan 1
    If Distan# <= Max( MinDist(koko1#/2,kulmia1), MinDist(koko2#/2,kulmia2) ) Then Return True
    
    // jos on mahdollista olla päällekkäin
    If Distan# <= (koko1 + koko2) / 2.0 Then
        For a=0 To kulmia1-1
            For b=0 To kulmia2-1
                If a+1 > kulmia1-1 Then a1 = 0 Else a1 = a + 1
                If b+1 > kulmia2-1 Then b1 = 0 Else b1 = b + 1
                If Lines_Intersect( PeekInt( mem1, a * 4 ), PeekInt( mem1, ( a + kulmia1 ) * 4 ), PeekInt( mem1, a1 * 4 ), PeekInt( mem1, ( a1 + kulmia1 ) * 4 ), PeekInt( mem2, b * 4 ), PeekInt( mem2, ( b + kulmia2 ) * 4 ), PeekInt( mem2, b1 * 4 ), PeekInt( mem2, ( b1 + kulmia2 ) * 4 ) ) Then Return True
            Next b
        Next a
    EndIf
EndFunction


Function Lines_Intersect(Ax#, Ay#, Bx#, By#, Cx#, Cy#, Dx#, Dy#)

   Rn# = (Ay#-Cy#)*(Dx#-Cx#) - (Ax#-Cx#)*(Dy#-Cy#)
   Rd# = (Bx#-Ax#)*(Dy#-Cy#) - (By#-Ay#)*(Dx#-Cx#)

   If Rd# = 0
       Return False    
   Else
       Sn# = (Ay#-Cy#)*(Bx#-Ax#) - (Ax#-Cx#)*(By#-Ay#)
       Intersection_AB# = Rn# / Rd#
       Intersection_CD# = Sn# / Rd#        
       If Intersection_AB#>1 Or Intersection_CD#>1 Or Intersection_AB#<0 Or Intersection_CD#<0 Then Return False
       IntersX = Ax# + Intersection_AB#*(Bx#-Ax#)
       IntersY = Ay# + Intersection_AB#*(By#-Ay#)    
       Return True        
   EndIf

End Function
Tekeillä pikkupelejä ja ohjelmia :)
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 8:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori »

Eipä tullut mieleeni käyttää tässä kahden janan päällekkäisyyden tarkistusta. Olisi ollut varmasti nopeampi kuin minun viritykseni. Alkaa nyt tuntua karmealta purkalta. :D
User avatar
Ilmuri
Developer
Developer
Posts: 277
Joined: Sun Aug 26, 2007 2:46 pm
Location: \o

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Post by Ilmuri »

Janojen leikkaus-metodi ei tunnista sisäkkäisiä kolmioita.
CoolBasic henkilökuntaa
Kehittäjä
CoolBasic Classic
Jonhu
Active Member
Posts: 186
Joined: Mon Aug 04, 2008 5:45 pm

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Post by Jonhu »

Ilmuri wrote:Janojen leikkaus-metodi ei tunnista sisäkkäisiä kolmioita.
Sen takia tuossa on tämä functio, joka kertoo, että ovatko pakosti sisäkkäin..

Code: Select all

// Laskee säännöllisen kulmion keskipisteestä lyhimmän etäisyyden sen reunaan 
// halkasija = koko#       kulmia = kulmien lkm.
Function MinDist(koko#,kulmia)
    alfa# = ( 360.0 / kulmia ) / 2.0
    Dist# = ( koko# / 2.0 ) / Cos( alfa# )
    Return Dist#
EndFunction
Kuvioiden päällekkäinolotarkistukseen on monta eri tapoja toteuttaa. Aikaisemmin toteutin functiolla, joka katsoo kummalla puolella viivaa piste x,y sijaitsee, mutta olen kuitenkin nyt havainnut, että tuo viivojen leikkaustakastus on parempi.
Tekeillä pikkupelejä ja ohjelmia :)
SPuntte
Tech Developer
Tech Developer
Posts: 650
Joined: Mon Aug 27, 2007 9:51 pm
Location: Helsinki, Finland
Contact:

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Post by SPuntte »

Kauhean monimutkaiselta vaikutti tuo homma. Minun ajatuksenjuoksuni sanoo, että tuo onnistuu helpoiten ihan siten, että funktio ottaa syötteenä kolmioiden kärkipisteet ja tarkistaa onko jo(t)kin toisen kärkipisteistä ensimmäisen sisällä. Tähän tarkistukseen löytyy esim. SDK:sta salamannopea funktio (olikohan pointInTriangle), joka muistaakseni käyttää jompaa kumpaa tällä sivulla kuvatuista menetelmistä.
CoolBasic henkilökuntaa
Tech-kehittäjä
CoolBasic Classic, Cool VES

CoolPhysicsEngine | MissileSystem | Jana-ympyrä -törmäys | cbSimpleTexture | CoolCPLX
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 8:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori »

Juuri niin ajattelin sen aluksi tehdä, mutta tuli mieleeni Daavidin tähti ja lisäsin tarkistettavaksi myös kolmioiden sivujen keskipisteet. Olen muuten hirveän huono tekemään koodista selkeää. Riittää, että itse saan melko nopeasti selvitettyä, mitä koodi tekee.
SPuntte
Tech Developer
Tech Developer
Posts: 650
Joined: Mon Aug 27, 2007 9:51 pm
Location: Helsinki, Finland
Contact:

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by SPuntte »

Alligaattori wrote:Juuri niin ajattelin sen aluksi tehdä, mutta tuli mieleeni Daavidin tähti ja lisäsin tarkistettavaksi myös kolmioiden sivujen keskipisteet. Olen muuten hirveän huono tekemään koodista selkeää. Riittää, että itse saan melko nopeasti selvitettyä, mitä koodi tekee.
Hehhee, enpäs jaksanut itsekään ajatella loppuun saakka. :oops: Noin lomittain ne tosiaan voivat mennä, mutta silloinkaan pelkät kärkipisteet ja sivujen keskipisteet eivät riitä. SDK:n determinanteilla toimiva linesIntersect - kuten joku edellä mainitsi - tuon edellä kuvaamani metodin lisäksi pitäisi siis olla vedenpitävä.
CoolBasic henkilökuntaa
Tech-kehittäjä
CoolBasic Classic, Cool VES

CoolPhysicsEngine | MissileSystem | Jana-ympyrä -törmäys | cbSimpleTexture | CoolCPLX
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 8:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori »

SPuntte wrote:Noin lomittain ne tosiaan voivat mennä, mutta silloinkaan pelkät kärkipisteet ja sivujen keskipisteet eivät riitä.
Kyllä ne mielestäni riittävät, jos pelataan tasasivuisilla kolmioilla. En ole keksinyt tilannetta, jossa ne eivät riittäisi.
SPuntte
Tech Developer
Tech Developer
Posts: 650
Joined: Mon Aug 27, 2007 9:51 pm
Location: Helsinki, Finland
Contact:

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by SPuntte »

Alligaattori wrote:
SPuntte wrote:Noin lomittain ne tosiaan voivat mennä, mutta silloinkaan pelkät kärkipisteet ja sivujen keskipisteet eivät riitä.
Kyllä ne mielestäni riittävät, jos pelataan tasasivuisilla kolmioilla. En ole keksinyt tilannetta, jossa ne eivät riittäisi.
Nyt on sitten taas sinun vuoro ajatella loppuun asti :P
Image
CoolBasic henkilökuntaa
Tech-kehittäjä
CoolBasic Classic, Cool VES

CoolPhysicsEngine | MissileSystem | Jana-ympyrä -törmäys | cbSimpleTexture | CoolCPLX
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 8:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori »

Auts.

Testasin vielä ja noinhan se on. :( Eli pitää ujuttaa sekaan vielä janojen leikkauksen tunnistaminen. Sitten kun/jos jaksan...
SPuntte
Tech Developer
Tech Developer
Posts: 650
Joined: Mon Aug 27, 2007 9:51 pm
Location: Helsinki, Finland
Contact:

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by SPuntte »

Alligaattori wrote:Auts.

Testasin vielä ja noinhan se on. :( Eli pitää ujuttaa sekaan vielä janojen leikkauksen tunnistaminen. Sitten kun/jos jaksan...
Mutta muista myös, että samalla voit tiputtaa ne sivujanojen keskipisteet pois :]
CoolBasic henkilökuntaa
Tech-kehittäjä
CoolBasic Classic, Cool VES

CoolPhysicsEngine | MissileSystem | Jana-ympyrä -törmäys | cbSimpleTexture | CoolCPLX
otto90x
Advanced Member
Posts: 349
Joined: Mon Aug 27, 2007 9:00 pm
Location: Lapinjärvi, Finland
Contact:

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by otto90x »

Tässähän tuo olisi kaamealla purkalla väännettynä, kiva oisi tuollainen yleistää millä tahansa n-kulmiolle, mutta luultavasti siinä tulee ongelmaksi ettei tiedä miten ne monikulmiot kolmioista rakentaisi. Onkos vinkkejä?

Code: Select all

t1x = Rand(0,400)
t1y = Rand(0,300)
t2x = Rand(0,400)
t2y = Rand(0,300)
t3x = Rand(0,400)
t3y = Rand(0,300)

t1  = Rand(10,100)
t2  = Rand(10,100)
t3  = Rand(10,100)

Repeat

triangle(t1x,t1y,t2x,t2y,t3x,t3y)

If KeyHit(cbkeyspace) Then 
    t1x = Rand(0,400)
    t1y = Rand(0,300)
    t2x = Rand(0,400)
    t2y = Rand(0,300)
    t3x = Rand(0,400)
    t3y = Rand(0,300)
    t1  = Rand(10,100)
    t2  = Rand(10,100)
    t3  = Rand(10,100)
EndIf
    
    
tx1=MouseX()+Cos(ang)*t1
ty1=MouseY()+Sin(ang)*t1
tx2=MouseX()+Cos(ang+120)*t2
ty2=MouseY()+Sin(ang+120)*t2
tx3=MouseX()+Cos(ang+240)*t3
ty3=MouseY()+Sin(ang+240)*t3

triangle(tx1,ty1,tx2,ty2,tx3,ty3)

If TriangleOverlap(t1x,t1y,t2x,t2y,t3x,t3y,tx1,ty1,tx2,ty2,tx3,ty3) Then 
    Color cbred
Else 
    Color cbwhite
EndIf

DrawScreen

Forever


Function Triangle(x1,y1,x2,y2,x3,y3,fill=0) 'by atomimalli

    Line x1,y1,x2,y2
    Line x2,y2,x3,y3
    Line x3,y3,x1,y1

    If fill = True Then
        If y2<y1 Then 'jos p2 on ylempänä kuin p1 vaihdetaan niiden paikkaa
            tmp=y1
            y1=y2
            y2=tmp
            
            tmp=x1
            x1=x2
            x2=tmp
        EndIf
        
        If y3<y1 Then 'jos p3 on ylempänä kuin p1 vaihdetaan niiden paikkaa
            tmp=y1
            y1=y3
            y3=tmp
            
            tmp=x1
            x1=x3
            x3=tmp
        EndIf
        
        If y3<y2 Then 'jos p3 on ylempänä kuin p2 vaihdetaan niiden paikkaa
            tmp=y2
            y2=y3
            y3=tmp
            
            tmp=x2
            x2=x3
            x3=tmp
        EndIf
        
        'pisteet ovat nyt järjestyksessä
        'ylhäältä alas p1(x1,y1), p2(x2,y2), p3(x3,y3)
        dy1=y2-y1'pystysuora matka p1:sta p2:seen
        dx1=x2-x1'vaakasuora matka p1:sta p2:seen
        dy2=y3-y1'pystysuora matka p1:sta p3:meen
        dx2=x3-x1'vaakasuora matka p1:sta p3:meen
        
        If dy1 Then 'jos kolmion yläosa on pidempi kuin 0
            'käydään läpi kaikki vaakaviivat kolmion yläosassa(p1-p2)
            For i = y1 To y2
                'lasketaan seuraava x-koordinaatti p1:stä p2:seen
                ax=x1+((i-y1)*dx1)/dy1
                'lasketaan seuraava x-koordinaatti p1:stä p3:meen
                bx=x1+((i-y1)*dx2)/dy2
                Line ax,i,bx,i 'piirretään viiva kolmion reunojen välille
            Next i
        EndIf
        
        dy1=y3-y2'pystysuora matka p2:sta p3:meen
        dx1=x3-x2'vaakasuora matka p2:sta p3:meen
        
        If dy1 Then 'jos kolmion alaosa on pidempi kuin 0
            'käydään läpi kaikki vaakaviivat kolmion alaosassa(p2-p3)
            For i = y2 To y3
                'lasketaan seuraava x-koordinaatti p2:stä p3:meen
                ax=x2+((i-y2)*dx1)/dy1
                'lasketaan seuraava x-koordinaatti p1:stä p3:meen
                bx=x1+((i-y1)*dx2)/dy2
                Line ax,i,bx,i 'piirretään viiva kolmion reunojen välille
            Next i
        EndIf
    EndIf
EndFunction


Function TriangleOverlap(x1#,y1#,x2#,y2#,x3#,y3#,xx1#,yy1#,xx2#,yy2#,xx3#,yy3#)
    
    If PointInTriangle(xx1#, yy1#, x1#, y1#, x2#, y2#, x3#, y3#) Then Return True
    If PointInTriangle(xx2#, yy2#, x1#, y1#, x2#, y2#, x3#, y3#) Then Return True
    If PointInTriangle(xx3#, yy3#, x1#, y1#, x2#, y2#, x3#, y3#) Then Return True
    
    If Lines_Intersect(x1#,y1#,x2#,y2#, xx1#,yy1#,xx2#,yy2#) Then Return True
    If Lines_Intersect(x2#,y2#,x3#,y3#, xx1#,yy1#,xx2#,yy2#) Then Return True
    If Lines_Intersect(x1#,y1#,x3#,y3#, xx1#,yy1#,xx2#,yy2#) Then Return True
    If Lines_Intersect(x1#,y1#,x2#,y2#, xx1#,yy1#,xx3#,yy3#) Then Return True
    If Lines_Intersect(x1#,y1#,x3#,y3#, xx1#,yy1#,xx3#,yy3#) Then Return True
    If Lines_Intersect(x3#,y3#,x2#,y2#, xx1#,yy1#,xx3#,yy3#) Then Return True
    If Lines_Intersect(x1#,y1#,x2#,y2#, xx2#,yy2#,xx3#,yy3#) Then Return True
    If Lines_Intersect(x3#,y3#,x2#,y2#, xx2#,yy2#,xx3#,yy3#) Then Return True
    If Lines_Intersect(x1#,y1#,x3#,y3#, xx2#,yy2#,xx3#,yy3#) Then Return True
    
    Return False
    
End Function 

Function PointInTriangle(x#, y#, x1#, y1#, x2#, y2#, x3#, y3#)
   ab# = ((y - y1) * (x2 - x1) - (x - x1) * (y2 - y1)) / 1000.0
   bc# = ((y - y2) * (x3 - x2) - (x - x2) * (y3 - y2)) / 1000.0
   ca# = ((y - y3) * (x1 - x3) - (x - x3) * (y1 - y3)) / 1000.0
   If (ab * bc) > 0 And (bc * ca) > 0 Then Return True
   Return False
EndFunction

Function Lines_Intersect(Ax#, Ay#, Bx#, By#, Cx#, Cy#, Dx#, Dy#)

   Rn# = (Ay#-Cy#)*(Dx#-Cx#) - (Ax#-Cx#)*(Dy#-Cy#)
   Rd# = (Bx#-Ax#)*(Dy#-Cy#) - (By#-Ay#)*(Dx#-Cx#)

   If Rd# = 0
       Return False    
   Else
       Sn# = (Ay#-Cy#)*(Bx#-Ax#) - (Ax#-Cx#)*(By#-Ay#)
       Intersection_AB# = Rn# / Rd#
       Intersection_CD# = Sn# / Rd#        
       If Intersection_AB#>1 Or Intersection_CD#>1 Or Intersection_AB#<0 Or Intersection_CD#<0 Then Return False
       IntersX = Ax# + Intersection_AB#*(Bx#-Ax#)
       IntersY = Ay# + Intersection_AB#*(By#-Ay#)    
       Return True        
   EndIf

End Function
Otto Martikainen a.k.a. MetalRain, otto90x, kAATOSade.
Runoblogi, vuodatusta ja sekoiluja.
Jonhu
Active Member
Posts: 186
Joined: Mon Aug 04, 2008 5:45 pm

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Post by Jonhu »

Itse ajattelin tehdä myös tunnistuksen erimuotoisille kolmioille, mutta näköjään ehdit ensin :D

Itse suosittelisin muistipaloja tai taulukoita, että tarkistus saataaisiin tehty for-silmukassa, jolloin function voisi yleistää kaikille monikulmioille.
Tekeillä pikkupelejä ja ohjelmia :)
otto90x
Advanced Member
Posts: 349
Joined: Mon Aug 27, 2007 9:00 pm
Location: Lapinjärvi, Finland
Contact:

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by otto90x »

Jonhu wrote:Itse suosittelisin muistipaloja tai taulukoita, että tarkistus saataaisiin tehty for-silmukassa, jolloin function voisi yleistää kaikille monikulmioille.
No ei se itse asiassa ihan niin näppärästi suju, sillä periaatteessahan kaikki monikulmiot pitäisi jakaa kolmioiksi, että tuota PointInTriangle funktiota voidaan käyttää. Toki voidaan vain tarkistaa monikulmion rajat LinesIntersect funktiolla, mutta silloinhan voi päällekkäisyyksiä esiintyä. Muistipalat lienevät parempi vaihtoehto, sillä tyypit ovat globaaleja ja siten saattavat aiheuttaa virheitä muualla.
Otto Martikainen a.k.a. MetalRain, otto90x, kAATOSade.
Runoblogi, vuodatusta ja sekoiluja.
SPuntte
Tech Developer
Tech Developer
Posts: 650
Joined: Mon Aug 27, 2007 9:51 pm
Location: Helsinki, Finland
Contact:

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by SPuntte »

otto90x wrote:
Jonhu wrote:Itse suosittelisin muistipaloja tai taulukoita, että tarkistus saataaisiin tehty for-silmukassa, jolloin function voisi yleistää kaikille monikulmioille.
No ei se itse asiassa ihan niin näppärästi suju, sillä periaatteessahan kaikki monikulmiot pitäisi jakaa kolmioiksi, että tuota PointInTriangle funktiota voidaan käyttää. Toki voidaan vain tarkistaa monikulmion rajat LinesIntersect funktiolla, mutta silloinhan voi päällekkäisyyksiä esiintyä. Muistipalat lienevät parempi vaihtoehto, sillä tyypit ovat globaaleja ja siten saattavat aiheuttaa virheitä muualla.
Tuo kolmioiksi jakaminen ei ole ihan niin kakkua kuin voisi kuvitella - tai on, jos monikulmioilta vaaditaan, että ne ovat kuperia (engl. convex), siis että kaikki kärjet ovat teräviä ulospäin. Tällöin mistä tahnsa monikulmion sisällä olevasta pisteestä kärkipisteisiin piirretyt janat jakavat monikulmion kolmioihin. Matemaattisesti helppo valinta on esimerkiksi jonkin monikulmion lävistäjän keskipiste (siis minkä tahansa kahden kärkipisteen keskiarvo).

Jos monikulmio ei ole kupera, se on kovera ( :D ) (engl. concave). Tällöin saattaa tulla mitä mainioimpia virheitä, jos yritetään käyttää edellä kuvattua tekniikkaa. Pienempi kämmi on, että lähtöpisteeksi valitaan piste, joka on edelleen kyllä monikulmion sisällä, mutta yksi tai useampi kolmiot määrittävistä janoista leikkaakin monikulmion jotakin sivua. Eniten päin mäntyä menee silloin, kun valittu alkupiste on monikulmion ulkopuolella. Tässä kuva esimerkkitapauksista:
Image

En tunne yhtään yksinkertaista vedenpitävää algoritmia koveran monikulmion jakamiseksi kolmioihin, mutta voisin yrittää etsiä/kehittää sellaista itse, jos haluatte tuollaisen funktion rakentaa. Jos joku muu ahkerampana tarttuu hommaan, annan sellaisen vinkin, että jos monikulmion kärkipisteet on lueteltu järjestyksessä kiertäen vastapäivään, on minkä tahansa kahden peräkkäisen sivuvektorin ristitulo (suomenkielisen wikipedian artikkeli on turhan teoreettinen) positiivinen, jos näiden yhteinen kärki on kupera, ja negatiivinen, jos kärki on kovera. Tästäkin havainnollistava kuva: (harmaat viivat esittävät monikulmion sisustaa ja vektorikuvioissa mustat viivat suoran kulman merkkejä vektorien välillä)
Image
CoolBasic henkilökuntaa
Tech-kehittäjä
CoolBasic Classic, Cool VES

CoolPhysicsEngine | MissileSystem | Jana-ympyrä -törmäys | cbSimpleTexture | CoolCPLX
Post Reply