WisFaq!

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

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 Smit
10-6-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!

hk
20-6-2003