TrianglesOverlap - kahden kolmion törmäystunnistus

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

TrianglesOverlap - kahden kolmion törmäystunnistus

Post by Alligaattori » Sun Mar 15, 2009 12:52 pm

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 10:29 pm, edited 4 times in total.

User avatar
Jani
Devoted Member
Posts: 741
Joined: Fri Oct 31, 2008 5:53 pm

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Post by Jani » Sun Mar 15, 2009 1:10 pm

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

User avatar
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 9:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori » Sun Mar 15, 2009 1:15 pm

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.

User avatar
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 » Sun Mar 15, 2009 2:31 pm

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.

User avatar
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 9:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori » Sun Mar 15, 2009 2:41 pm

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 » Mon Mar 16, 2009 7:30 pm

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 :)

User avatar
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 9:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori » Mon Mar 16, 2009 9:23 pm

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 » Tue Mar 17, 2009 1:17 am

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 » Tue Mar 17, 2009 5:01 pm

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 :)

User avatar
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 » Tue Mar 17, 2009 5:13 pm

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

User avatar
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 9:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori » Tue Mar 17, 2009 5:20 pm

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.

User avatar
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 » Tue Mar 17, 2009 5:29 pm

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

User avatar
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 9:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori » Tue Mar 17, 2009 5:57 pm

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.

User avatar
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 » Tue Mar 17, 2009 10:21 pm

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

User avatar
Alligaattori
Active Member
Posts: 135
Joined: Fri Mar 07, 2008 9:49 pm

Re: TrianglesOverlap - kahden kolmion törmäystunni

Post by Alligaattori » Tue Mar 17, 2009 10:27 pm

Auts.

Testasin vielä ja noinhan se on. :( Eli pitää ujuttaa sekaan vielä janojen leikkauksen tunnistaminen. Sitten kun/jos jaksan...

User avatar
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 » Tue Mar 17, 2009 10:55 pm

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

User avatar
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 » Wed Mar 18, 2009 3:12 pm

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 » Wed Mar 18, 2009 4:28 pm

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 :)

User avatar
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 » Wed Mar 18, 2009 4:40 pm

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.

User avatar
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 » Thu Mar 19, 2009 1:35 am

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