Keskustelu: Ohjelmointikysymykset: C: Polygoniin törmääminen

Mikä olisi paras tapa testata monikulmion ja ympyrän "törmäämistä" 2-ulotteisessa ympäristössä? Eli funktion pitäisi vain kertoa osuvatko ne toisiinsa vai eivät, lasken seuraukset itse.

Voit tietenkin tarkistaa kaikki kulmioiden viivat ja yhdistelmät. Jos yksikin viiva on toisen päällä, ne ovat törmänneet.

Approksimoi monikulmiota ympyrällä ja tarkista josko ympyröiden keskipisteiden etäisyys on pienempi kuin niiden säteiden summa.

Kyseessä oli siis ympyrän ja monikulmion törmääminen, ei kahden monikulmion. Niillä ei varmaankaan oikein voi tuota viivoilla leikkimistä tehdä(?) Tietenkin olisi helpointa ympyröidä monikulmio, mutta sehän on kauhean epätarkkaa, eikö?

Eikun tosiaan, voihan sen viivojen leikkaamisen testata ympyrälläkin. Nyt on enää yksi onkelma: Miten kokeilen, leikkaavatko kaksi viivaa? :)

Ympyrän ja janan leikkaus:

Jos ympyrän keskipiste sijaitsee pisteessä C ja ympyrän säde on R. Ja jana kulkee pisteestä A pisteeseen B.

J=B-A
V=J/|J|
N.x=V.x
N.y=-V.y
jos (C*N-A*N < R)
{
  jos (0 < (C-A)*V < |J|) leikkaus pisteessä A+((C-A)*V)*V
  muuten ei leikkausta
}
muuten
{
  Ei leikkausta
}

Tuo noin äkkiä paperilla ja kynällä hahmoteltuna. En menisi takuuseen toimivuudesta. Kaikki symbolit ovat tietenkin vektoreita ja * tarkoittaa pistetuloa.

Tarkoittaako tuo |J| J:n pituutta? Ei tuo ainakaan näin tulkittuna toimi:

int linecollision(CIRCLE a, LINE b)
{
VECTOR J, V, N;
J=AddVector(b.epoint,ReverseVector(b.spoint));
V=NormalizeVector(J);
N.x=V.x;
N.y=-V.y;
if (DotVector(a.center,N)-DotVector(b.spoint,N)<a.radius)
{
if (0<DotVector(AddVector(a.center,ReverseVector(b.spoint)),V)<VectorLength(J))
{
return 1;
}
}
return 0;
}

Tuon pitäisi palauttaa 1 jos leikkaus tapahtuu, mutta se palauttaa aina nollan. spoint on siis janan alkupää ja epoint sen loppupää.

Tarkoitus oli sanoa, että se palauttaa aina ykkösen.

Joo siinä oli yhtä sun toista häikkää. Tosin niin oli kyllä sinun koodissasikin mm. normalisoit vektorin ennen kuin otit sen pituuden.

Tässä varmasti toimiva algoritmi. Samat symbolit kuin edellisessä.

J=B-A                        // Janan pituusvektori
V=J/|J|                      // Janan suuntainen yksikkövektori
D=C-A                        // Vektori janan alkupisteestä ympyrän keskelle.
// Etsi se piste janalta joka on lähinnä ympyrää
jos ( D*V<0 ) P=A            // Piste on janan alkupiste
muuten jos ( D*V>|J| ) P=B   // Piste on janan loppupiste
muuten P=A+D*V               // Piste on jossain välillä
// Tarkista onko tämä piste alle säteen päässä ympyrän keskipisteestä.
Jos ( |C-P|<R ) leikkaus
muuten ei leikkausta

Tuo NormalizeVector() on siis itse tekemäni funktio, joka palauttaa yksikkövektorin, ei muuta parametriksi annettua vektoria miksikään. Mutta mitä tarkoittaa A+D*V? A:han on vektori ja pistetulo on yksi luku, miten niitä voi laskea yhteen?

Nyt toimii, kiitos paljon avusta!

nakkikorva kirjoitti:

Mutta mitä tarkoittaa A+D*V? A:han on vektori ja pistetulo on yksi luku, miten niitä voi laskea yhteen?

Siinä on kirjoitusvirhe. Sen pitäisi olla P=A+(D*V)*V.
Eli liikutaan pisteestä A eteenpäin sen vektorin verran, joka saadaan, kun D projisoidaan vektorille V (tai miksei myös vektorille J, mutta silloin pitäisi vielä jakaa J:n pituudella).

Joo, tajusin sen kun vähän ajattelin itsekin =)