CoolBasic Forums

Posted: **Sun Mar 15, 2009 11:52 am**

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ää

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

Posted: **Sun Mar 15, 2009 12: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ä.

Posted: **Sun Mar 15, 2009 12: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.

Posted: **Sun Mar 15, 2009 1: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

Posted: **Sun Mar 15, 2009 1:41 pm**

Oho, olin poistanut vähän tarkisteluja siivotessani funktiota. Nyt pitäisi toimia taas.

Posted: **Mon Mar 16, 2009 6: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

Posted: **Mon Mar 16, 2009 8: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.

Posted: **Tue Mar 17, 2009 12:17 am**

Janojen leikkaus-metodi ei tunnista sisäkkäisiä kolmioita.

Posted: **Tue Mar 17, 2009 4: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.

Posted: **Tue Mar 17, 2009 4: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ä.

Posted: **Tue Mar 17, 2009 4: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.

Posted: **Tue Mar 17, 2009 4: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.

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ä.

Posted: **Tue Mar 17, 2009 4: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.

Posted: **Tue Mar 17, 2009 9: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

Posted: **Tue Mar 17, 2009 9:27 pm**

Auts.

Testasin vielä ja noinhan se on.

Eli pitää ujuttaa sekaan vielä janojen leikkauksen tunnistaminen. Sitten kun/jos jaksan...

Posted: **Tue Mar 17, 2009 9: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 :]

Posted: **Wed Mar 18, 2009 2: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

Posted: **Wed Mar 18, 2009 3:28 pm**

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

Itse suosittelisin muistipaloja tai taulukoita, että tarkistus saataaisiin tehty for-silmukassa, jolloin function voisi yleistää kaikille monikulmioille.

Posted: **Wed Mar 18, 2009 3: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.

Posted: **Thu Mar 19, 2009 12: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 (

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

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

CoolBasic Forums

TrianglesOverlap - kahden kolmion törmäystunnistus

TrianglesOverlap - kahden kolmion törmäystunnistus

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunnistus

Re: TrianglesOverlap - kahden kolmion törmäystunni

Re: TrianglesOverlap - kahden kolmion törmäystunni