Mikä olisi helpoin tapa katsoa onko jokin piste kolmion sisällä?
Laskemalla tietysti...
Millainen kolmio on kyseessä?
Suorakulmainen kolmio
Olkoon kyseinen piste P. Valitse piste P', joka on varmasti kolmion ulkopuolella. Piirrä jana PP'. Jos tämä jana leikkaa kolmion sivut kerran, on piste kolmion sisällä, muuten ulkona. Tämä toimii kunhan PP' ei ole yhdensuuntainen kolmion sivun kanssa eikä kulje kolmion kärkipisteen kautta.
Piste on monikulmion sisäpuolella, jos siitä piirretty äärettömän pitkä puolisuora leikkaa parittoman määrän monikulmion sivuja.
Koodivinkissäni Törmäystarkistus 3D-avaruudessa tehdään juuri tällainen tarkistus, kommenteista pitäisi selvitä periaate.
Juu kiitoksia tein C++:lla tuon alkoritmin ja se on tämännäköinen
int isin(int Ax, int Ay, int Bx, int By, int Cx, int Cy, int Px, int Py) {
int fAB=(Py-Ay)*(Bx-Ax)-(Px-Ax)*(By-Ay);
int fCA=(Py-Cy)*(Ax-Cx)-(Px-Cx)*(Ay-Cy);
int fBC=(Py-By)*(Cx-Bx)-(Px-Bx)*(Cy-By);
int ret;
if (fAB*fBC > 0) {
if (fBC*fCA > 0) {
ret = 1;
}
else {
ret = 0;
}
}
else {
ret = 0;
}
return ret;
}(Mod. edit. Käytäpä kooditageja.)
Lupaan, etten enää ikinä koskaan nipota kellekään mistään, mutta tulipa pari tyyli- ja suunnitteluajatusta mieleen tuosta koodipätkästä. Tajuan kyllä, ettei sen ole tarkoituskaan olla mikään koulukirjaesimerkki, mutta...
Funktion paluuarvon voi päätellä aika selkeästi ja suoraan näin:
return (fAB*fBC > 0) && (fBC*fCA > 0);
Paluuarvomuuttuja ja if-polveilu on turhaa sössötystä.
Kun funktion on tarkoitus vastata johonkin kysymykseen "kyllä" tai "ei", paluutyyppi bool viestittää tällaisesta meiningistä parhaiten.
Kun tekee toteutuksen jollekin algoritmille, pelkkä kopiointi ei aina riitä. Oikein toteutetussa numeerisessa laskennassa tarvii kyllä pikkuisen väijyä arvoalueita, tarkkuuksia ja muita pirun hankalia juttuja. Jos tykkää, että ääh, kyllähän tuo nyt varmana ihan riittävän hyvin pelaa, niin väännetään vähän rautalangasta: Otetaan kolmio {(0, 0), (10, 0), (10, 10)} ja piste (2, 1). Tulos: sisällä on, hyvin pelaa. Otetaanpas sitten samanlainen isompi kolmio {(0, 0), (10000, 0), (10000, 10000)} ja kappas: piste ei enää olekaan kolmion sisällä. Mutta kyllä tuolla joo aina jonkun savonlinnan halpahallin katon voi suunnitella.
Siis, joko koordinaattiavaruutta pitää rajoittaa, pitää laskea eri tavalla tai käyttää suurempia tarkkuuksia. Tai kaikkia näitä yhdessä, koodaaminen on totista touhua, sopii enempi nipottaville tosikoille.
Kun puuhaa geometristen otusten kanssa, kannattaa luokat ja funktiot suunnitella sillä tapaa, että ne myötäilevät ihmisten tapaa tajuta geometriaa. C-koodarit on tietty niin läpitte rääkättyjä, että funktiokutsu kahdeksalla int-parametrilla on ihan jees
int ax = ...
int ay = ...
int bx = ...
int by = ...
int cx = ...
int cy = ...
int px = ...
int py = ...
if (isin(ax, ay, bx, by, cx, cy, px, py))
// tai aukikirjoitettuna vielä äijämäisemmin
if (isin(0, 0, 10000, 0, 10000, 10000, 2, 1))
{mutta kyllä oliomaisempi tapa
triangle abc = ...
point p = ...
if (abc.is_enclosing(p))
// tai vastaavasti auki
triangle abc(point(0, 0), point(10000, 0), point(10000, 10000));
if (abc.is_enclosing(point(2, 1)))
{on helpompi muille kuolevaisille, siitä kun saattaa jopa vähän nähdäkin, että minkä juttujen kanssa ollaan tekemisissä.
Tulipas taas vuodatusta. Olisihan se kumminkin kiva, jos esimerkillisiä ideoita demottaisiin toteutuksilla, jotka myös olisivat esimerkillisiä - mieluiten hyvässä. Eikä tämä ole mitenkään Tesmun vika, nettihän on väärällään samanlaisia ns. venäjäksi tehtyjä kyhäelmiä.
Mutta nyt saa riittää löpinät.
koo kirjoitti:
Siis, joko koordinaattiavaruutta pitää rajoittaa, pitää laskea eri tavalla tai käyttää suurempia tarkkuuksia.
Totta. Kolmion sisäpisteiden lukumäärä on ylinumeroituva, mutta tietokoneen muistiin mahtuu vain äärellisen monta bittiä. Siten tekipä ohjelman miten tahansa, ei ohjelma pysty täysin varmasti sanomaan annetusta kolmiosta onko annettu piste kolmion sisä-, reuna- vai ulkopiste.
no siis siihen tarkotukseen johon tarvitsin tota tuo alkoritmini riittää aivan mainiosti
Jaska kirjoitti:
Totta. Kolmion sisäpisteiden lukumäärä on ylinumeroituva, mutta tietokoneen muistiin mahtuu vain äärellisen monta bittiä. Siten tekipä ohjelman miten tahansa, ei ohjelma pysty täysin varmasti sanomaan annetusta kolmiosta onko annettu piste kolmion sisä-, reuna- vai ulkopiste.
Kyllä mutta ei. Kun koordinaattien esittämiseen käytetään tietokoneen tavallisia perustyyppejä, myös tasossa olevien pisteiden joukko on äärellinen ja numeroituva, kuten kolmion sisällä olevien pisteiden joukkokin.
Pisteen kuuluminen kolmion (tai ylipäätään konveksin monikulmion) sisään voidaan päätellä Tesmun löytämällä algoritmilla, mutta laskennassa pitää ottaa huomioon välitulosten arvoalue ja tarkkuus. Jos arvoaluetta ja tarkkuutta ei saada tarpeeksi, tarvii muuttaa laskentatapaa tai asettaa rajoituksia parametrien arvoalueille (siis koordinaattiavaruudelle), esmes sopivilla tyyppimäärittelyillä.
tesmu kirjoitti:
no siis siihen tarkotukseen johon tarvitsin tota tuo alkoritmini riittää aivan mainiosti
Just joo. Tarkoittaako riittävä sitä, että testattavat kolmiot ja pisteet ovat sattumalta 127*127 pisteen alueella vai sitä, ettei haittaa, vaikka funktio nyt vähän vääriä tuloksia antaisikin? Pitäisikö jossain olla edes varoitusteksti?
Vaikka vatupassilla naulaaminen näyttää tapauksessasi onnistuvan ihan mainiosti, älä hyvä mies ota sitä tavaksi tai älä ainakaan mainosta sellaista! Olet varmasti niin fiksu, että saat hoidettua nuo jutut oikeinkin, kun vaan vähän keskityt niihin.
koo kirjoitti:
tesmu kirjoitti:
no siis siihen tarkotukseen johon tarvitsin tota tuo alkoritmini riittää aivan mainiosti
Just joo. Tarkoittaako riittävä sitä, että testattavat kolmiot ja pisteet ovat sattumalta 127*127 pisteen alueella vai sitä, ettei haittaa, vaikka funktio nyt vähän vääriä tuloksia antaisikin? Pitäisikö jossain olla edes varoitusteksti?
Vaikka vatupassilla naulaaminen näyttää tapauksessasi onnistuvan ihan mainiosti, älä hyvä mies ota sitä tavaksi tai älä ainakaan mainosta sellaista! Olet varmasti niin fiksu, että saat hoidettua nuo jutut oikeinkin, kun vaan vähän keskityt niihin.
kuten sanoin että sitä tarkoitusta varten johon tarvitsin tuota niin tuo riittää
testattavana on vain yksi kolmio jonka aikalailla keskelle tietyissätapauksissa laitetaan 3 pistettä eroavaisuuksia kohdissa on ja loput pisteet tulevat varmasti kolmion ulkopuolelle kolmion paikka saattaa kyllä vaihtua eli A:n B:n ja C:n koordinaatit saattavat vaihtua mutta kolmio muodoltaan on kuitenkin samanlainen
No voi hyvät hyssykät! Tuo toteutus antaa vääriä tuloksia sekä kolmion sisällä että ulkona oleville pisteille. Väännetään rautakangesta: Otetaan suorakulmainen tasasivuinen kolmio {(0, 0), (373, 0), (0, 373)}, (EDIT: korjattu typo koordinaatissa) pannaan aikalailla sen keskelle piste (124, 124) ja tättärää, toteutus sanookin sen olevan kolmion ulkopuolella! Vastaavasti, muodoltaan samanlaisen kolmion {(0, 0), (124, 0), (0, 124)} ulkopuolella varmasti oleva piste (373, 373) onkin sitten sen sisäpuolella. Yleisesti ottaen tuo toteutus muuttuu epäluotettavaksi, kun joidenkin testissä mukana olevien pisteiden x- tai y-koordinaattien erotus alkaa mennä 180 päälle.
Jos tuo tosiaan riittää tarkoituksiisi, niin olkoon sitten niin. Kyllä tämä touhu alkaa riittää jo minullekin.
Aihe on jo aika vanha, joten et voi enää vastata siihen.