/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
Linje rammer polygon test
Fra : Klaus Petersen


Dato : 10-03-03 22:45

Davs.

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

Der findes steder på nettet hvor det er forklaret.. men jeg er lidt fatsvag,
når det kommer til matematik, så jeg skal helst gerne have det serveret
meget "let-spiseligt".

På forhånd tak for al den hjælp jeg kan få.

Klaus.



 
 
Carsten Svaneborg (11-03-2003)
Kommentar
Fra : Carsten Svaneborg


Dato : 11-03-03 12:15

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


Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408849
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste