analytische 2D Geometrie

[BlackViruZ]

Hallo allerseits,

Ich versuche gerade mich ein bisschen an der 2D Spiele Programmierung, und will eine kleine (analytische) 2D Geometrie Klassenbibliothek schreiben.
Das Problem ist folgendes: Ich möchte die Berechnungen möglichst mathematisch korrekt haben, was mir aber durch die Gleitkommazahlen Ungenauigkeit gehörig versalzen wird - Ein Beispiel: Ich kann zwar ohne weiteres einen Punkt einer Geraden berechnen lassen, jedoch schlägt die anschließende Punktprobe ("ist der Punkt auf der Gerade?") fehl.

Wie kann ich die Ergebnisse möglichst.. sagen wir vereinheitlichen?
Ich will die Ergebnisse möglicht genau und einheitlich haben.. Irgendwelche Vorschläge?

Und nein: Ich will nach Möglichkeit keine fertige 2D API benutzen - man wächst mit seinen Projekten...

 

[Illuvatar]

Ich würd mal sagen, es gibt zwei Möglichkeiten:
- Verwende BigDecimal zur Darstellung deiner Zahlen, dort kannst du angeben auf wie viel Nachkommastellen genau exakt gerechnet werden soll. Wenn du zwei Zahlen vergleichst, werden sie vor dem Vergleich auf etwas weniger Nachkommastellen gerundet. Das sollte wirklich so gut wie immer funktionieren, wenn man es geschickt macht.
- Wenn du willst dass es immer korrekt ist, kannst du es sozusagen tatsächlich algebraisch machen. D.h. du schreibst Klassen für Brüche, n-te Wurzeln und ähnliches. Dann kriegst du aber spätestens bei transzendenten Zahlen ziemlich Probleme - außerdem kannst du dann auch die ganzen Methoden aus java.lang.Math nicht mehr verwenden. Vllt gibts solche Klassen schon irgendwo... sonst würde ich davon wohl eher abraten.

 

[Wookie81]

[...]jedoch schlägt die anschließende Punktprobe ("ist der Punkt auf der Gerade?") fehl.

Wie testet du das? Mit

if (Geradengleichung(Punkt)==0)
   printf ("Punkt auf Gerade");

?

Das dürfte immer fehlschlagen, weil der gerundete Punkte nie 100% auf der Gerade liegt. Du müsstest prüfen ob er innerhalb/unterhalb eines Schwellwerts ist:

float eps = 0.01;
if (abs(Geradengleichung(Punkt))<=eps)
   printf ("Punkt auf Gerade");

Wk

 

[Marco13]

Ich würde dir von beiden Möglichkeiten abraten
- BigDecimal ist grottigst langsam, und die entstehende Bebliothek wäre deswegen höchstens für "kleine" Berechnungen geeignet, und (wenn die BigDecimals in die API durchschlagen) "unbequem" zu verwenden
- Vom zweiten hat Illuvatar schon selbst abgeraten

Die "mathematische Korrektheit", die du beschreibst, kann es (wenn ich diesen Begriff richtig interpretiere) schon deswegen nicht geben, weil ein Punkt, dessen Koordinaten als float oder double gespeichert sind, z.B. NIE die x-Koordinate "0.1" haben kann. Wenn nun ein Schnittpunkt zwischen zwei Linien "matematisch präzise" bei x=0.1 liegt, und man einen Punkt mit x=0.1 anlegt, wird er (...präzise...) NICHT mit dem Schnittpunkt übereinstimmen.

Die übliche Abhilfe sind Epsilons. Die Abfrage "liegt ein Punkt auf der Linie" liefert dann z.B. "true", wenn der Punkt einen Abstand von weniger als 1e-6 zur Linie hat. Das kann in seltenen Fällen auch zu Problemen führen, aber ist der beste Kompromiß zwischen Präzision, Geschwindigkeit und Handhabbarkeit....

 

[BlackViruZ]

Bin grade noch auf der Arbeit - ich werde morgen oder wann ich Zeit finde mal die Variante mit dem Abstand ausprobieren, klingt ansich gut.
Über BigDecimal hatte ich auch bereits nachgedacht - habe mir allerding schon gedacht dasses damit nicht performant genug werden würde.

Wieso genau 1e-6?
Wie wurde das Problem bei den ganzen java-basierten Geometrie-Programmen (GeoGebra etc) gelöst?

Danke schonmal für die schnelle Hilfe

 

[Marco13]

1e-6 war mehr oder weniger "willkürlich". Mehr oder weniger, weil man bei float eben Zahlen von 1.0 und 1.0 + 1e-6 noch unterscheiden kann, und jeder kleinere Fehler auf Rundungsfehler zurückzuführen sein kann. Man könnte sich da noch was ausgefeilteres überlegen... Aber so die Größenordnung 1e-5 bis 1e-7 für float, oder 1e-10 bis 1e-14 für double sind wohl OK...

 

[BlackViruZ]

Ok, habe die Toleranz bis jetzt erstmal bei der Methode zur überprüfung auf Parallelität und Orthogonalität eingebaut - und: ES FUNKTIONIERT
Die Punktprobe muss noch warten, da sich erst ein weiteres Problem anbahnt:
Ich schreibe gerade an der Schnittpunktberechnung, und bin auf die entsprechende Formel im Toturialthread für analytische Geometrie gestoßen:

Schnittpunkt
Für den Schnittpunkt zweier Geraden muss man ein kleines Gleichungssystem lösen:

a0*x + b0*y + c0 = 0
a1*x + b1*y + c1 = 0

// das kann man z.B. folgendermassen weiter auflösen:

a1 / a0 * ( a0 * x + b0 * y + c0) = 0
a1*x + b1*y + c1 = 0

(b1 - a1 / a0 * b0 ) y + ( c1 - a1 / a0 * c0 ) = 0

y = ( a1 / a0 * c0 - c1 ) / (b1 - a1 / a0 * b0 )

x = (b0 * y + c0) / (-a0)

// Das funktioniert natürlich nur, falls a0 != 0. Andernfalls muss man einen anderen Parameter wählen...

Meiner Meinung nach ergibt sich bei der umgeformten final-formel mehr als das genannte Problem mit dem Parameter:

y = ( a1 / a0 * c0 - c1 ) / (b1 - a1 / a0 * b0 )

x = (b0 * y + c0) / (-a0)

Da eine Multiplikation mit 0 immer 0 ergibt, würde dies für die Formel bedeuten, weder a0 noch b0 darf 0 sein, da ansonsten eine Divide by Zero Exception ausgelöst würde... - Das heißt für die Geraden, das zur Schnittpunktbestimmung, diese (Geraden) weder parallel zur X noch zur Y achse verlaufen darf - meiner Meinung nach ein großes Problem...

Habe ich etwas in der Formel falsch verstanden, oder.. ?? - bin verwirrt

 

[BlackViruZ]

Eine mehr oder minder provisorische lösung wär natürlich folgendes.
man setzt diese Formel als private Methode um - methodensignatur - Punkt math_schnittpunktZwischen(Gerade, Gerade)
im vorraus wird überprüft ob die beiden Geraden parallel zu einer achse sind - ist nur eine von beiden parallel wird diese als 2. Gerade Parameter der methode übergeben, sind beide parallel, wird überprüft ob sie beide zur selben achse parallel sind.
Ist dies der Fall sind Sie sowieso parallel oder beschreiben die selbe Gerade und die Methode gibt null zurück - sind sie beiden zu unterschiedlichen Achsen parallel, wird von der zur X-Achse Parallelen die Y-Verschiebung und von der Y-Achsen Parallelen die X-Verschiebung in eine Punkt instanz geschrieben.

Wenn niemand eine einfachere Idee hat... ^^

 

[Landei]

Um die Steigung einer Geraden arithmenticexceptionfrei zu berechnen, gibt es Math.atan2.

Two other functions needs special comment. The first is Math.atan2. This takes two arguments, say x and y. The value of Math.atan2(y,x) is the angle that a line drawn from the origin of a rectangular coordinate system to the point (x,y) would make with the x-axis. (Notice the order of its arguments.) It thus converts rectangular coordinates to polar, or at least it finds the polar coordinate angle associated with the points. The effect is almost the same as Math.atan(y/x), which also returns the angle made by this line, since the tangent of that angle is the ratio y/x. However, Math.atan cannot tell the difference between the first and third quadrants, since the ratio, say, -1/-1 is the same as +1/+1. Nor will Math.atan work well if y=0, since division by 0 is not allowed. But Math.atan2 keeps the x and y arguments separated, so it can tell which quadrant the answer is in, and it can handle the case y=0.

Introduction to Java

 

[BlackViruZ]

Wo ich gerade darüber nachdenke fällt mir eine weitere Schwäche der Formel auf:

y = ( a1 / a0 * c0 - c1 ) / (b1 - a1 / a0 * b0 )

x = (b0 * y + c0) / (-a0)

Es darf bei dieser Formel in keinem fall b1 und a1 gleich groß sein - ansonsten findet auch hier eine Division by Zero statt - also darf die gerade welche als 2. übergeben wird auch nicht die Steigung -1 haben...

Vielleicht hat jmd einen Algorythmus für die Schnittpunktberechnung über die Parameterform der Geraden zur hand? Würde den ja selbst schreiben, aber Mathe is schon so lange her... -.-

 

[BlackViruZ]

Um die Steigung einer Geraden arithmenticexceptionfrei zu berechnen, gibt es Math.atan2.


Introduction to Java

Ich habe bereits Winkelberechungen implementiert, ich suche nicht nach Winkeln sondern nach dem Schnittpunkt zweier Geraden

 

[BlackViruZ]

So, habe es gelöst mit einem kleinen trick.
Meine Geraden und Vektoren sind über Parameterform beschrieben - allerdings wird bei der Instanzierung einer geraden (und bei einer Änderung an dem Objekt) die Lineare Gleichung der Geraden aufgestellt - also solange sie nicht y-Achsen parallel ist.
Und mit der Gleichung wird der Schnittpunkt berechnet (solange die beiden geraden nicht parallel sind).

Wenn eine der beiden geraden y-Paralellität aufweißt, wird die x-Koordinate von ihr als x-Koordinate des Schnittpunkts benutzt und in die lineare Gleichung der 2. Gerade eingesetzt - so wird dann die y-Koordinate des Schnittpunkts errechnet.

	public static Punkt schnittPunkt(Gerade a, Gerade b) {
		double x, y;
		if (a.istParallel(b)) {
			return null;
		} else if (a.getRichtungsVektor().ist_Parallel_zu_yAchse()) {
			x = a.getStandVektor().getX();
			y = b.steigung * x + b.yachsenabschnitt;
		} else if (b.getRichtungsVektor().ist_Parallel_zu_yAchse()) {
			x = b.getStandVektor().getX();
			y = a.steigung * x + a.yachsenabschnitt;
		} else {
			x = (b.yachsenabschnitt - a.yachsenabschnitt)
					/ (a.steigung - b.steigung);
			y = a.steigung * x + a.yachsenabschnitt;
		}
		return new Punkt(x, y);
	}

Das ganze ist noch in Denglisch^^ - ich denke die namen der aufgerufenen methoden etc sind selbsterklärend und falls es jmd braucht kann die Person eine entsprechende Methode wohl selbst schreiben.

Hat jmd eine bessere & schnellere Variante?

 

[Landei]

Ich habe bereits Winkelberechungen implementiert, ich suche nicht nach Winkeln sondern nach dem Schnittpunkt zweier Geraden

Mit atan2 kannst du die Steigung einer Geraden berechnen. Sind zwei Gerade jeweils durch einen Punkt x,y und eine Steigung s gegeben, rechnet man:

y1 + s1(x-x1) = y2 + s2(x-x2)
x*(s1-s2) = y2 - y1 + s1*x1 + s2*x2
x = (y2 - y1 + s1*x1 - s2*x2)/(s1-s2)

An dieser x-Koordinate schneiden sich die Geraden. Aber wenn dir das zu einfach ist...

 

[Steev]

Hat jmd eine bessere & schnellere Variante?

Ähm, ich ?!

Ich habe so eine lineare Schnittpunktberechnung zwischen zwei Geraden vor ein paar Tagen programmiert. Anbei findest du den Quellcode. Ich bin von folgender Annahme ausgegangen:

1. eine Gerade wird mithilfe von Vektoren anhand folgender Formel abgebildet:

v1 = p1 + t1 * (p2 - p1)

Wobei

(p2 - p1)

der Steigungsvektor ist.

Wenn wir zwei Geraden haben, dann können wir diese, um den Schnittpunkt zu ermitteln gleich setzen, dann können wir anhand der Parameterwerte für t1 und t2 (das sind quasi die Skalierungsfaktoren, die den Schnittvektor auf der jeweiligen Geraden bestimmen) ermitteln, wie wir die Formeln weiter auflößen müssen.

Gerade 1:
=> v1 = p1 + t1 * (p2 - p1)

=> v1_x = v1_p1_x + t1 * (v1_p2_x - v1_p1_x)
   v1_y = v1_p1_y + t1 * (v1_p2_y - v1_p1_y)

Ermittle den Ortsvektor für die Gerade v1
==> v1_dv_x = (v1_p2_x - v1_p1_x)
    v1_dv_y = (v1_p2_y - v1_p1_y)

=> v1_x = v1_p1_x + t1 * v1_dv_x
   v1_y = v1_p1_y + t1 * v1_dv_y

Gerade 2:
=> v2 = p1 + t2 * (p2 - p1)

=> v2_x = v2_p1_x + t2 * (v2_p2_x - v2_p1_x)
   v2_y = v2_p1_y + t2 * (v2_p2_y - v2_p1_y)

Ermittle den Ortsvektor für die Gerade v2
==> v2_dv_x = (v2_p2_x - v2_p1_x)
    v2_dv_y = (v2_p2_y - v2_p1_y)

=> v2_x = v2_p1_x + t2 * v2_dv_x
   v2_y = v2_p1_y + t2 * v2_dv_y

Gleichsetzen der beiden Geraden
=> v1 = v2

=> v1_p1_x + t1 * v1_dv_x = v2_p1_x + t2 * v2_dv_x | - v1_p1_x
   v1_p1_y + t1 * v1_dv_y = v2_p1_y + t2 * v2_dv_y | - v1_p1_y

=> t1 * v1_dv_x = v2_p1_x + t2 * v2_dv_x - v1_p1_x | - t2 * v2_dv_x
   t1 * v1_dv_y = v2_p1_y + t2 * v2_dv_y - v1_p1_y | - t2 * v2_dv_y

=> t1 * v1_dv_x - t2 * v2_dv_x = v2_p1_x - v1_p1_x
   t1 * v1_dv_y - t2 * v2_dv_y = v2_p1_y - v1_p1_y

=> [B]I.[/B] (v1_dv_x * t1) - (v2_dv_x * t2) = v2_p1_x - v1_p1_x
   [B]II.[/B] (v1_dv_y * t1) - (v2_dv_y * t2) = v2_p1_y - v1_p1_y

Da wir den Wert für t1 oder t2 benötigen gibt es jetzt einige verschiedene Möglichkeiten, t1 zu ermitteln:
1. Wenn v2_dv_x null ist, so gilt: [B]t1 = (v2_p1_x - v1_p1_x) / v1_dv_x[/B]
2. Wenn v2_dv_y null ist, so gilt: [B]t1 = (v2_p1_y - v1_p1_y) / v1_dv_y[/B]
3. Wenn v2_dv_x ungleich v2_dv_y ist, so muss v2_dv_x gleich v2_dv_y oder v2_dv_y gleich v2_dv_x sein, damit die Schritte 4. oder 5. zur ermittlung von t1 durchgeführt werden können. Dazu kann man ermitteln ob v2_dv_x > v2_dv_y ist, wenn dies der Fall ist, so gilt: I. / (v2_dv_x / v2_dv_y), ansonsten gilt: II. / (v2_dv_y / v2_dv_x). Wenn dies getan wurde, so muss entweder der Punkt 4, oder der Punkt 5 durchgeführt werden um t1 zu erhalten.
4. Wenn v2_dv_x gleich v2_dv_y ist, und v2_dv_x - v2_dv_y null ergibt, so kann durch I. - II. t1 ermittelt werden:
  => [B]I.[/B] (v1_dv_x * t1) - (v2_dv_x * t2) = v2_p1_x - v1_p1_x
     [B]II.[/B] (v1_dv_y * t1) - (v2_dv_y * t2) = v2_p1_y - v1_p1_y
  
  => I. - II.
  
  => (v1_dv_x * t1) - (v1_dv_y * t1) = (v2_p1_x - v1_p1_x) - (v2_p1_y - v1_p1_y)
  
  => (v1_dv_x - v1_dv_y) * t1 = (v2_p1_x - v1_p1_x) - (v2_p1_y - v1_p1_y)
  
  => t1 = ((v2_p1_x - v1_p1_x) - (v2_p1_y - v1_p1_y)) / (v1_dv_x - v1_dv_y)
5. Wenn v2_dv_x gleich v2_dv_y ist, und v2_dv_x + v2_dv_y null ergibt, so kann durch I. + II. t2 ermittelt ähnlich wie oben ermittelt werden.

Da wir jetzt den Wert für t1 haben, können wir Ihn einfach einsetzen, um t2 zu erhalten.
Wenn wir dann t2 haben setzen wir dies in v1 oder v2 ein und erhalten so die Schnittpunkte, etwa so:

=> [B]I.[/B] (v1_dv_x * t1) - (v2_dv_x * t2) = v2_p1_x - v1_p1_x
   [B]II.[/B] (v1_dv_y * t1) - (v2_dv_y * t2) = v2_p1_y - v1_p1_y

=> Einsetzen von t1 in I.

=> -(v2_dv_x * t2) = v2_p1_x - v1_p1_x - (v1_dv_x * t1)

=> -(v2_dv_x * t2) = v2_p1_x - v1_p1_x - (v1_dv_x * t1)

=> t2 = (v2_p1_x - v1_p1_x - (v1_dv_x * t1)) / - v2_dv_x

=> Einsetzen von t1 in v1 und t2 in v2
=> Vergleichen von v1 und v2, wenn die beiden Gleich sind, so haben die beiden Geraden einen gemeinsamen Schnittpunkt, wenn nicht, so schneiden sich die beiden Geraden nicht.
=> Prüfen ob t1 oder t2 größer als 1 oder kleiner als 0 sind, ist dies der Fall, so liegt der Schnittpunkt nicht auf dem Bereich der definierten Geraden, sondern auserhalb und es gibt auch keinen Schnittpunkt.
=> Fertig :)

In meinem Quellcode (Klasse Collider) steht die Lösung nochmal etwas in den Kommentaren erläutert.

Ich hoffe du kannst mit meinem Lösungsansatz etwas anfangen...

Gruß
Steev

Edit:
Ich habe die Lösung mal etwas erläutert, auch wenn Ansätze in vorherigen Posts schon stehen.

 

[BlackViruZ]

Ich danke nochmal allen für dich Hilfe,
bin soweit damit erstmal zufrieden

Wenn das Projekt irgendwann mal halbwegs fertig werden sollte, stell ich's kurz vor^^

MfG Blacky - Thread erledigt