Abstand 2er Strecken

Flamefire · Verfasst: Di 15.09.09 22:35

Ich will den Abstand 2er Strecken (nicht geraden!) in der Ebene berechnen. Da das sehr häufig gemacht wird, muss es sehr schnell gehen.

Eigendlich brauche ich nicht den abstande, sondern nur ob deren Abstand unter einem Wert liegt.
Meine derzeitige funktion sieht so aus:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:

function LineDistBelow(cX1,cY1,cX2,cY2,lX1,lY1,lX2,lY2,minDist:Integer): Boolean;
var a1,a2,b1,b2,c1,c2,tmp,tmp2:Integer;
    sxf,syf,dx,dy,d,t:Double;
begin
  a1 := cY2-cY1;
  b1 := cX1-cX2;
  c1 := a1*cX1 + b1*cY1;
  a2 := lY2-lY1;
  b2 := lX1-lX2;
  c2 := a2*lX1 + b2*lY1;

  tmp:=(a1*b2-a2*b1);
  tmp2:=(c1*b2-c2*b1);
  if(tmp=0) then begin //Lines parallel
    if(tmp2=0) then begin//Lines on 1 Line
      tmp:=(cX1-lX1)*(cX1-lX1)+(cY1-lY1)*(cY1-lY1);
      if(tmp<minDist) then exit(true);
      tmp:=(cX2-lX1)*(cX2-lX1)+(cY2-lY1)*(cY2-lY1);
      if(tmp<minDist) then exit(true);
      tmp:=(cX1-lX2)*(cX1-lX2)+(cY1-lY2)*(cY1-lY2);
      if(tmp<minDist) then exit(true);
      tmp:=(cX2-lX2)*(cX2-lX2)+(cY2-lY2)*(cY2-lY2);
      if(tmp<minDist) then exit(true);
      exit(false);
    end;
    d:=hypot(b1,a1);
    dx:=b1/d;dy:=a1/d;
    t:=(lX1-cX1)*dx+(lY1-cY1)*dy;
    dx:=cX1+t*dx;
    dy:=cY1+t*dy;
    exit((dx-lX1)*(dx-lX1)+(dy-lY1)*(dy-lY1)<minDist);
  end;
  sXf := tmp2/tmp;
  sYf := (a1*c2-a2*c1)/tmp;
  if (sXf > cX1) and (sXf > cX2)
    or (sXf < cX1) and (sXf < cX2)
    or (sYf > cY1) and (sYf > cY2)
    or (sYf < cY1) and (sYf < cY2) then begin
      tmp:=Round(sXf);tmp2:=Round(sYf);
      //intersection point not on line1
      if(Abs(tmp-cX1)>Abs(tmp-cX2)) or (Abs(tmp2-cY1)>Abs(tmp2-cY2)) then begin
        c1:=cX2;c2:=cY2;
      end else begin
        c1:=cX1;c2:=cY2;
      end;
      Result:=(PointLineDistSqr(lX1,lY1,lX2,lY2,c1,c2)<minDist);
  end else if(sXf > lX1) and (sXf > lX2)
    or (sXf < lX1) and (sXf < lX2)
    or (sYf > lY1) and (sYf > lY2)
    or (sYf < lY1) and (sYf < lY2) then begin
      tmp:=Round(sXf);tmp2:=Round(sYf);
      //intersection point not on line2
      if(Abs(tmp-lX1)>Abs(tmp-lX2)) or (Abs(tmp2-lY1)>Abs(tmp2-lY2)) then begin
        c1:=lX2;c2:=lY2;
      end else begin
        c1:=lX1;c2:=lY1;
      end;
      Result:=(PointLineDistSqr(cX1,cY1,cX2,cY2,c1,c2)<minDist);
    end else Result:=true;
end;

Aber irgendwas stimmt da manchmal nicht ganz. vl hab ich irgendewo nen Fehler übersehen.
Kann den jemand erkennen und vl verbesserungen bzgl geschwindigkeit finden?

Desweiteren habe ich 2 weitere Funktionen, die das gleiche speziell für Strecken machen, von denen eine die Horizontal bzw vertikal ist. Als weitere Spezialisierung ist bei diesen funktionen gegeben, dass der erste punkt der hor/ver strecke kleiner ist als der 2. (Spart abfragen)
aber da seh ich grad nicht durch. hab die schon 5 mal neugeschrieben. derzeit hab ich nur ne halbfertige variante:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

function LineDistBelowH(cX1,cY1,cX2,cY2,lX1,lY,lX2,minDist:Integer): Boolean;
var dx,dy,sp,d1,d2:Integer;
begin
  if(cY1-minDist<lY) and (cY2-minDist<lY)
    or(cY1+minDist>lY) and (cY2+minDist>lY) then exit(false);
  dy:=cY2-cY1;
  if(dy=0) then begin //Lines Parralel
    if(cY1=lY) then begin//lines on 1 Line
      if((cX1<lX1) or (cX1>lX2))
      and ((cX2<lX1) or (cX2>lX2)) then begin
          if(cX1-lX1<minDist) then exit(true);
          if(cX2-lX1<minDist) then exit(true);
          if(cX1-lX2<minDist) then exit(true);
          if(cX2-lX2<minDist) then exit(true)
          else exit(false);
      end else exit(true);
    end else exit(Abs(cY1-lY)<minDist);
  end;
  dx:=cX2-cX1;
  if(cY1>=lY) and (cY2<=lY)
  or (cY1<=lY) and (cY2>=lY) then begin
    sx:=Round(cX1+dx/dy*(lY-cY1));
    if(sx>=lX1) and (sx<=lX2) then exit(true);//Intersection
  end;
  if(cX1>=lX1) and (cX1<=lX2) then begin
    if(Abs(cY1-lY)<minDist) then exit(true);
    if(cX2>=lX1) and (cX2<=lX2) then begin
      if(Abs(cY2-lY)<minDist) then exit(true)
      else exit(false);
    end;
  end else if(cX2>=lX1) and (cX2<=lX2) and (Abs(cY2-lY)<minDist) then exit(true);

  Result:=(cY1-lY<minDist) or (cY2-lY<minDist);
end;

wie man sieht, ist die strecke mit präfix "l" die Horizontale.
Meine idee hier ist: ich brauch den schnittpunkt nicht allgemein ausrechnen, da es letztenendes auf ne art nullstellenbestimmung rausläuft. außerdem kann abgebrochen werden, falls sich die 1. strecke (die beliebig liegt) mehr als minDist px rechts/links der 2. strecke befindet. auch die abstandsbestimmung kann vereinfacht werden.
aber bei den ganzen ifs verwirre ich mich selbst ;-)

Kann mir hier jemand weiterhelfen?

Flamefire · Verfasst: Mi 16.09.09 11:28

Hab ne neue variante der 2. funktion:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:

function LineDistBelowH(cX1,cY1,cX2,cY2,lX1,lY,lX2,minDist:Integer): Boolean;
var dx,dy:Integer;
    p1In,p2In:Boolean;
begin
  //Line left or right or below or above
  if(cY1+minDist<lY) and (cY2+minDist<lY)
    or(cY1-minDist>lY) and (cY2-minDist>lY)
    or(cX1+minDist<lX1) and (cX2+minDist<lX1)
    or(cX1-minDist>lX2) and (cX2-minDist>lX2) then exit(false);
  p1In:=(cX1>=lX1) and (cX1<=lX2);
  p2In:=(cX2>=lX1) and (cX2<=lX2);
  dy:=cY2-cY1;
  dx:=cX2-cX1;
  if(cY1=lY) and (p1In)
    or(cY2=lY) and (p2In) then exit(true);//1 point on line
  if(dy=0) then begin   //lines parallel
    if(cY1=lY) and //same height
      ((cX1<lX1) and (cX2>lX2)
      or(cX2<lX1) and (cX1>lX2)) then exit(true);//line on line
  end else   //Lines not parallel
  if((cY1>=lY) and (cY2<=lY)
  or (cY1<=lY) and (cY2>=lY)) then begin//and intersection possible
    if(p1In) and (p2In) then exit(true); //Intersection
    dx:=Round(cX1+dx/dy*(lY-cY1));
    if(dx>=lX1) and (dx<=lX2) then exit(true);//Intersection
  end;
  //No intersection
  if(p1In) then begin
    if(Abs(lY-cY1)<minDist) then exit(true);
  end else begin
    dx:=minDist*minDist;
    if(PointDistSqr(cX1,cY1,lX1,lY)<dx) then exit(true);
    if(PointDistSqr(cX1,cY1,lX2,lY)<dx) then exit(true);
  end;
  if(p2In) then begin
    if(Abs(lY-cY2)<minDist) then exit(true);
  end else if(dy<>0) or (not p1In) then begin //just check 2nd Point if not "lines parallel and p1 is in line"
    if(not p1In) then dx:=minDist*minDist;
    if(PointDistSqr(cX2,cY2,lX1,lY)<dx) then exit(true);
    if(PointDistSqr(cX2,cY2,lX2,lY)<dx) then exit(true);
  end;
  Result:=false;
end;

glaube aber nicht, dass es vollständig ist...scheint zu einfach ^^

F34r0fTh3D4rk · Verfasst: Mi 16.09.09 14:02

Wenn es dir schnell genug ist, könntest du vier mal den Abstand Punkt<->Gerade ausrechnen. Das Minimum sollte dann dein gesuchter Abstand sein. Solltest du während der Berechnung einen Abstand finden, der kleiner als dein Schwellwert ist, so kannst du direkt aufhören (early out).
Das Ganze funktioniert aber nur, wenn sich die Strecken nicht schneiden.
Allerdings ist es so weit ich weiß so, dass die Abstände Vorzeichen haben, die anzeigen, auf welcher "Seite" der Geraden sich der Punkt befindet. An einem Vorzeichenwechsel könntest du dann den Schnitt der beiden Strecken erkennen und direkt Null zurückgeben.

PseudoCode (ungetestet):

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

for (int i=0; i<anzahl_Strecken; i++) {  
  for (int j=i; j>=0; j--) {
    dist1 = bestimme_Abstand(strecken[i], strecken[j].punkt1);
    dist2 = bestimme_Abstand(strecken[i], strecken[j].punkt2);
    if (unterschiedliches_Vorzeichen(dist1, dist2))
      return true;
    dist_gesamt = min(abs(dist1), abs(dist2));
    if (dist_gesamt < schwellwert)
      return true;
  }
}  
return false;

Flamefire · Verfasst: Mi 28.10.09 11:44

bin mal wieder da mit dem problem.
meine lösung scheint nur unzurechend zu funktionieren, oder ich habe einen fehler.
Problemstellung mal genauer: eine linie ist auf den schnittpunkt mir einer anderen zu überprüfen (vorherige plausibilitätsprüfung mittels hitbox erfolgt)
und das ganze möglichst sehr schnell, da sehr häufige ausführung

bisheriger code:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:

function LineDistBelow(cX1,cY1,cX2,cY2,lX1,lY1,lX2,lY2,minDist:Integer): Boolean;
var aY,bY,aX,bX,c1,c2,tmp,tmp2,sxf,syf,dx,dy,d,t:Double;
    PX,PY:Integer;
begin
  aY := cY2-cY1;
  aX := cX1-cX2;
  bY := lY2-lY1;
  bX := lX1-lX2;
  c1 := aY*cX1 + aX*cY1;
  c2 := bY*lX1 + bX*lY1;

  tmp:=(aY*bX-bY*aX);
  tmp2:=(c1*bX-c2*aX);
  if(tmp=0) then begin //Lines parallel
    if(tmp2=0) then begin//Lines on 1 Line
      tmp:=(cX1-lX1)*(cX1-lX1)+(cY1-lY1)*(cY1-lY1);
      if(tmp<minDist) then exit(true);
      tmp:=(cX2-lX1)*(cX2-lX1)+(cY2-lY1)*(cY2-lY1);
      if(tmp<minDist) then exit(true);
      tmp:=(cX1-lX2)*(cX1-lX2)+(cY1-lY2)*(cY1-lY2);
      if(tmp<minDist) then exit(true);
      tmp:=(cX2-lX2)*(cX2-lX2)+(cY2-lY2)*(cY2-lY2);
      if(tmp<minDist) then exit(true);
      exit(false);
    end;
    d:=hypot(aX,aY);
    dx:=aX/d;dy:=aY/d;
    t:=(lX1-cX1)*dx+(lY1-cY1)*dy;
    dx:=cX1+t*dx;
    dy:=cY1+t*dy;
    exit((dx-lX1)*(dx-lX1)+(dy-lY1)*(dy-lY1)<minDist);
  end;
  sXf := tmp2/tmp;
  sYf := (aY*c2-bY*c1)/tmp;
//bis hierhin schnittpunkts untersuchung (sXf/sYf sind schnittpunkte der geraden (nicht strecken)
//jetzt muss das ganze noch auf strecken umgewandelt werden
//teste also bei keinem schnittpunkt die randpunkte einer strecke
  if (sXf > cX1) and (sXf > cX2)
    or (sXf < cX1) and (sXf < cX2)
    or (sYf > cY1) and (sYf > cY2)
    or (sYf < cY1) and (sYf < cY2) then begin
      tmp:=Round(sXf);tmp2:=Round(sYf);
      //intersection point not on line1
      if(Abs(tmp-cX1)>Abs(tmp-cX2)) or (Abs(tmp2-cY1)>Abs(tmp2-cY2)) then begin
        PX:=cX2;PY:=cY2;
      end else begin
        PX:=cX1;PY:=cY1;
      end;
      Result:=(PointLineDist(lX1,lY1,lX2,lY2,PX,PY)<minDist);
  end else if(sXf > lX1) and (sXf > lX2)
    or (sXf < lX1) and (sXf < lX2)
    or (sYf > lY1) and (sYf > lY2)
    or (sYf < lY1) and (sYf < lY2) then begin
      tmp:=Round(sXf);tmp2:=Round(sYf);
      //intersection point not on line2
      if(Abs(tmp-lX1)>Abs(tmp-lX2)) or (Abs(tmp2-lY1)>Abs(tmp2-lY2)) then begin
        PX:=lX2;PY:=lY2;
      end else begin
        PX:=lX1;PY:=lY1;
      end;
      Result:=(PointLineDist(cX1,cY1,cX2,cY2,PX,PY)<minDist);
    end else Result:=true;
end;

die variante mit den 4 mal den abstand punkt<>strecke prüfen, sieht auch ganz gut aus.
nur sehe ich da probleme bei schnittpunkten.
das mit dem unterschiedlichen vorzeichen könnte ja funktionieren, wenn da nicht strecken statt geraden wären
habe dann gedacht man könnte gucken, ob für BEIDE strecken BEIDE punkte der jeweils anderen strecke auf verschiedenen seiten der strecke liegen-->schnittpunkt
aber das gibt probleme bei (fast) parrallelen strecken aufgrund der genauigkeit.
hier mal die funktionen, die ich derzeit hätte:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:

function PointLineDist(lX1,lY1,lX2,lY2,PX,PY:Integer): Integer;overload;
var
  dx,dy,t,xX,xY,d:Double;
  px2,py2:Integer;
begin
  dx := lX2 - lX1;
  dy := lY2 - lY1;
  d := hypot(dx, dy);
  if d = 0 then
    raise Exception.Create('A and B are the same-->No Line !!');
  dx:=dx/d;
  dy:=dy/d;
  px2 := PX - lX1;
  py2 := PY - lY1;
  t:=px2*dx+py2*dy;
  if(t<=0) then begin
    xX:=lX1;
    xY:=lY1;
  end else if(t>=d) then begin
    xX:=lX2;
    xY:=lY2;
  end else begin
    xX:=lX1+t*dx;
    xY:=lY1+t*dy;
  end;
  Result:=Round(sqrt((xX-Px)*(xX-Px)+(xY-Py)*(xY-Py)));
end;
//...
//strecke p1<->p2; punkte a und b auf gleicher seite?
function SameSide(p1x,p1y,p2x,p2y,ax,ay,bx,by:Integer):Boolean;
var cp1,cp2:Integer;
begin
  Dec(bX,aX);
  Dec(bY,aY);
  cp1:=bX*(p1Y-aY)-bY*(p1X-aX);
  cp2:=bX*(p2Y-aY)-bY*(p2X-aX);
  if(cp1<0) then Result:=cp2<=0
  else if(cp1>0) then Result:=cp2>=0
  else Result:=true;
end;

kann mir da jemand weiterhelfen?

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme