WisFaq!

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
26-8-2003

Antwoord

Hoi,

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

Gegeven een vlakke veelhoek met n hoekpunten p_i: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 q_i: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 g_i:i=1..n waarbij g_i loodrecht op het XY-vlak staat en door p_i en p_i+1 loopt voor in en voor g_n door p_n en p₁. Voor het gemak kan je een punt p_n+1=p₁ definiëren. We krijgen dan uniformer formules. De richting van de ribben van V noemen we v.
Een punt in zijvlak g_i kunnen we dus voorstellen als: m_i. v +l_i. p_i+(1-l_i) p_i+1 waarbij m_i reëel is en l_i tussen 0 en 1 ligt. Een punt op een ribbe R_i door p_i kunnen we voorstellen als p_i+ r_i. v.

We benoemen voor V’ ook q_m+1= q₁. De richting van de ribben van V’ is v’. De zijvlakken definiëren we analoog als boven: g’_i:i=1..m en een punt erop stellen we voor als: m’_i. v’ +l’_i. q_i+(1-l’_i) q_i+1 waarbij m’_i reëel is en l’_i tussen 0 en 1 ligt. Een punt op een ribbe R’_i door q_i kunnen we voorstellen als q_i+ r’_i. v’.

De hoekpunten van de gezochte veelhoeken berekenen we in principe door een ribbe R_i te snijden met g’_j en R’_i te snijden met g_j. 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 R_i met een vlak g’_j, dan kunnen we een volgend hoekpunt van de ruimteveelhoek enkel vinden:
waar R_i+1 snijdt met g’_j
waar R_i-1 snijdt met g’_j
waar R’_j snijdt met g_i-1
waar R’_j snijdt met g_i
waar R’_j+1 snijdt met g_i-1
waar R’_j+1 snijdt met g_i
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
29-8-2003