Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Schnittpunkt von Geraden - Ungenaue Berechnung

  • 1
  • 2

Werbeanzeige

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

1

18.05.2011, 08:29

Schnittpunkt von Geraden - Ungenaue Berechnung

Hi,

mal wieder ein Problem, bei dem ich nicht so recht weiterkomme. Ich berechne mir die Schnittpunkte zwischen zwei Geraden mittels der Formel y=mx+n welche ich für beide Geraden ermittele und dann in der nach x bzw. y umgestellten Form den Schnittpunkt errechne. Das funktioniert im Prinzip ganz gut, leider stoße ich da in einem Sonderfall auf ein Problem:


(Link)


Die beiden Geraden "blau" und "grün" treffen sich in einem Punkt, haben aber deutlich unterschiedliche Steigungen. Jetzt ermittele ich jeweils den Schnittpunkt mit der roten Geraden, welche in diesem Sonderfall durch exakt diesen gemeinsamen Punkt gehen. Die so ermittelten Schnittpunktkoordinaten für "grün" und "blau" weichen in dem Fall in x-Richtung doch recht deutlich voneinander ab, obwohl sie eigentlich ebenfalls im gleichen Punkt liegen sollten. "Deutlich" heißt hier, dass die Differenz >0.0001 ist. Es hilft auch nichts, wenn ich alle Eingangskoordinaten und das Ergebnis auf 4 Nachkommastellen (meine maximale Genauigkeit) runde, die Abweichung bleibt trotzdem so groß.

Meine Berechnung arbeitet Bereits mit double-Datentypen, so dass ich hier nicht weiß, wie ich noch genauer werden soll. Was nun, wie kann ich diese Ungenauigkeit umgehen?

marcgfx

Treue Seele

Beiträge: 236

  • Private Nachricht senden

2

18.05.2011, 09:14

oft kommt es auf die reihenfolge der operationen an. es wäre sicher von vorteil, wenn du auch den entsprechenden code posten könntest...
Devader DevLog - Devader spielen

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

3

18.05.2011, 10:12

Kein Problem:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

double deltaX1,deltaX2;
double m1,n1,m2,n2;

deltaX1=end1->x-start1->x;
deltaX2=end2->x-start2->x;

m1=(end1->y-start1->y)/deltaX1; // Steigungen ermitteln
m2=(end2->y-start2->y)/deltaX2;

if (ROUND(m1,MAX_ACCURACY)==ROUND(m2,MAX_ACCURACY)) return false; // Geraden sind parallel

n1=start1->y-(m1*start1->x); // Abstände von X-Achse ermitteln
n2=start2->y-(m2*start2->x);

result->x=(n2-n1)/(m1-m2);  // Schnittpunktkoordinate berechnen
result->y=m1*result->x+n1;


ROUND ist ein Makro, welches auf die maximal nötige Genauigkeit rundet. "start" und "end" legen jeweils den Anfang und das Ende einer Geraden fest, die Member x und y sind alles double.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

4

18.05.2011, 10:37

Rechne nicht mit der Form y = k * x + d sondern mit Vektoren. Aber abgesehen davon: Wie groß ist denn der Fehler und inwiefern ist das ein Problem. Wenn du Rundungsfehler nicht tolerieren kannst dann darfst du nicht mit Gleitkommazahlen arbeiten...
m4studios

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

5

18.05.2011, 10:43

Zitat von »dot«

Rechne nicht mit der Form y = k * x + d sondern mit Vektoren.


Ähm...und wie komme ich damit auf die Schnittpunkt-Koordinaten?

Zitat von »dot«

Aber abgesehen davon: Wie groß ist denn der Fehler und inwiefern ist das ein Problem. Wenn du Rundungsfehler nicht tolerieren kannst dann darfst du nicht mit Gleitkommazahlen arbeiten...


Teilweise ist die Abweichung in x-Richtung größer als 0,0001 (meiner maximal nötigen Genauigkeit).

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

6

18.05.2011, 11:42

Sind diese Geraden mit denen du den Schnittpunkt ermitteln willst immer horizontal? Warum berechnest du überhaupt den Schnittpunkt wenn du doch weißt dass die Gerade durch den gemeinsamen Punkt von blau und grün läuft!? Wofür genau brauchst du diesen Schnittpunkt?
m4studios

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

7

18.05.2011, 12:32

> Sind diese Geraden mit denen du den Schnittpunkt ermitteln willst immer horizontal?

Nein

> Warum berechnest du überhaupt den Schnittpunkt wenn du doch weißt dass die Gerade durch den gemeinsamen Punkt von blau und grün läuft!?

Das weiß ich nicht, die Geraden können an beliebigen Positionen liegen und dabei ist es halt _manchmal_ der Fall, dass sie da durch laufen.

> Wofür genau brauchst du diesen Schnittpunkt?

Die Antwort spare ich mir mal, da die Erklärung recht lange dauern würde und zur Problemlösung nix beisteuert.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

8

18.05.2011, 12:39

Naja, du könntest dir das Ganze eben nicht nur immer in der selben Dimension anschauen sondern je nachdem wie die Richtungsvektoren der beteiligten Geraden zueinander stehen die Dimension (x- oder y-Richtung) nehmen die numerisch das beste Ergebnis liefert. Oder noch besser: Transformier eine Gerade in das Koordinatensystem das von Punkt + Richtungsvektor und Normalvektor der andren Gerade aufgespannt wird und rechne dir den Schnittpunkt dort in der Dimension mit der größten Koordinate aus. Abgesehen davon wirds eben leider schwierig, Gleitkomma ist eben nicht die Lösung für alles...

Zitat von »Elmi«

Die Antwort spare ich mir mal, da die Erklärung recht lange dauern würde und zur Problemlösung nix beisteuert.

Sicher? Vielleicht könnte man dein Problem ja ganz ohne irgendwelche Schnittpunktsberechungen lösen!?
m4studios

Dieser Beitrag wurde bereits 6 mal editiert, zuletzt von »dot« (18.05.2011, 13:11)

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

9

19.05.2011, 07:44

Zitat von »dot«

Sicher? Vielleicht könnte man dein Problem ja ganz ohne irgendwelche Schnittpunktsberechungen lösen!?


Na dann versuche ich es mal mit einer Kurzfassung:

Ich habe geschlossene Polygone, welche ich mit einem Linienmuster füllen muss. Die Linien können dabei in jedem beliebigen Winkel daherkommen, aber nicht durcheinander, d.h. sie liegen immer parallel zueinander. Die Abstände zwischen den Linien sind ebenfalls unterschiedlich. Innerhalb eines Polygons kann ein weiteres Polygon liegen, was in dem Fall ein Loch definiert, sprich hier darf dann nicht gefüllt werden.

Mein Ansatz ist also, die einzelnen Linien über das Polygon zu legen und dann von deren Anfang zum Ende zu gehen, um zu überprüfen, ob es einen Schnittpunkt gibt. Bei diesen Schnittpunkten wird dann jeweils begonnen, die Linie tatsächlich zu zeichnen oder das auch wieder beendet. Dieses An/Abschalten löst zwar das Problem mit dem inneren Polygon, welches als Loch erscheinen soll, bringt mich aber in Schwierigkeiten, wenn die Berechnung im Treffpunkt zweier Polygonlinien ungenau ist. Hier wird ein und der selbe Punkt dann mal als An- und dann als Ausschalter angesehen, was dazu führt, dass die Linie am Beginn entweder nicht gezeichnet wird oder am Ende (dann schon außerhalb des Polygons bzw. innerhalb des Loches) fälschlicherweise gezeichnet wird.

Cubic

Frischling

Beiträge: 21

  • Private Nachricht senden

10

19.05.2011, 09:14

Mit Abweichungen musst du bei Fließkommazahlen immer rechnen - jetzt kannst du
A) hoffen das es mit long double klappt.
B) dir eine arbitrary precision arithmetics lib zulegen.
C) solche Sonderfälle erkennen und Ausnahmebehandlungen durchführen
D) mir fällt nix mehr ein, aber dir vielleicht.

Werbeanzeige

  • 1
  • 2

Ähnliche Themen