De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Algoritme: doorsnede van 2 prisma s bepalen

Gegeven: twee vlakken in de ruimte bepaalt door drie hoekpunten (x,y,z).
De vlakken zijn rechthoeken.
Gevraagd : hoe bepaal ik de snijlijn tussen deze twee vlakken met als resultaat het begin en eindpunt(x,y,z)

Bruno
Iets anders - dinsdag 26 augustus 2003

Antwoord

Hoi,

Na een aantal bijkomende vraagjes blijkt dit een nauwkeuriger omschrijving van je probleem.

Gegeven een vlakke veelhoek met n hoekpunten pi:i=1..n. Dit is een stuksgewijze lineaire benadering van een figuur die het grondvlak van een extrusievolume V voorstelt (de veelhoek is praktisch dus niet-splitsbaar en meestal zelfs convex). Dit volume staat loodrecht op het grondvlak.

Dit extrusievolume wil je doorboren door een tweede volume V’ waarvan het grondvlak ook een vlakke veelhoek is en waarvan alle andere ribben loodrecht op het grondvlak staan. De m hoekpunten van het grondvlak noemen we qi:i=1..m.

Een toegelaten vereenvoudiging bestaat erin dat de lengteassen van V en V’ loodrecht op elkaar staan. Wellicht hebben we deze vereenvoudiging niet nodig.

De vraag is nu: hoe bereken je de punten van de ruimteveelhoek(en) die de doorsnede van deze volumes V en V’ vormt?

De n zijvlakken van V kunnen we dus voorstellen door gi:i=1..n waarbij gi loodrecht op het XY-vlak staat en door pi en pi+1 loopt voor in en voor gn door pn en p1. Voor het gemak kan je een punt pn+1=p1 definiëren. We krijgen dan uniformer formules. De richting van de ribben van V noemen we v.
Een punt in zijvlak gi kunnen we dus voorstellen als: mi. v +li. pi+(1-li) pi+1 waarbij mi reëel is en li tussen 0 en 1 ligt. Een punt op een ribbe Ri door pi kunnen we voorstellen als pi+ ri. v.

We benoemen voor V’ ook qm+1= q1. De richting van de ribben van V’ is v’. De zijvlakken definiëren we analoog als boven: gi:i=1..m en een punt erop stellen we voor als: mi. v’ +li. qi+(1-li) qi+1 waarbij mi reëel is en li tussen 0 en 1 ligt. Een punt op een ribbe R’i door qi kunnen we voorstellen als qi+ ri. v’.

De hoekpunten van de gezochte veelhoeken berekenen we in principe door een ribbe Ri te snijden met gj en R’i te snijden met gj. Dit komt neer op het oplossen van een (3x3) stelsel naar l, m en r. Let erop dat we enkel bruikbare hoekpunten vinden waar lÎ[0,1]. In totaal zijn er zo 2.n.m stelsels en als we enkel de hoekpunten berekenen weten we nog niet hoe we ze moeten groeperen en sorteren tot ruimteveelhoeken. We moeten dus nog een intelligente manier vinden om onze punten in de juiste volgorde te zetten.

De clue is de volgende : als we een snijpunt hebben van een ribbe Ri met een vlak gj, dan kunnen we een volgend hoekpunt van de ruimteveelhoek enkel vinden:
waar Ri+1 snijdt met gj
waar Ri-1 snijdt met gj
waar R’j snijdt met gi-1
waar R’j snijdt met gi
waar R’j+1 snijdt met gi-1
waar R’j+1 snijdt met gi
Minstens 2 van deze snijdingen moeten een bruikbaar punt opleveren. In totaal moeten we normaal precies 2 verschillende punten vinden (tenzij in een ontaard geval): het vorige en het volgende hoekpunt op de doorsnede.
Zodra we een eerste volgend hoekpunt hebben, verschuiven we en passen we hetzelfde zoekalgortime toe. Omdat alle doorboringen gesloten ruimteveelhoeken zijn, moeten we uiteindelijk op het vertrekpunt terugkomen. Zo hebben we een enkele gesloten ruitmeveelhoek volledig afgelopen.

Resterende vragen:
1. hoe vind je een eerste snijpunt ?
2. hoe weet je dat er geen andere ruimteveelhoeken meer zijn (bv.: gescheiden ingangs- en uitgangsdoorsnede)

Hier heb ik niet direct een intelligenter antwoord dan:
1. Trial and error
2. Alle hoekpunten overlopen die nog niet eerder in een doorsnede-veelhoek gezet zijn

Op basis van dit kan je al een eerste versie van je programma maken. Mochten er dan nog problemen zijn, laat het dan maar horen.

Groetjes,
Johan

andros
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 29 augustus 2003



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3