WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Re: Re: Probleem met coordinaatbepaling (Wanneer ligt een punt in een driehoek?)

Dit is een reactie op vraag 12006

Ik ben op zoek naar de driehoek waarin het vrije coordinaat zich bevind en niet naar het dichtstbijzijnde coordinaat. Zoals in het plaatje kan het zijn dat het coordinaat dat het dichtste bij het vrije coordinaat ligt niets met de driehoek te maken hebben waarin het vrije coordinaat ligt.
Ik zoek een berekening die ik in een programma kan uitvoeren waarbij er niet al te veel gezocht moet worden want ik meer dan een paar miljoen driehoeken hebben en de berekening moet in maximaal 40 milliseconden gevonden hebben welk driehoek degene is waarop ik kijk.

Ik hoop dat dit enige duidelijkheid biedt. Alvast bedankt.
Joël S
Leerling mbo - dinsdag 10 juni 2003

Antwoord

Het gaat er dus om om te bepalen wanneer een punt binnen een driehoek ligt.

Van medebeantwoordster Anneke kreeg ik de volgende tip:

Stel je hebt de punten A(a1,a2), B(b1,b2) en C(c1,c2) en het punt P(p1,p2) .
Om na te gaan of P binnen driehoek ABC ligt moet je dan het volgende doen:

Bereken
z = det(a,b) + det(b,c) + det(c,a)
x = (det(a,b) + det(b,p) + det(p,a))/z
y = (det(c,a) + det(a,p) + det(p,c))/z

(De grootheid det(a,b) noemen we de determinant van de vectoren OA en OB deze bereken je als volgt det(a,b)=a1*b2-a2*b1. De andere determinanten bereken je op analoge manier.)

Als nu x en y beide tussen 0 en 1 liggen, en x+y is kleiner dan 1, dan ligt punt P binnen driehoek ABC, en omgekeerd geldt ook: als P binnen de driehoek ligt, dan enz...

Nu is de vraag of als je deze berekening meer dan 1 miljoen keer uitvoert dit snel genoeg is voor jouw programma.
Op mijn computer (450Mhz) en met Delphi is dit helaas niet het geval. (ongeveer 10 keer te langzaam).
Je moet dus een eenvoudiger criterium hebben om kandidaatdriehoeken te selecteren om daarna bovenstaande berekening uit te voeren. Ik heb toen het volgende gedaan:

Ik bereken eerst:
xmin=minimum(a1,b1,c1), xmax=maximum(a1,b1,c1) en
ymin=minimum(a2,b2,c2), xmax=maximum(a2,b2,c2)
De punten (xmin,ymin) en (xmax,ymax) vormen nu de hoekpunten linksonder en rechtsboven van de rechthoek waar driehoek ABC precies in past.
Zo dus:

Alleen als P binnen deze rechthoek ligt heeft het zin om de uitgebreidere berekening met de determinanten uit te voeren. Als je dus deze twee punten bij het inlezen van je driehoek als extra gegevens opslaat heb je een eenvoudige test om na te gaan of die complexere berekening nodig is.
Onderstaande code is een gedeelte van het programma dat ik heb gebruikt om de definitieve versie te testen

function det(aa1,aa2,bb1,bb2:integer):integer; begin result:=aa1*bb2-aa2*bb1 end; function inside(a1,a2,b1,b2,c1,c2,p1,p2,minx,maxx,miny,maxy:integer):boolean; var x,y:extended; z:integer; begin if (p1minx) then if (p1maxx) then if (p2miny) then if (p2maxy) then begin z:=det(a1,a2,b1,b2)+det(b1,b2,c1,c2)+det(c1,c2,a1,a2); x:=(det(a1,a2,b1,b2)+det(b1,b2,p1,p2)+det(p1,p2,a1,a2))/z; if ((x0) and (x1)) then begin y:=(det(c1,c2,a1,a2)+det(a1,a2,p1,p2)+det(p1,p2,c1,c2))/z; if ((y0) and (y1)) then if (x+y1) then inside:=true; end; end else inside:=false; end; begin //hoekpunten inlezen a1:=... a2:=... b1:=... b2:=.. c1:=.. c2:=.. minx:=min(min(a1,b1),c1); maxx:=max(max(a1,b1),c1); miny:=min(min(a2,b2),c2); maxy:=max(max(a2,b2),c2); for p1:=1 to fom1.width do for p2:=1 to form1.height do if inside(a1,a2,b1,b2,c1,c2,p1,p2,minx,maxx,miny,maxy)=true then //take action you want

Afhankelijk van de gekozen waarden van de coordinaten van de hoekpunten lukt het op mijn computer net om in de buurt te komen van de door jou opgegeven tijslimiet.
Op demo kun je een demoprogramma ophalen voor deze routine (Delphi broncode+exe)

Veel succes!

Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 20 juni 2003