Ik kan wel wat pro-hulp gebruiken met dit probleem. Ik zal het proberen te visualiseren:
Je zit aan je buro, je hebt er ergens een punaise in geprikt. Boven het buro hangt een lamp. Je houdt een A4'tje tussen de lamp en het buro, zodat de schaduw een viervlak (als je dat zo noemt??) op het buro projecteert. Met een lineaaltje kun je alle punten en afstanden opmeten.
Hoe kun je bewijzen dat de punaise binnen of buiten het schaduwvlak valt?
Ik ben op zoek naar een 'elegante' oplossing, die ik in een paar regels code aan de computer kan uitleggen, zeg maar.
Ik heb een aantal ideeën, maar helaas is mijn wiskundige toolbox niet toereikend om de hele oplossing te zien:
idee 1: als punt E in viervlak ABCD ligt, dan is de oppervlakte van de driehoeken EAB, EBC, ECD en EDA gelijk aan de opppvlakte van ABCD - probleem: alles is ongelijkzijdig; wat het berekenen van de oppervlakte bemoeilijkt
idee 2: een stelsel van logische waarden E.x > A.x && E.y > A.y && enz.. probleem: in mijn échte probleem liggen zijn de punten niet noodzakelijkerwijs positief, dan moet ik met te veel dingen rekening houden.
Volgens mij kan het simpeler en korter. Kunnen jullie hier eens over nadenken en misschien ideeën aandragen?
Ligt punt in viervlak?
Re: Ligt punt in viervlak?
Het is een vierhoek ABCD.
Stel deze vierhoek is gegeven door de punten
A = (xa, ya)
B = (xb, yb)
C = (xc, yc)
D = (xd, yd)
waarbij AC een diagonaal is.
Je wil bepalen of punt E = (x, y) in/op vierhoek ABCD ligt.
Je ideeen zijn goed:
IDEE 1:
Programmeer eerst een hulpfunctie die de lengte van lijnstukken berekent:
De lengte van lijnstuk PQ tussen punten P = (xp, yp) en Q = (xq, yq) kan je vinden via de stelling van Pythagoras:
^2 \;+\; (yp-yq)^2})
Vervolgens gebruik je de formule van Heron om de oppervlakten van alle driehoeken te berekenen:
(zie bv http://nl.wikipedia.org/wiki/Formule_van_Heron):
Gegeven de lengtes van de zijden van een driehoek (a, b en c) bereken je eerst s = de helft van de omtrek van de driehoek:
en vervolgens bereken hiermee het oppervlak O van die driehoek:
(s-b)(s-c)})
Programmeer hiervoor ook een functie.
Het oppervlak van vierhoek ABCD = oppervlak driehoek ABC + oppervlak driehoek ACD
De oppervlakten van de overige driehoeken (ABE, BCE, CDE en DAE) bereken je direct met deze formules.
IDEE 2:
Gaat goed als je barycentrische coordinaten gebruikt,
zie bv http://en.wikipedia.org/wiki/Barycentri ... ate_system
Test hiermee of je punt E binnen of op driehoek ABC ligt:
- zo ja: dan ligt E binnen of op ABCD
- zo nee: test of je punt E binnen of op driehoek ACD ligt:
- - zo ja: dan ligt E binnen of op ABCD
- - zo nee: dan ligt E buiten vierhoek ABCD
Voorbeeld:
Als je wil testen of punt E = (x, y) in of op driehoek ABC ligt,
dan bereken je eerst:
L1 = ((yb-yc)*(x-xc) + (xc-xb)*(y-yc)) / ((yb-yc)*(xa-xc) + (xc-xb)*(ya-yc));
L2 = ((yc-ya)*(x-xc) + (xa-xc)*(y-yc)) / ((yb-yc)*(xa-xc) + (xc-xb)*(ya-yc));
L3 = 1 - L1 - L2;
(dit zijn de formules voor lambda1, lambda2 en lambda3 op die wiki-pagina)
en test vervolgens of ten minste 1 van die 3 L-waarden negatief is:
ALS ((L1 < 0) OF (L2 < 0) OF (L3 < 0))
DAN: (x, y) ligt buiten driehoek ABC
ANDERS: (x, y) ligt op of in driehoek ABC
Analoog voor driehoek ACD.
Kom je hiermee verder?
Stel deze vierhoek is gegeven door de punten
A = (xa, ya)
B = (xb, yb)
C = (xc, yc)
D = (xd, yd)
waarbij AC een diagonaal is.
Je wil bepalen of punt E = (x, y) in/op vierhoek ABCD ligt.
Je ideeen zijn goed:
IDEE 1:
Programmeer eerst een hulpfunctie die de lengte van lijnstukken berekent:
De lengte van lijnstuk PQ tussen punten P = (xp, yp) en Q = (xq, yq) kan je vinden via de stelling van Pythagoras:
Vervolgens gebruik je de formule van Heron om de oppervlakten van alle driehoeken te berekenen:
(zie bv http://nl.wikipedia.org/wiki/Formule_van_Heron):
Gegeven de lengtes van de zijden van een driehoek (a, b en c) bereken je eerst s = de helft van de omtrek van de driehoek:
en vervolgens bereken hiermee het oppervlak O van die driehoek:
Programmeer hiervoor ook een functie.
Het oppervlak van vierhoek ABCD = oppervlak driehoek ABC + oppervlak driehoek ACD
De oppervlakten van de overige driehoeken (ABE, BCE, CDE en DAE) bereken je direct met deze formules.
IDEE 2:
Gaat goed als je barycentrische coordinaten gebruikt,
zie bv http://en.wikipedia.org/wiki/Barycentri ... ate_system
Test hiermee of je punt E binnen of op driehoek ABC ligt:
- zo ja: dan ligt E binnen of op ABCD
- zo nee: test of je punt E binnen of op driehoek ACD ligt:
- - zo ja: dan ligt E binnen of op ABCD
- - zo nee: dan ligt E buiten vierhoek ABCD
Voorbeeld:
Als je wil testen of punt E = (x, y) in of op driehoek ABC ligt,
dan bereken je eerst:
L1 = ((yb-yc)*(x-xc) + (xc-xb)*(y-yc)) / ((yb-yc)*(xa-xc) + (xc-xb)*(ya-yc));
L2 = ((yc-ya)*(x-xc) + (xa-xc)*(y-yc)) / ((yb-yc)*(xa-xc) + (xc-xb)*(ya-yc));
L3 = 1 - L1 - L2;
(dit zijn de formules voor lambda1, lambda2 en lambda3 op die wiki-pagina)
en test vervolgens of ten minste 1 van die 3 L-waarden negatief is:
ALS ((L1 < 0) OF (L2 < 0) OF (L3 < 0))
DAN: (x, y) ligt buiten driehoek ABC
ANDERS: (x, y) ligt op of in driehoek ABC
Analoog voor driehoek ACD.
Kom je hiermee verder?
Re: Ligt punt in viervlak?
Perfect! Dit zet me op het goede spoor. De formule van Heron is goed te begrijpen. Barycentrische coördinaten zijn wat ingewikkelder (begrijp er niet veel van moet ik bekennen) maar gelukkig heb je de formule voor me uitgeschreven. Daar kan ik wel mee aan de slag.
Ben er inmiddels ook achter gekomen dat ik niet de enige ben met dit probleem. Zoeken op 'Point in polygon', 'Point in square' en 'hit test' levert een hoop bruikbare ideeën, waar ik op dit moment de meest begrijpelijke uit probeer te halen
http://en.wikipedia.org/wiki/Point_in_polygon
oei, valsspelen is ook mogelijk in C#
https://msdn.microsoft.com/en-us/librar ... -snippet-1
Ben er inmiddels ook achter gekomen dat ik niet de enige ben met dit probleem. Zoeken op 'Point in polygon', 'Point in square' en 'hit test' levert een hoop bruikbare ideeën, waar ik op dit moment de meest begrijpelijke uit probeer te halen
http://en.wikipedia.org/wiki/Point_in_polygon
oei, valsspelen is ook mogelijk in C#
https://msdn.microsoft.com/en-us/librar ... -snippet-1
Re: Ligt punt in viervlak?
Merk wel op dat dit alleen werkt voor rechthoeken die bovendien volgens de assen georienteerd zijn.JJD schreef:... oei, valsspelen is ook mogelijk in C#
https://msdn.microsoft.com/en-us/librar ... -snippet-1
Dit werkt dus NIET voor willekeurige vierhoeken ABCD waarvan de zijden en hoeken allemaal verschillend mogen zijn.