qt4: herausfinden, ob QPoint auf einer linie

[arne.anka]

hej,
ich habe einen vector mit qpoints, von denen ich mir eine polyline erzeugen lasse.
jetzt möchte ich gerne, dass beim überfahren der linie mit der maus etwas passiert -- mein problem ist ganz einfach, dass ich keinen ansatz habe, effizient zu erkennen, ob die maus gerade über der linie ist, der momentan aktuelle punkt also exakt zwischen start- und endpunkt der line liegt.
kann mich da bitte mal wer tippsen?

[Querdenker]

Hi,

konkretes habe ich zwar im Moment nicht, aber im groben würde ich es so lösen:
Die Polylines bilden ja eine Figur deren Points man in einen Path setzen kann. Dieser Path deckt die Ränder der Figur ab. Nun kann man den Path ganz einfach per Funktion in eine Region umsetzen und mit: PtInRgn() prüfen, ob sich der Mouspointer außerhalb der Figur oder innerhalb der Figur befindet und dementsprechend reagieren.

Qt hat ja da einiges unter Path Stroking

Vielleicht genügt der Wink ja schon

[upsala]

Es gibt garantiert bessere Algorithmen dafür, aber probiers mal damit:

Code: Alles auswählen

QLineF yourLine; //deine Linie
QLineF mouse(yourLine.p1(), mousePos);
if (qAbs(yourLine.angle()-mouse.angle())<=1 &&
   mousePos.x()>=qMin(yourLine.x1(), yourLine.x2()) &&
   mousePos.x()<=qMax(yourLine.x1(), yourLine.x2()) &&
   mousePos.y()>=qMin(yourLine.y1(), yourLine.y2()) &&
   mousePos.y()<=qMax(yourLine.y1(), yourLine.y2())) {
//Treffer
}

[BartSimpson]

oder du benutzt QCanvas. Dort gibt es glaube ich sogar Funktionen dafür.

[Volker]

Vielleicht hilft dir ja auch ein bissle Mathe weiter:

Wenn Du jeweils zwei Punkte betrachtest, zwischen denen eine Linie definiert ist, kannst Du den Abstand eines Punktes (die Position der Maus) von dieser Linie wie folgt berechnen:

Punkt A, Startpunkt der Gerade
Punkt B, Endpunkt der Gerade

dx = B_x - A_x
dy = B_y - A_y

a = A_y - B_y
c = A_x * B_y - B_x * A_y
dAB = sqrt(dx*dx+dy*dy);

wenn Du nun einen Punkt P nimmst und dessen Abstand zur Geraden zwischen A und B berechnen willst funktioniert das wie folgt:

fabs((a * P_x + dx * P_y + c) / dAB) = distance

Wenn Du das fabs weglässt bekommst du noch mit auf welcher Seite der Geraden der Punkt liegt.

Ich glaub es gibt auch ein effizientes Verfahren für Polygone, hab ich aber leider vergessen.

[arne.anka]

Vielleicht hilft dir ja auch ein bissle Mathe weiter:

das war mein ausgangspunkt ;-) ich weiss meistens, dass es mathematsich geht -- aber selten, wie ...

fabs((a * P_x + dx * P_y + c) / dAB) = distance

ich war jetzt angekommen bei
yA=[(yC-yB)/(xC-xB)] xA + (yC - [(yC-yB)/(xC-xB)] xC )
wobei A die maus-position, B und C die endpunkte der linie sind
problematisch ist es noch mit senkrechten linien -- die haben eine steigung von 0 -- und das führt zur didvision durch 0 ...

Ich glaub es gibt auch ein effizientes Verfahren für Polygone, hab ich aber leider vergessen.

brauche ich auch nicht -- ich habe es immer mit linien zu tun (bzw polylines) aber nie mit geschlossenen polygonen.

[arne.anka]

mir scheint, dass mit deinem ansatz nicht geprüft wird, ob die maus sich auch _zwischen_ den beiden punkten befindet?
ich bekomme auch dann 0 als distanz, wenn ich ausserhalb des durch die beiden punkte gegebenen streckenabschnittes auf die gerade klicke ...
habe ich das was verdreht oder ist das "broken by design"?
trotzdem vielen dank natürlich! immerhin kann ich mit deinem ansatz sehr viel besser etwas unschärfe reinbringen ("distanz <= 10"), um das mühselige suchen nach exakt der linie zu vermeiden ...

[Christian81]

Ich habe es nicht ganz durchgelesen, aber evtl. funktioniert es schneller(?) mit dem Strahlensatz.

Punkt A(x1,y1)
Punkt B(x2,y2)

und meine Mausposition C(xc,yc)

Wenn C und B auf einer Strecke mit dem Startpunkt A liegen, gilt

(x2 - x1) / (y2 - y1) == (xc - x2) / (yc - y1)

Oder liege ich da falsch?

[beReal]

Strahlensatz ist eigentlich ein ganz guter Ansatz.

In meinem eigenen Projekt lass ich folgendes Prüfen:


geg:
Punkt A
Punkt B
und Punkt M(aus)

Ich lasse erstens prüfen, ob die Maus sich quasi im Viereck, welches die Punkte A und B aufspannen, befindet. Danach berechne ich noch den Anstieg der Geraden AB und den Anstieg von AM. Sind beide annähernd gleich, muss M auf der Geraden AB liegen.

Anstieg = dy/dx = (B.y - A.y) / (B.x - A.x) = (M.y - A.y) / (M.x - A.x)

[upsala]

Ich hab noch eine andere Idee:

Code: Alles auswählen

bool intersect(QLineF deineLinie, QPoint mousePos)
  int d=3; //max. Abstand Maus<->Linie

  QLineF l(mousePos+QPoint(-d, -d), mousePos+QPoint(d, -d));
  if (deineLinie.intersect(l, 0)!=QLineF::NoIntersection) {
    return true;
  }

 l=QLineF(mousePos+QPoint(d, -d), mousePos+QPoint(d, d));
  if (deineLinie.intersect(l, 0)!=QLineF::NoIntersection) {
    return true;
  }

 l=QLineF(mousePos+QPoint(d, d), mousePos+QPoint(-d, d));
  if (deineLinie.intersect(l, 0)!=QLineF::NoIntersection) {
    return true;
  }

 l=QLineF(mousePos+QPoint(-d, d), mousePos+QPoint(-d, -d));
  if (deineLinie.intersect(l, 0)!=QLineF::NoIntersection) {
    return true;
  }

  return false;
}

[arne.anka]

danke für die rege beteiligung ;-)
ich habe es mit volker's ansatz gelöst (nicht exakt, aber mit einer vereinfachten formel), der zudem - ich glaube, ich erwähnte es schon - den vorteil hat, dass ich etwas unschärfe in das klicken bringen kann, man muss also die linie nicht exakt treffen.
die "offenen enden" fange ich ab, in dem ich prüfe, ob mein maus-punkt "zwischen" den beiden anderen punkten liegt.
klappt sehr gut.

Code: Alles auswählen

		double tDist=B.y()*aPoint.x() + A.y()*(B.x()-aPoint.x()) + A.x()*(aPoint.y()-B.y()) - aPoint.y()*B.x();
		int tMinX=qMin(A.x(), B.x())-myDist;
		int tMinY=qMin(A.y(), B.y())-myDist;
		int tMaxX=qMax(A.x(), B.x())+myDist;
		int tMaxY=qMax(A.y(), B.y())+myDist;
		if(tDist<=myDist && ((tMinX <= aPoint.x() && aPoint.x() <= tMaxX) && (tMinY <= aPoint.y() && aPoint.y() <= tMaxY)))
			return true;

myDist ist die unschärfe.