Klaus Petersen wrote:
> Jeg mangler en forklaring og meget gerne et eksempel til hvordan man
> tester via. en udregning hvorvidt en linie i rummet går igennem et polygon
> (simpelt+konvekst).
Er polygonen flad?
Anyways, du kan opløse polygonen i et antal trekanter og
checke for hver trekant.
Hvordan checker du om linien går gennem en trekant i rummet?
1) trekanten definere et plan krydser linien dette plan?
2) hvis ja, så kan du finde punktet hvor linien krydser planet
3) du har nu et 2D problem, fordi både trekant og punkt ligger i samme plan
4) find ud af om punktet ligger inde i trekanten
Jeg har spekuleret lidt over dette, og jeg tror følgende
er den hurtigste løsning.
Find skærings punktets koordinater i det ikke retvinklede og
normerede koordinatsystem der defineres af to af trekantens sider.
Dvs. er trekanten defineret ved tre hjørner R1,R2,R3, så
vælger vi R2 som origo, og e1=R2-R1 og e2=R3-R2 som akser
i koordinatsystemet, bemærk e1,e2 er ikke enhedsvektorer!!
(er de paralelle er trekanten ikke en trekant!)
R som skæringspunktet
Du skal så løse ligningen x*e1 + y*e2 = (R-R2) for
de to konstanter x og y. R-R2 er vektoren fra origo til
skæringspunktet.
(e1,e2, R-R2 er alle vektorer, så der er 3 ligninger med 2
ubekendte, men fordi alt er begrænset til et plan er der
kun 2 uafhængige ligninger.)
x og y er koordinaterne på skæringspunktet udtrykket ved
i det valgte koordinatsystem, der IKKE vil være vinkelret
og hvor akserne ikke har længe 1.
Det smarte ved koordinatsystemet er at det er valgt så,
punktet ligger inde i hele trekanten hvis dets koordinater
opfylder den simple ulighed x>=0 && y>=0 && x+y<=1
(tegn det på et stykke papir)
--
Mvh. Carsten Svaneborg
http://www.softwarepatenter.dk