Kreise die sich berühren...

[Meflin]

Hi,

ich möchte rausfinden, ob sich 2 Kreise (mit demselben Radius r) in einem beliebigen Koordinatensystem berühren, soll heissen einen Schnittpunkt haben.
Dazu hab ich mir folgendes überlegt: Sie haben genau dann einen Schnittpunkt, wenn die Gerade durch die beiden Mittelpunkte der Kreise genau 2r lang ist. Um diese Gerade (ich taufe sie g) zu berechnen, denke ich mir ein Hilfsdreieck, um mit Hilfe des Satzes des Pytagoras (a² + b² = c²) dann das c (in diesem falle g) berechnen zu können, was mich dann schließlich zu dieser gleichung bringt:

Code:

g² = (X(Km2) - X(Km1))² + (Y(Km2) - Y(Km1))²

wobei Km Kreismittelpunkt heissen soll ;) also X(Km1) der X - Wert des Mittelpunktes des Kreises 1 ist.

so, jetzt kommt das eigentliche Problem: die rechte Seite dieser Gleichung ist ja einfach zu berechnen, nur dann muss ich ja die Wurzel aus g² berechnen, um dann g mit 2r vergleichen zu können.
Aber: es gibt ja bei Pixeln keine Komma-Werte, und das verwendete koordinatensystem wird definitiv Pixel als einheit verwenden. Bei Wurzel aus g² wird aber doch selten eine Ganzzahl herauskommen, d.h. wenns dumm läuft (weil ich mit gerundetem g - Wert vergleichen muss) erkennt die function nicht, dass sich die beiden Kreise berühren, obwohl sie es tun!

Wie könnte cih dieses Problem beheben?

*MFG*

[ibp]

indem du abfragst ob g<=2r wobei ich g dann nicht runden würde sondern mit einem gleitkomma wert(r) rechnen würde!!!

[Meflin]

Zitat:

Zitat von ibp

indem du abfragst ob g<=2r wobei ich g dann nicht runden würde sondern mit einem gleitkomma wert(r) rechnen würde!!!

:wall: manchmal kommt man auf die einfachsten sachen nicht. thx :)

[IngoD7]

:shock: Hä?

Dann schlägt die Funktion aber auch zu, wenn die beiden Kreise sich überschneiden. Ich dachte, es sei nur von Berührung die Rede?

[Chewie]

Ich würde beim Zeichnen grundsätzlich zwei Ebenen betrachten: Einmal die gedankliche Ebene, die (weitgehend) stetig ist. Dort arbeitest du mit Kommazahlen. Alle Berechnungen, die du machst, machst du hier.
Wenn dein Bild soweit berechnet ist, gehts ans Zeichnen. Dann brichst du deine stetigen Zahlen in diskrete runter, am einfachsten mittels Trunc.

Diese Trennung hat den Vorteil, dass du immer mit den exakten Werten (sofern mab bei Gleitkommadarstellungen von "exakt" sprechen kann; exakt heißt hier immer, der Unterschied zweier Zahlen ist nicht groß ;) ) rechnest und nicht Pixelwerte und Werte in deiner gedachten Welt mischen musst. Außerdem kann sich die Größe deiner Darstellung ändern, in diesem Fall müsstest du sonst auch die Größe deiner Welt ändern!

[ibp]

natürlich auch wenn sie sich überschneiden, das ist richtig!

[IngoD7]

Zitat:

Zitat von ibp

natürlich auch wenn sie sich überschneiden, das ist richtig!

Siehst du, und mich wundert nun, wieso Meflin mit dieser (Nicht-)Lösung :wink: seines Problems zufrieden ist ...

Wo er sich doch so viel Mühe gegeben hat, genauestens zu erklären, wann eine Berührung stattfindet und wieso ein Unterschied zwischen der reinen Berechnung einer Berührung und ihrer Darstellung in einem Pixel-Raster auftreten kann.

Ich würde es bei der Berechnung von g (ohne Rundung) belassen und manuell eine erlaubte Abweichung von 2r festlegen, innerhalb derer man noch von Berührung ausgehen darf.

[glkgereon]

dann kann man ja gucken ob abs( g² - dasdaoben ) < 2 oder sowas....

[Meflin]

edit: erstmal respekt, dachte nicht dass gleich so viele ideen kommen :thumb:

Zitat:

Zitat von Chewie

Ich würde beim Zeichnen grundsätzlich zwei Ebenen betrachten: Einmal die gedankliche Ebene, die (weitgehend) stetig ist. Dort arbeitest du mit Kommazahlen. Alle Berechnungen, die du machst, machst du hier.
Wenn dein Bild soweit berechnet ist, gehts ans Zeichnen. Dann brichst du deine stetigen Zahlen in diskrete runter, am einfachsten mittels Trunc.

Diese Trennung hat den Vorteil, dass du immer mit den exakten Werten (sofern mab bei Gleitkommadarstellungen von "exakt" sprechen kann; exakt heißt hier immer, der Unterschied zweier Zahlen ist nicht groß ;) ) rechnest und nicht Pixelwerte und Werte in deiner gedachten Welt mischen musst. Außerdem kann sich die Größe deiner Darstellung ändern, in diesem Fall müsstest du sonst auch die Größe deiner Welt ändern!

also das musst du mir irgendwie nochmal erklären: die berechnungen in der gedanklichen ebene, mit welchen daten sollte ich die denn dann machen? ich kann ja die berechnung nur mit den daten der wirklichen ebene machen?! irgendwie verstehe ich nicht so ganz, wie du das meinst!

Zitat:

Zitat von IngoD7

Siehst du, und mich wundert nun, wieso Meflin mit dieser (Nicht-)Lösung seines Problems zufrieden ist ...

Wo er sich doch so viel Mühe gegeben hat, genauestens zu erklären, wann eine Berührung stattfindet und wieso ein Unterschied zwischen der reinen Berechnung einer Berührung und ihrer Darstellung in einem Pixel-Raster auftreten kann.

Ich würde es bei der Berechnung von g (ohne Rundung) belassen und manuell eine erlaubte Abweichung von 2r festlegen, innerhalb derer man noch von Berührung ausgehen darf.

nun ja, das wäre kein problem gewesen, da es sich um bewegte kreise handelt, sprich bevor die 2 kreise schnittpunkte haben könnten, haben sie ja schon einen, und das programm wird gestoppt. dieses problem tritt also nicht auf, allerdings bleibt die ungenauigkeit wenn ich g aufrunde, sprich es ist nur eine halbe lösung des problems.
allerdings scheint mir eine toleranz von 2r doch etwas zu groß !? du meinst wohl 2 pixel oder?

[IngoD7]

Zitat:

Zitat von Meflin

allerdings bleibt die ungenauigkeit wenn ich g aufrunde, sprich es ist nur eine halbe lösung des problems.

Dann runde eben nicht auf. Sowohl ibp's Lösung (die wie gesagt auf Berührung und Überschneidung prüft) als auch mein Vorschlag runden g nicht.

Zitat:

Zitat von Meflin

allerdings scheint mir eine toleranz von 2r doch etwas zu groß !? du meinst wohl 2 pixel oder?

Nein. Ich meine eine Abweichung des Wertes g von dem Wert 2r, nicht eine Abweichung um 2r. :-D

Also: Man berechnet g und die Summe der beiden Radien. Eine kleine Abweichung voneinander wird dem Pixel-Problem angelastet und trotzdem als Berührung erkannt. Welche Abweichung tolerierbar ist, kann ich dir jetzt so nicht sagen. Musst du notfalls ausprobieren.