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.

[Flogo]

Na da frag ich mich doch wozu du das brauchst .... :roll:
:cheers:

Zitat:

Zitat von glkgereon

abs( g² - dasdaoben ) < 2

bedeutet ja dass der Abstand nur 2 Pixel/Einheiten groß sein darf

Die gedachte Ebene kriegst du ganz einfach in den Griff, wenn du deinen Kugeln keinen TPoint als Mittelpunkt gibst sondern ein record mit 2 Gleitkommazahlen. (vielleicht gibst so was auch schon fertig). Dann nur noch alle Trunc, Round, div .. rausstreichen und fertig. OK div solltest du nicht streichen, sondern durch / ersetzen und bei der Ausgabe musst du natürlich wieder runden (Darstellungsebene).

Die Darstellungsebene musst du wahrscheinlich sowieso im Massstab ein wenig variieren. (berechne mal 100.000 Kugeln und du weißt warum) Also musst du da sowieso wieder teilen/runden -> deine Gedachte Ebene in eine Zeichenebene umwandeln

[Nikolas]

*räusper* :roll:

[Flogo]

mal rein aus Interesse (und ein wenig OT):
wäre es eigentlich schneller wenn man g² und (2r)² vergleicht, statt g und 2r.
mit anderen Worten geht quadrieren schneller als Wurzelziehen

[Edit]
@Toxman: Ja ich dachte mir auch sowas.
[/Edit]

[Chewie]

Zitat:

Zitat von Meflin

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!

Du hattest in deinem ersten Post was davon geschrieben, dass du die Positionen deines Mittelpunktes, die du als Gleitkommawert hast, mit den Pixelwerten in Verbindung bringen musst.
Mit der gedanklichen Ebene mein ich, dass du zunächst mal alles berechnest, was du brauchst, also alles Kreise, Linien usw. Diese Berechnung machst du so genau, wie du sie brauchst.

Das Zeichnen ist dann erst der zweite Schritt. Nachdem du deine Welt berechnet hast, gehts ans Zeichnen. Hier kannst du, falls notwendig, noch eingreifen und dein Bild z.B. so skalieren, dass es in deine Zeichenfläche passt.

Aber wichtig ist die Trennung Berechnung - Zeichnung. Das Zeichnen selbst ist relativ trivial, die Herausforderung in der Grafik liegt in den Berechungen. Und je genauer die sind, desto richtiger die Bilder. Wenn du aber von vorneherein mit ganzen Pixeln rechnest, hast du keine sehr große Genauigkeit.

[Nikolas]

Leute, dass ist BWINF. Also bitte jetzt nichts mehr zum Thema posten.

[IngoD7]

Zitat:

Zitat von Toxman

Leute, dass ist BWINF. Also bitte jetzt nichts mehr zum Thema posten.

Was ist BWINF?

[Flogo]

Der Bundeswettbewerb für Informatik. Wir haben mit einem DP-Team teilgenommen und waren in der ersten Runde die 5. beste Gruppe *angeb* :-D
Das hier ist Teil einer Aufgabe aus der zweiten Runde, in der Gruppenarbeit leider verboten ist. d.h. nur grundsätzliche Fragen zum verständnis der Aufgaben dürfen geklärt werden. :angel:

[Meflin]

Zitat:

Zitat von Toxman

Leute, dass ist BWINF. Also bitte jetzt nichts mehr zum Thema posten.

also moment mal. es handelt sich hier um eine rein mathematische frage, wofür ich das brauche ist eindeutig mein bier und es geht hier keinesfalls um den verbotenen austausch von lösungsiddeen!
dass ich das für den BWINF brauche ist eine -wenn auch naheliegende - unterstellung, wie auch immer, es hat nichts mit einer lösungsidee zu tun!

[IngoD7]

[OT]
Ich werde mit Sicherheit jetzt nicht anfangen und jegliche Frage hinsichtlich ihrer moralischen Korrektheit künstlich hinterfragen. Wenn es offensichtlich ist, dass ein Menschlein andere übervorteilen will, kann ich mich ja immer noch entscheiden, ob ich meinen Senf dazugebe oder nicht.

Fremde Wettbewerbe, bei denen ich weder Ausrichter noch Teilnehmer bin - so auch ein "BWINF" -, sind mir so ziemlich egal, muss ich gestehen.

Wenn (ich unterstelle und vermute gar nichts!) in einer Frage in einem Delphi-Forum nach irgendwelchen Wettbewerbsregeln eine unerlaubte Handlung zu sehen ist (unerlaubt im Sinne des Wettbewerbs also, nicht im Sinne des Gesetzes), so ist das Sache des Wettbewerbs bzw. des Ausrichters desselben, nicht meine. Möglicherweise ist der Ausrichter in so einem Fall ja für einen Tipp ganz dankbar ...?

So hart es vielleicht klingt:
Ich möchte mir deshalb die Teilnahme an, und den Wissensaustausch in diesem Forum (und in anderen) möglichst nicht madig machen lassen.
[/OT]

[Flogo]

Wie gesagt: Gruppenarbeit und Lösungsideen auszutauschen ist verboten; Grundsätzliche Fragen sind erlaubt.
Als was die Gesellschaft für Informatik diesen Thread hier ansieht ist deren Auslegungssache.
Ich denke mal Toxmans Post war nicht ganz so extrem gemeint wie er auf Anhieb klingt ("Nichts mehr zum Thema" also nur noch OT :?: ).
Wir sollten hier eben nicht die "Hausaufgaben" von anderen machen. Solange die Frage allgemein bleibt werde ich für meinen Teil mich auch weiter an der Lösungshilfe beteiligen. Sollte die Frage zu konkret werden antworte ich einfach nicht mehr.

Zitat:

Zitat von IngoD7

Möglicherweise ist der Ausrichter in so einem Fall ja für einen Tipp ganz dankbar ...?

Naja das wäre schon ziemlich hart! Da müsste ich schon zufällig jemand finden, der sich die Aufgabe von einem Forum lösen lässt und dann abgibt. So nach dem Motto: "Schaut euch mal diese Aufgabe an [[e-mail]]. Mir fällt dazu gar nichts ein. Könnt ihr mir mal ein paar Tipps geben"