Minimal afstand mellem to trekanter i rummet.

1) For hver af trekanterene beregner du midtpunktet for hver side. Du får på den måde 6 punkter for hver trekant: 3 hjørner og 3 midtpunkter.

2) Løb igennem de 6 punkter i den ene trekant
... for hver af dem løber du igennem de 6 punkter i den anden trekant
...... for hvert par af et punkt fra den ene og et punkt fra den anden, beregner du afstanden mellem hjørnerne.

3) Den mindste afstand er det tal du søger.

...... for hvert par af et punkt fra den ene og et punkt fra den anden, beregner du afstanden mellem hjørnerne.

- skulle have været:

...... for hvert par af et punkt fra den ene og et punkt fra den anden, beregner du afstanden mellem punkterne.

Nej, den holder ikke vand efter nærmere analyse... kigger lidte mere på det :^)

Man kan godt regne sig frem til det, men det bliver hurtigt nogle lange udtryk som det kan være svært at holde styr på. I stedet vil jeg foreslå en numerisk algoritme... bisektion.

Lad mig se om jeg kan forklare det uden at gøre nogen mere forvirrede end højst nødvendig:

Trin 1)

For hver hjørne A i trekant nr. 1.
... løber du igennem hver side i trekant nr. 2.

Trin 2)

For hver side, i trekant nr. 2, starter du med de to hjørner B og C.
... beregn midtpunktet, D, mellem B og C.
...... beregn afstanden mellem A og hvert af de tre punkter B, C, og D.
......... udvælg de to punkter som har mindst afstand til A.

Lad dette være de nye to punkter B og C,
beregn D som midtpunkt,
og fortsæt på denne måde så længe du vil
(indtil at afstanden ikke mere bliver mindre).

Trin 3)

Afstanden fra A til D er en kandidat til den mindste afstand.
For hver af de 3 sider, i trekant nr. 2, får man en sådan kandidat.
Vælg den mindste af de 3: dette er en bedre kandidat

Trin 4)

For hvert af de 3 hjørner i trekant nr.1
får man en ”bedre kandidat”.
Vælg den mindste af de 3: dette er en endnu bedre kandidat

Trin 5-8)

Derefter byttes rollerne om mellem de to trekanter:

For hver hjørne A i trekant nr. 2.
... løber du igennem hver side i trekant nr. 1.

- og man udregner den ”endnu bedre kandidat” for dette.

Trin 9)

Dem mindste af de to ”endnu bedre kandidater” er det rigtige svar.

Måske kan dette også være til hjælp?

http://www.nist.gov/dads/HTML/euclidndstnc.html

nielle
Hvis jeg forstår din algoritme korrekt, så kigger du kun på randen af trekanterne, men den korteste afstand kan jo også være mellem f.eks. et hjørne i trekant 1 og et punkt i trekant 2's indre. Måske er der ingen vej uden om at kigge på alle muligheder (hjørner vs. hjørner, hjørner vs. sider, hjørner vs. trekantindre, sider vs. sider)

kjulius
Siden viser hvordan man beregner den euklidiske afstand mellem to punkter. Det får jeg selvfølgelig brug for, men det er ikke helt det jeg leder efter.

Jeg må jo nok tilstå at jeg om til at tænke trekanter i det 2.dimensionelle plan. Imidlertid kan algoritmen nemt modificeres til trekanter i det 3-dimensionelle rum:

Trin 1)

1) For hver hjørne, A, i trekant nr.1.
2) ... starter du med de tre hjørner B, C, og D, i trekant nr. 2.
3) ...... beregn midtpunktet, E,  mellem disse punkter.
4) ......... beregn afstanden fra A til hvert af punkterne B, C, D, og E.
5) ............ det af punkterne,  B, C, D, og E, hvor afstanden til A er størst, smides væk.
6) ............... Du har nu tre punkter tilbage – altså en ny trekant nr. 2.

Gentag punkt 2-6 så længe du vil.
(indtil at afstanden mellem A og E ikke bliver mindre.)
Afstanden fra A til E er en kandidat.

Trin 2)

Gør det samme for de to andre hjørner i trekant nr. 1.
Vælg den mindste af de tre: dette er en bedre kandidat.

Trin 3-4)

Derefter byttes rollerne om mellem de to trekanter:

For hvert hjørne, A, i trekant nr.2
... beregnes ”kandidaten”.

På samme måde som får ender man med en ”bedre kandidat”.

Trin 5)

Til sidst sammenlignes de to ”bedre kandidater”,
og det rigtige svar er så den mindste af disse to.

nielle
Igen, hvis jeg forstår din algoritme korrekt, så vil den finde den korteste afstand mellem et af den ene trekants hjørner og den anden trekant (rand og indre). Men den korteste afstand mellem de to trekanter kan jo også være mellem to kanter. Jeg har sat en geometriprofessor på sagen, men der er noget der tyder på, at jeg skal igennem alle tilfælde. Men det vil umiddelbart, som jeg ser det, stadig være færre beregninger end din numeriske metode.

Har du egentligt fået løst denne her endnu?

Både ja og nej. Jeg kan finde den eksakte afstand mellem to trekanter ved at beregne alle følgende afstande: hjørne vs. hjørne, hjørne vs. kant, hjørne vs. indre, kant vs. kant og så tage den korteste af de fundne afstande, men dette viste sig at være alt for "tungt" tidsmæssigt. Det viste sig imidlertid, at jeg kunne nøjes med en approximeret korteste afstand mellem de objekter i rummet jeg har med at gøre, så en simpel afstand mellem to bounding boxes kunne gøre det for mig.

Hvis du svarer på spørgsmålet vil jeg imidlertid gerne give dig pointene for din indsats.

Ah, det lyder som om at der er tale om noget 3D animation og kollisionskontrol?

Ja, i så fald handler det nok mere om hastighed end om at være nøjagtig.

Jeg er nu ellers sikker på at det godt kan gøres med en numerisk metode, men den er ikke nødvendigvis så hurtig som du sikkert kunne ønske dig (hvis jeg har gættet rigtigt mht. 3D animation?). Og jeg ved for resten heller ikke om den nødvendigvis er pænere end det du har nu. Det er dog sikkert at den metode jeg pt. har i tankerne ikke egner sig til at blive vist på Eksperten, idet det involvere en del matematiske formler (herunder partiel differentiation). Men jeg er da parat til at prøve hvis det er vigtigt for dig?

For resten: Er det egentlig afstanden du har brug for, eller er det nok for dog at vide om de to trekanter skære hinanden (kollidere)?

Det er i hvertfald noget 3D :-) Men ikke kollisionskontrol, til det bruger jeg SAT (separating axes theorem). Og det var ideelt afstanden mellem to ikke-konvekse polyeder jeg søgte. Jeg kunne dog kun finde en metode der brugte voronoiregioner, som jeg ikke gad rode mig ud i. Dernæst reducerede jeg så problemet til at finde afstanden mellem trekanterne der udgør polyederne, men jeg burde nok have sagt mig selv, at det ville være for tungt.

For min skyld behøver du ikke besvære dig med at give den numeriske metode. I øvrigt tror jeg da ikke, at partiel differentation er for hårdt matematisk for eksperten.dk :-)

Det er formelerene som er lidt svære at skrive på Eksperten :^)