| Autor |
Beitrag |
Quivadis
      
Beiträge: 314
UBUNTU 9.04
D2005 PERS, JAVA, D7 Pers.
|
Verfasst: Di 19.04.05 15:28
Hallo Freunde,
habe folgendes Problem:
Auf einer Zeichenfläche befindet sich eine Vektorlinie, ist eine Linie die aus mehreren Segmenten besteht, welche man hin und her bewegen kann. Nun kann man ja die Linie so ziehen, dass sich Linien kreuzen.
Dieses möchte ich irgendwie verhindern.
Ich habe eine funktion die mir sagt ob sich die Linien kreuzen. Da ist es aber schon passiert. Ich brauche so eine Routine die von vornherein verhindert das kreuzungspunkte überhaupt erst auftretten können.
Hat da jemand von euch eine Idee wie ich das machen könnte?
Brauche es dringend.
Die Koordinaten der einzelnen Elemente habe ich in einer Liste. So wie ich es jetzt habe, müsste ich bei jeder Mausbewegung, denn Punkt der Maus mit jeder schon vorhandenen Linie abfragen. Das dauert immer länger je mehr Punkte vorhanden sind.
_________________ Wissen ist macht, nichts wissen macht auch nichts. ODER: Wer nichts weis, kann nichts vergessen.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 19.04.05 15:35
Quivadis hat folgendes geschrieben: | Dieses möchte ich irgendwie verhindern.
Ich habe eine funktion die mir sagt ob sich die Linien kreuzen. Da ist es aber schon passiert. Ich brauche so eine Routine die von vornherein verhindert das kreuzungspunkte überhaupt erst auftretten können.
|
Wie möchtests du das verhindern? Möchtest du eine Funktion, die verhindert, dass man mit der Maus "zu fest an einem Objekt ziehen" kann?
Könntest du das Ziel ein wenig konkreter formulieren?
|
|
Quivadis 
      
Beiträge: 314
UBUNTU 9.04
D2005 PERS, JAVA, D7 Pers.
|
Verfasst: Di 19.04.05 15:45
Habe mal ein Bild angefügt wie ich es meine.
Hoffe du verstehst es.
Das 1. Bild so soll es sein.
2. Bild das darf nicht passieren , wenn man die Linien bewegt
3. Bild die rote Linie darf die anderen Linien nicht kreuzen.
das meine ich mit verhindern.
Einloggen, um Attachments anzusehen!
_________________ Wissen ist macht, nichts wissen macht auch nichts. ODER: Wer nichts weis, kann nichts vergessen.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 19.04.05 15:48
Du willst es also beim Verschieben mit der Maus verhindern? Was soll denn passieren, wenn ich die Maus trotzdem in die verbotene Zone bewege?
|
|
Quivadis 
      
Beiträge: 314
UBUNTU 9.04
D2005 PERS, JAVA, D7 Pers.
|
Verfasst: Di 19.04.05 15:52
Der Anfasser (das sind die schwarzen Vierecke) darf nicht über die Linie gehen. Er soll entweder ein paar pixel davor stehen bleiben oder auf den Ausgangspunkt zurückspringen.
Mein Problem ist wie man das vorher erkennt.
_________________ Wissen ist macht, nichts wissen macht auch nichts. ODER: Wer nichts weis, kann nichts vergessen.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 19.04.05 16:00
Aha, und Schnittpunkte berechnen möchtest du nicht?
Wenn man das gut implementiert, sollte man doch aber eigentlich einige tausend Schnittpunkte ohne weiteres kurz berechnen können.
|
|
Quivadis 
      
Beiträge: 314
UBUNTU 9.04
D2005 PERS, JAVA, D7 Pers.
|
Verfasst: Di 19.04.05 16:06
die schnittpunktberechnung habe ich mir schon geschrieben. Da habe ich aber eine Bereichsprüfung ob der schnittpunkt auf der Strecke ist. Liefert erst dann Ergebniss, meiner Meinung nach, wenn Schnittpukt schon vorhanden ist, dann ist es aber schon zu spät.
Ohne bereichsüberprüfung kommt doch nur mist raus, weil dann mache ich ja geraden raus.
Bin etwas verwirt, aber erfreut zugleich das du mir das vorschlägst was ich erst nehmen wollte. Dachte es gibt da noch irgendwelche anderen Methoden das festzustellen.
Edit: darfst auch nicht vergessen ich male auf ein Image. siehe meine anderen Probleme.
_________________ Wissen ist macht, nichts wissen macht auch nichts. ODER: Wer nichts weis, kann nichts vergessen.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 19.04.05 16:12
Es gibt effiziente Methoden um herauszufinden, wo der Schnittpunkt Gerade-Polygon liegt (Line-Clipping an einem Polygon).
Da du ja aber einfach eine offene "Kurve" hast, kann man die nicht nutzen.
Mir fällt im Moment leider auch nichts anderes ein, als einfach Schnittpunkte zu berechnen. Und falls ein Schnittpunkt auftaucht, die Linie bis zum Schnittpunkt zu verkürzen...
|
|
Quivadis 
      
Beiträge: 314
UBUNTU 9.04
D2005 PERS, JAVA, D7 Pers.
|
Verfasst: Di 19.04.05 16:18
Danke Dir.
Muss ich wohl doch bei jeder Mausbewegung, jede Linie auf Schnittpunkt und/oder auf vermeintlichen Schnittpunkt abfragen und dann noch dazu die Entfernung zu der warscheinlichen Linien die ich treffen/schneiden könnte.
mal sehen wie man das effektiv umsetzen kann.
_________________ Wissen ist macht, nichts wissen macht auch nichts. ODER: Wer nichts weis, kann nichts vergessen.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 19.04.05 16:30
Man kann es schon ein bisschen optimieren. Du kannst z.B. die (minimale) Distanz Punkt-Kurve berechnen und erst dann anfangen Schnittpunkte zu berechnen, wenn die Maus um mindestens diese Distanz bewegt wurde.
So müsstest du nicht bei jeder kleinsten Bewegung alles neu berechnen sondern nur dann, wenn theoretisch der schlimmstmögliche Fall überhaupt eintreten könnte.
Jedoch erfordert diese Distanzberechnung auch eine ziemliche Rechnung... Für jedes Linienstück der Kurve müsstest du die Punkt-Linie Prozedur ausführen.
|
|
Quivadis 
      
Beiträge: 314
UBUNTU 9.04
D2005 PERS, JAVA, D7 Pers.
|
Verfasst: Di 19.04.05 16:38
Das mit den Mausevents ist so eine sache, sprich die kommen nicht regelmässig. So setze ich ja meine Anfasser auf die freihandlinie, immer nach 10 pixeln sollte einer kommen. Theorie: gut gedacht. Resultat: Funktioniert, wenn du die Maus ganz langsam bewegst, sobald Maus zu schnell wird stimmt der Abstand nicht mehr.
Sprich wenn ich es so mache, bekomme ich nicht wirklich hin.
wenn Polygon geschlossen ist, kann man ja nur noch die Anfasser bewegen. da könnte ich die überprüfung beim loslassen der Maustaste machen. wenn Schnittpunkt dann Anfasser zurück auf alte position.
Aber beim anlegen , sprich offenes Polygon dürfte das nicht gehen.
_________________ Wissen ist macht, nichts wissen macht auch nichts. ODER: Wer nichts weis, kann nichts vergessen.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 19.04.05 18:40
Ich denke, Schnittpunkte zu berechnen ist ohne weiteres keine schlechte Lösung. Ich denke du kannst 10'000 Schnittpunkte pro Mausbewegung berechnen, ohne dass man das geringste merkt. Und so viele werden es ja nicht sein. Einige hundert vielleicht.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 19.04.05 18:55
Mit dem hier sollte es eigentlich nicht möglich sein, eine selbstüberschneidende Kurve zu zeichnen. Wenn es passt kannst du ja das hier nehmen und ein bisschen anpassen.
Gruss
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: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137:
| unit Unit1;
interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls;
type TForm1 = class(TForm) Image1: TImage; procedure Image1MouseDown(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer); procedure Image1MouseMove(Sender: TObject; Shift: TShiftState; X, Y: Integer); procedure FormCreate(Sender: TObject); private Points: array of TPoint; procedure CorrectPos(var P: TPoint); procedure DrawCurve; public end;
var Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.CorrectPos(var P: TPoint); procedure Intersect(const A1, A2, B1, B2: TPoint; var D: Extended); Var I, J, K1, K2, K3: integer; E: Extended; begin K1 := B2.Y-B1.Y; K2 := A1.Y-A2.Y; K3 := A2.Y-B2.Y; J := A1.X*(B1.Y-B2.Y)+A2.X*K1+B1.X*(A2.Y-A1.Y)+B2.X*K2; if J=0 then exit; I := A1.X*K3+A2.X*(B2.Y-A1.Y)+B2.X*K2; if J > 0 then begin if (I <= 0) or (I >= J) then exit; end else if (I >= 0) or (I <= J) then exit; I := B1.X*K3+B2.X*(B1.Y-A2.Y)+A2.X*K1; if J > 0 then begin if (I <= 0) or (I >= J) then exit; end else if (I >= 0) or (I <= J) then exit; E := I/J; if E>D then D := E; end; var D, L: Extended; I, Index: Integer; begin D := 0; Index := Length(Points)-1; for I := 0 to Index-2 do Intersect(Points[Index],P,Points[I],Points[I+1],D); if D > 0 then begin L := sqrt(sqr(Points[Index].X-P.X)+sqr(Points[Index].Y-P.Y)); D := D + 1.5/L; P.X := Round(Points[Index].X*D+P.X*(1-D)); P.Y := Round(Points[Index].Y*D+P.Y*(1-D)); end; end;
procedure TForm1.DrawCurve; var I, L: Integer; begin with Image1.Canvas do begin FillRect(ClipRect); L := Length(Points); if L > 0 then begin with Points[0] do MoveTo(X, Y); if L > 1 then for I := 1 to Length(Points)-1 do with Points[I] do LineTo(X,Y); end; end; end;
procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer); var Index: Integer; P: TPoint; begin P.X := X; P.Y := Y; CorrectPos(P); Index := Length(Points); SetLength(Points, Index+1); Points[Index] := P; DrawCurve; end;
procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X, Y: Integer); var Index: Integer; P: TPoint; begin Index := Length(Points)-1; if Index >= 0 then with Image1.Canvas do begin DrawCurve; P.X := X; P.Y := Y; CorrectPos(P); with P do LineTo(X,Y); end; end;
procedure TForm1.FormCreate(Sender: TObject); begin DrawCurve; end;
end. |
//Edit: Unitname korrigiert 
Zuletzt bearbeitet von delfiphan am Mi 20.04.05 21:26, insgesamt 1-mal bearbeitet
|
|
Quivadis 
      
Beiträge: 314
UBUNTU 9.04
D2005 PERS, JAVA, D7 Pers.
|
Verfasst: Di 19.04.05 20:50
Thx, probiere es morgen auf arbeit gleich mal aus. Wird aber sicherlich eine ziemliche arbeit das in mein projekt zu bekommen.
_________________ Wissen ist macht, nichts wissen macht auch nichts. ODER: Wer nichts weis, kann nichts vergessen.
|
|
Quivadis 
      
Beiträge: 314
UBUNTU 9.04
D2005 PERS, JAVA, D7 Pers.
|
Verfasst: Mi 20.04.05 08:42
Hallo delfiphan,
danke Dir.
Das Prog ist so ungefähr das was ich gesucht habe. Es funktioniert auch, mir ist nur nicht ganz klar wie, wenn du Zeit hast könntest du mir mal erklären, was die einzelnen Variablen genau machen.
Ich muss das Prinzip verstanden haben, dann kann ich es auch in mein Prog implementieren. So sehe ich nicht genau durch wie es funktioniert. Am meisten interresiert mich diese doppel-procedure, wusste gar nicht das es sowas gibt und das es funktioniert.
Auf solche implementierungen würde ich nie kommen.
Meine Versuch sieht/sah so aus: 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:
| function schnittpunkt(x11,y11,x12,y12,x21,y21,x22,y22: integer): Boolean;
var m1,m2 : double; x,y : integer; begin x:=0; y:=0; result:=false; m1 := (x11-x12)/(y11-y12); m2 := (y21-y22)/(x21-x22);
if m1<>m2 then begin x := round((m1 * (m2*x22 - y22 + y12) - x12) / (m1*m2 - 1) ); y := round(m2 * (x-x22) + y22);
if (x11<x) and (x<x12) and (y11<y) and (y<y12)
or
(x21<x) and (x<x22) and (y21<y) and (y<y22)
or
(x12>x) and (x>x11) and (y12>y) and (y>y11)
or
(x22>x) and (x>x21) and (y22>y) and (y>y21)
then result:=true;
end;
end; |
_________________ Wissen ist macht, nichts wissen macht auch nichts. ODER: Wer nichts weis, kann nichts vergessen.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Mi 20.04.05 11:59
Bei der Schnittpunkteberechnung habe ich nicht mit Steigungen gerechnet, da nicht jede Linie eine Steigung hat. Sie kann unendlich werden, wenn die Linie senkrecht ist. Deswegen wird der Schnittpunkt anders berechnet. Der Schnittpunkt wird hier via 2x2 Gleichungssystem gelöst. Also indem die zwei Linien in Parameterform gleichgesetzt werden.
Herleitung (Schnittpunktberechnung zweier endlicher Linien):
A1 und A2 seien die beiden Endpunkte der ersten Linie.
Dann kann man mit
P = A1*t+A2*(1-t) (Liniengleichung)
alle Punkte P der Linie erreichen, indem man irgendwelche Werte für t einsetzt.
Das ist einfach einzusehen: Falls t=1 ist bekommt man A1 raus; Falls t=0 ist bekommt man A2 raus. Und für die Werte dazwischen (also zwischen 0 und 1) erhält man alle anderen Punkte der Linie. Das t gibt also quasi an, zu welchem Anteil man bei A1 bzw. A2 ist. Bei t=0.5 ist man genau in der Mitte. (Bemerkung: Ist t>1 bzw. t<0, dann ist man über die Linie hinaus)
Seien nun B1 und B2 die beiden Endpunkte der zweiten Linie. Dann definiert
P = B1*t2+B2*(1-t2) t2=[0..1]
die zweite Linie.
Jetzt sucht man den gemeinsamen Punkt beider Linien; man setzt beide Formeln einfach gleich:
B1*t2+B2*(1-t2) = A1*t1+A2*(1-t1) (Schnittgleichung)
Die Aufgabe lautet nun: Suche t1 und t2, sodass obere Gleichung (Schnittgleichung) gilt.
Die Gleichung ist eine Vektorgleichung ( A1, A2, B1, B2 sind Vektoren). Ausgeschrieben erhält man also die zwei Gleichungen:
t1*A1X+(1-t1)*A2X=t2*B1X+(1-t2)*B2X
t1*A1Y+(1-t1)*A2Y=t2*B1Y+(1-t2)*B2Y
Das ist jetzt ein lineares Gleichungssystem mit 2 Unbekannten.
So. Wie man das löst führe ich nicht vor. Ich habs auch nicht von Hand gerechnet.
solve('t1*A1X+(1-t1)*A2X=t2*B1X+(1-t2)*B2X,t1*A1Y+(1-t1)*A2Y=t2*B1Y+(1-t2)*B2Y','t1,t2')
Ergibt dann:
t1=-(B1Y*A2X-A2Y*B1X+A2Y*B2X-B2X*B1Y+B1X*B2Y-B2Y*A2X)/(B1Y*A1X-B1Y*A2X-B2Y*A1X+B2Y*A2X-A1Y*B1X+A1Y*B2X+A2Y*B1X-A2Y*B2X)="I1/J";
t2=(A2Y*A1X-B2Y*A1X+B2Y*A2X+A1Y*B2X-A1Y*A2X-A2Y*B2X)/(B1Y*A1X-B1Y*A2X-B2Y*A1X+B2Y*A2X-A1Y*B1X+A1Y*B2X+A2Y*B1X-A2Y*B2X)="I2/J";
Man bemerke, dass bei t1 und t2 durch den gleichen Wert geteilt wird. Dieser Wert entspricht J im Delphi-Code. Die beiden Dividenden sind dann I1 (Zeile 45) und I2 (Zeile 51). (Also: t1=I1/J und t2=I2/J. Das J muss wie gesagt nur einmal berechnet werden.)
Ein Schnittpunkt liegt nun dann vor, falls t1=[0..1] und t2=[0..1].
Also dann, wenn I1/J=t1=[0..1] und I2/J=t2=[0..1] oder nochmals anders ausgedrückt:
0 < I1/J < 1 und 0 < I2/J < 1
Das ganze kann man jetzt nochmals ein bisschen umformulieren, damit keine Division nötig ist (damit man mit Integers rechnen kann). Die oberen Ungleichungen mal J ergibt die definitive Schnittbedingung:
0 < I1 < J und 0 < I2 < J falls J > 0
0 > I1 > J und 0 > I2 > J falls J < 0
Soviel zur Herleitung.
Bemerkungen zum Code:
- Zeile 44: Falls J=0, dann sind die Linien parallel und es gibt keine eindeutige Lösung bzw. es gibt überhaupt keinen Schnittpunkt.
- Erst auf Zeile 57 wird die Division durchgeführt, wenn feststeht, dass es ein Schnittpunkt gibt.
- Zeile 67: Hier werden alle t=I/J berechnet und man nimmt schlussendlich den grössten Wert (Zeile 58/59). Das grösste t steht für den nähesten Schnittpunkt.
Das wär's eigentlich schon. Auf Zeilen 73/74 werden dann die Koordinaten des Schnittpunktes anhand des grössten t berechnet. (Um die konkreten Koordinaten auf der Linie zu erhalten, setzt man t einfach die die Liniengleichung ein.)
Die Prozedur CorrectPos schaut sich also den neuen Punkt an (welcher in die Liste hinzugefügt werden soll). Er berechnet die Schnittpunkte zu den bisherigen Linien; falls es ein Schnittpunkt gibt, wird die Linie dann verkürzt bis zum Schnittpunkt (wenn es mehrere Schnittpunkte gibt, wird derjenige Schnittpunkte gewählt, welcher die Linie am kürzesten macht).
Hoffentlich war das jetzt einigermassen verständlich
Gruss,
Simon
|
|
Quivadis 
      
Beiträge: 314
UBUNTU 9.04
D2005 PERS, JAVA, D7 Pers.
|
Verfasst: Mi 20.04.05 12:45
Hi delfiphan,
du scheinst ein Matheass zu sein.
Wie du in mein Code erkennen kannst, wusste ich nicht wie man die Probleme paralell, steigung,... so richtig löst.
Danke, ohne dich wäre ich in meinen Projekt nie soweit gekommen. Hatte immer nur die Idee, aber keine Ahnung wie man das richtig umsetzt.
Werde mich jetzt an die Arbeit machen und versuchen das, mit Hilfe deiner Erklärung, in meinen Projekt umzusetzen. Wird nicht einfach, male ja in 3 verschieden Ebenen und und mit zoomstufen. Habe auch deswegen mehrere Listen die meine Koordinaten enthalten.
Denke mal, werde das schon irgendwie umsetzen können.
_________________ Wissen ist macht, nichts wissen macht auch nichts. ODER: Wer nichts weis, kann nichts vergessen.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Mi 20.04.05 21:20
Wenn man alles ineinander einsetzt und man den Schnittpunkt explizit als Formel hinschreibt, müsste eigentlich die gleiche Formel rauskommen wie bei dir.
Der Vorteil der Parameterform ist die einfache Bereichsüberprüfung und, dass man das ganze in Integern rechnen kann. Ich denke meine Berechnung ist von der Anzahl Operationen her etwas aufwändiger als deine, jedoch kann man - wie gesagt - fast alles mit Integern rechnen, was die Berechnung wieder beschleunigt. Auch kann man die Rechnung häufig frühzeitig beenden, da meist vor Ende der gesamten Rechnung fest steht, dass es gar keinen Schnittpunkt gibt.
PS: Durch die grobe Rundung auf ganze Zahlen scheint es in einigen Fällen doch möglich zu sein, eine sich überschneidende Kurve zu erhalten.
|
|
|