Keskustelu: Ohjelmointikysymykset: C: Törmäystarkistus

Kuinka voi helposti tarkistaa että onko pixeli(panos) tasasivuisen kolmion(alus) sisällä?

Valitse kolmion kärkipiste A ja olkoot kolmion sivuina vektorit u ja v (lähtee A:sta). Tällöin jokainen tason piste on muotoa P=xu+yv, missä x ja y ovat reaalilukuja. Nyt P on kolmion sisällä, jos ja vain jos x,y>=0 ja x+y<=1.

Ööh,voisiko tuota kertoa hieman alemmalla matematiikalla?
En ole oikein sinut vektoreiden kanssa.
Vaikka funktion tynkää.
Kärkipisteet ja muutkin pisteet toki tiedän.

Enpä tiedä tuosta menetelmästä, miten sen selittäisi yksinkertaisemmin. Todistus nimittäin perustuu konveksiin peitteeseen ja se voi olla liian korkeammalle menevää, jos vektoritkaan ei ole hallussa.

Toinen tapa tehdä tarkistus on seuraava: Valitse jokin piste P kolmion virittämästä tasosta. Tarkista ensin, että pisteesi kuuluu tähän tasoon, sillä muuten piste ei voi olla kolmion sisäpuolella. Olkoon tutkittava piste P'. Laske montako kertaa jana PP' leikkaa kolmion. Jos määrä on yksi, niin P' kolmion sisällä. Jos määrä on nolla tai kaksi, niin P' on kolmion ulkopuolella.

https://www.ohjelmointiputka.net/oppaat/opas.php?tunnus=mat3
jos olisi jotain apua

Tarkista "tason ristitulolla", onko piste samalla puolella jokaista sivujanaa. Jos on, niin piste on kolmion sisällä.

int onko_piste_kolmiossa(
       double px, double py, /* piste */
       double ax, double ay, /* kolmion kärkipisteet a,b,c */
       double bx, double by,
       double cx, double cy)
{
	double e1x = bx-ax, /* sivujanavektorit e1,e2,e3 */
	       e1y = by-ay,
	       e2x = cx-bx,
	       e2y = cy-by,
	       e3x = ax-cx,
	       e3y = ay-cy;

	double p1 = e1x*(py-ay)-e1y*(px-ax), /* ristitulot */
	       p2 = e2x*(py-by)-e2y*(px-bx),
	       p3 = e3x*(py-cy)-e3y*(px-cx);

	/* piste on kolmion sisällä, jos ristitulojen merkit ovat samat,
	   eli piste on samalla puolella (esim. vasemmalla)
	   kaikkia sivujanoja */
	return ((p1 <= 0) == (p2 <= 0) && (p2 <= 0) == (p3 <= 0));
}

Menetelmä toimii myös muille tason konvekseille.

Tästähän on muuten aiempikin keskustelu.

Nyt sentään lasketaan vähän eri tyypeillä, mutta jotkut asiat eivät ole muuttuneet pätkääkään... :-)